Оптимальное решение известной NP-полной задачи, когда входные значения достаточно близки друг к другу.
Делиться
В этой статье я представлю решение задачи суммирования подмножеств, имеющее линейную временную сложность O(n), если все 'n' входных значений достаточно близки друг к другу. Вскоре мы увидим, что на самом деле означает это условие, а также почему его часто можно соблюдать (или почти соблюдать) на практике. Для входных данных, которые «почти близки» друг к другу, алгоритм все еще имеет определенную вероятность работать достаточно быстро.
Данная статья построена следующим образом:
- В главе 1 мы вспомним задачу о сумме подмножеств и покажем, вероятно, наиболее тривиальное решение этой задачи, основанное на методе полного перебора.
- В главе 2 рассматривается класс NP-полных задач и связь задачи о сумме подмножеств с ним.
- В главе 3 рассматривается широко используемое решение, основанное на методе динамического программирования, и объясняется, почему это псевдополиномиальный алгоритм.
- В главе 4 я представлю новый алгоритм, называемый «Решение на основе интервалов».
- В главе 5 будет показано, что, подобно методу динамического программирования, алгоритм, основанный на интервалах, также может восстановить точное подмножество элементов, формирующих заданную целевую сумму, а не просто ответить, достижима ли целевая сумма или нет.
- Наконец, в главе 6 мы увидим, почему алгоритм, основанный на интервалах, фактически достигает линейной временной сложности, если все 'n' входных значений достаточно близки друг к другу (а также мы поймем, что на самом деле означает условие «достаточно близки»).
Источник: towardsdatascience.com
