Полиномиальный в среднем алгоритм для задачи упаковки/Задачи/ex-packing-average-bad-and-good-data — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 1: Строка 1:
 +
<big>Цыганова Светлана, 974 гр.</big>
 +
 
* Какие входные данные для алгоритма динамического программирования для упаковки
 
* Какие входные данные для алгоритма динамического программирования для упаковки
 
заставят его работать экспоненциально долго?
 
заставят его работать экспоненциально долго?
Строка 4: Строка 6:
 
* А какие — за <m>O(n^3)</m>?
 
* А какие — за <m>O(n^3)</m>?
  
[[Category:Нерешенные задачи]]
+
'''Решение'''
<!--Вообще-то, решения уже есть-->
+
 
 +
1) Экспоненциально долго алгоритм будет работать на частный случае подмножеств: каждое подмножество будет отвечать некоторому элементу, таким образом число подмножеств равно числу элементов, все подмножества попарно не пересекаются (диагональная матрица инцидентности). Тогда столбцов будет n. Для каждого столбца число объектов(совокупность решения, покрытия, размера покрытия) в листе X увеличивается в 2 раза (для каждого объекта на предыдущем шаге приписываем в лист ещё один объект). Таким образом для i-го столбца будет совершено <m>2^i</m> прохода по внутреннему циклу, и для последнего столбца - <m>2^n</m>. Таким образом после работы в X будет <m>2^n</m> объектов. Чтобы их записать в X, очевидно, надо было потратить экспоненциальное время. Таким образом на данном входе алгоритм работает экспоненциальное время.
 +
 
 +
[[Category:На проверку]]

Версия 18:25, 1 декабря 2014

Цыганова Светлана, 974 гр.

  • Какие входные данные для алгоритма динамического программирования для упаковки

заставят его работать экспоненциально долго?

  • А какие — за ?

Решение

1) Экспоненциально долго алгоритм будет работать на частный случае подмножеств: каждое подмножество будет отвечать некоторому элементу, таким образом число подмножеств равно числу элементов, все подмножества попарно не пересекаются (диагональная матрица инцидентности). Тогда столбцов будет n. Для каждого столбца число объектов(совокупность решения, покрытия, размера покрытия) в листе X увеличивается в 2 раза (для каждого объекта на предыдущем шаге приписываем в лист ещё один объект). Таким образом для i-го столбца будет совершено прохода по внутреннему циклу, и для последнего столбца - . Таким образом после работы в X будет объектов. Чтобы их записать в X, очевидно, надо было потратить экспоненциальное время. Таким образом на данном входе алгоритм работает экспоненциальное время.