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

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

Версия 15:49, 20 мая 2020

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

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

  • А какие — за ?
Источник — «https://discopal.ispras.ru/index.php?title=Полиномиальный_в_среднем_алгоритм_для_задачи_упаковки/Задачи/ex-packing-average-bad-and-good-data&oldid=11112»