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

Или, точнее, каково определение комбинаторного алгоритма и линейного алгоритма, соответственно?

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

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

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


approximation np-complete
person Tobias    schedule 16.06.2009    source источник
comment
Вы уверены, что линейное программирование разрешимо за линейное время? Я считаю, что в линейном программировании линейное применяется к степени решаемых уравнений, а не обязательно к сложности алгоритма для его решения.   -  person JB King    schedule 27.06.2009
comment
Линейное программирование разрешимо за полиномиальное (не линейное) время.   -  person pyon    schedule 12.09.2009

Ответы (3)


arrow_upward
4
arrow_downward

Вопрос в формулировке проблемы.

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

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

person BBK    schedule 25.09.2011

arrow_upward
0
arrow_downward

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

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

person PaulJWilliams    schedule 16.06.2009
comment
Извините, это не то, что я ищу. Я попытался уточнить вопрос. - person Tobias; 16.06.2009

arrow_upward
0
arrow_downward

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

person JesperE    schedule 16.06.2009
comment
Извините, это не то, что я ищу. Я попытался уточнить вопрос. - person Tobias; 16.06.2009