В чем разница между «комбинаторным алгоритмом» и «линейным алгоритмом»?

Question

Вернее, каково определение комбинаторного алгоритма и линейного алгоритма, соответственно ??1001*

Чтобы было понятно, потому что, очевидно, первые респонденты неправильно поняли вопрос: я не ищу определение алгоритма, работающего в линейное время против нелинейного времени. Линейный алгоритм так или иначе связан с линейным программированием, которое представляет собой метод поиска или аппроксимации решений задач линейной оптимизации.

Поскольку NP-сложные задачи очень сложны, существует целая область, пытающаяся найти приблизительные решения. Например, задача коммивояжера имеет несколько приближенных решений, которые выполняются за полиномиальное время и дают решение, которое находится в заданных пределах наилучшего решения.

Некоторые из этих аппроксимирующих алгоритмов называются линейным алгоритмом, другие комбинаторным алгоритмом; и последнее кажется предпочтительным (почему?). Вот две концепции, которые я хотел бы понять.

Answer 1

Проблема заключается в постановке проблемы.

Так же, как вы сказали, «Задача коммивояжера» (TSP) равна NP-hard именно потому, что она имеет дискретную формулировку проблемы (продавец либо посещает город, либо нет в определенное время). Эта дискретная формулировка делает проблему и ее алгоритм комбинаторным . (Обратите внимание, что не все комбинаторные задачи являются NP-сложными; рассмотрим алгоритмы сортировки.)

Однако, ослабление TSP с помощью линейного программирования (LP) приводит к алгоритму linear . Это потому, что проблема была переформулирована так, что продавец посещает город определенную долю времени. Основная причина использования LP-релаксации заключается в том, что расслабленная версия может быть решена за полином времени. Однако решение для релаксации LP не обязательно является решением исходной проблемы.

Answer 2

Комбинаторные алгоритмы "взрываются" по мере роста их вклада. Линейные алгоритмы растут пропорционально их входным данным, тогда как комбинаторные алгоритмы растут пропорционально экспоненте (или хуже) или их входным данным: перечисляя, например, все возможные пути через граф.

Answer 3

Линейный алгоритм имеет тенденцию работать только с одним набором данных: «Возьмите все числа в наборе a, удвойте их и поместите результат в набор b». Количество операций равно количеству элементов в наборе

Комбинаторный работает с комбинациями наборов: «Для каждого числа в наборе a вычислите сумму этого числа и каждого числа в наборе b и распечатайте на экран». Количество операций является произведением размера набора a и размера набора b.