Минимален Хамилтонов цикъл

[ptj]

Имам въпрос от теория на графите:

Някой знае ли каква е минималната сложност на намерените до момента алгоритми за намиране на хамилтонов цикъл в граф с минимално тегло (сума на обходените ребра)?

[peyo]

Имам въпрос от теория на графите:

Някой знае ли каква е минималната сложност на намерените до момента алгоритми за намиране на хамилтонов цикъл в граф с минимално тегло (сума на обходените ребра)?

Изглежда говорим за TSP проблема. Не съм чул някой да е успял да избегне експоненциално решение. Моя search към днешна дата казва:

In summary, the choice of the "best" algorithm for TSP depends on specific requirements:

Exact Solution Needed: Concorde TSP Solver is the premier choice, albeit with significant computational demands. $O(2^n⋅n^2)$

Approximate Solution with Performance Guarantee: Christofides' Algorithm and its variants offer provable bounds on solution quality.

High-Quality Heuristic Solution: Lin-Kernighan and Ant Colony Optimization provide effective heuristics, especially for large instances where exact methods are impractical.

Също така изглежда някои хора работят по прилагането на quantum computer алгоритми и съм доста сигурен, че ще чуем нещо в близките години.

[ammornil]

Имам въпрос от теория на графите:

Някой знае ли каква е минималната сложност на намерените до момента алгоритми за намиране на хамилтонов цикъл в граф с минимално тегло (сума на обходените ребра)?

Изглежда говорим за TSP проблема. Не съм чул някой да е успял да избегне експоненциално решение. Моя search към днешна дата казва:

In summary, the choice of the "best" algorithm for TSP depends on specific requirements:

Exact Solution Needed: Concorde TSP Solver is the premier choice, albeit with significant computational demands. $O(2^n⋅n^2)$

Approximate Solution with Performance Guarantee: Christofides' Algorithm and its variants offer provable bounds on solution quality.

High-Quality Heuristic Solution: Lin-Kernighan and Ant Colony Optimization provide effective heuristics, especially for large instances where exact methods are impractical.

Също така изглежда някои хора работят по прилагането на quantum computer алгоритми и съм доста сигурен, че ще чуем нещо в близките години.

Това от ChatGPT ли го взехте? Можеше поне да го преведете на български за да е достъпно за цялата аудитория на форума.


За някои специални случаи на ориентирани графи с малък брой възли и когато не се изисква висока точност, приблизителните алгоритми могат да бъдат достатъчно добри. Но като цало колегата е прав, минималният брой цикли, гарантиращ оптимално решение на "проблема с пътуващия търговец", е експоненциално пропорционален на броя на възлите. Ние сме ползвали това в миналото със сравнително добри времеви резултати. За съжаление, колегата който го направи вече не работи при нас, а аз нямам достатъчно знания в областта за да съм Ви по-полезен.

[ptj]

Имам въпрос от теория на графите:

Някой знае ли каква е минималната сложност на намерените до момента алгоритми за намиране на хамилтонов цикъл в граф с минимално тегло (сума на обходените ребра)?

Изглежда говорим за TSP проблема. Не съм чул някой да е успял да избегне експоненциално решение. Моя search към днешна дата казва:

In summary, the choice of the "best" algorithm for TSP depends on specific requirements:

Exact Solution Needed: Concorde TSP Solver is the premier choice, albeit with significant computational demands. $O(2^n⋅n^2)$

Approximate Solution with Performance Guarantee: Christofides' Algorithm and its variants offer provable bounds on solution quality.

High-Quality Heuristic Solution: Lin-Kernighan and Ant Colony Optimization provide effective heuristics, especially for large instances where exact methods are impractical.

Също така изглежда някои хора работят по прилагането на quantum computer алгоритми и съм доста сигурен, че ще чуем нещо в близките години.

Благоодаря!

Имам втори въпрос свързан със съмненията ми в корекността на резултатa $O(2^n⋅n^2)$.
По принцип за всяка една задача съществува алгоритъм на пълно изчерпване съответстващ на множеството от всички нейни възможни резултати, т.е. пълното множество за нея.
Примерно за задачата [tex]A[/tex] съответното пълно множество може да го означим с [tex][A][/tex].

Някой знае ли за съществуването на долна оценка на бързодействието на алгоритмите, решаващи задачата [tex]А[/tex], на база стойността на [tex][A][/tex] (при ограничена памет).

[peyo]

Изглежда говорим за TSP проблема. Не съм чул някой да е успял да избегне експоненциално решение. Моя search към днешна дата казва:

In summary, the choice of the "best" algorithm for TSP depends on specific requirements:

Exact Solution Needed: Concorde TSP Solver is the premier choice, albeit with significant computational demands. $O(2^n⋅n^2)$

Approximate Solution with Performance Guarantee: Christofides' Algorithm and its variants offer provable bounds on solution quality.

High-Quality Heuristic Solution: Lin-Kernighan and Ant Colony Optimization provide effective heuristics, especially for large instances where exact methods are impractical.

Също така изглежда някои хора работят по прилагането на quantum computer алгоритми и съм доста сигурен, че ще чуем нещо в близките години.

Благоодаря!

Имам втори въпрос свързан със съмненията ми в корекността на резултатa $O(2^n⋅n^2)$.
По принцип за всяка една задача съществува алгоритъм на пълно изчерпване съответстващ на множеството от всички нейни възможни резултати, т.е. пълното множество за нея.
Примерно за задачата [tex]A[/tex] съответното пълно множество може да го означим с [tex][A][/tex].

Някой знае ли за съществуването на долна оценка на бързодействието на алгоритмите, решаващи задачата [tex]А[/tex], на база стойността на [tex][A][/tex] (при ограничена памет).

Хмм. Нещо съм объркал в моя research. Всъщност сложността $O(2^n⋅n^2)$ се отнася за Bellman-Held-Karp алгоритъма и е за малки множества (под 20 града).
Алгоритъма на Concorde от друга страна твърди, че също гарантирано намира оптималното решение, и се хвалят, че са успели да намерят решение за 85900 града. Опитах се да намеря каква е сложността на Concorde, но никъде не е публикувана, а chatgpt твърди, че също е експоненциална:

Conclusion: Big O Complexity of Concorde: Worst-Case Time Complexity: $O(k^n)$ where $k>1$, indicating exponential growth.
Exact Value of k: The base k is not fixed and depends on the specifics of the algorithm's implementation and the problem instance.

Но не знам колко да му вярвам.
Да видим до тук. Пълно решение $О(N!)$. Bellman-Held-Karp $O(2^n⋅n^2)$, което даже не е очевидно по-добро от първото, но е. Concorde прави някакви чудеса, но пак е експоненциално. Тогава кой знае, може би съществува долна оценка на бързодействието на алгоритмите на базата на [tex][A][/tex]?! Според chatgpt човечеството още не може да отговори на този въпрос, защото дори не знаем дали $P=NP$, а двата проблема може да са свързани. Тоест още сме малки и трябва да да се развиваме.

[ptj]

Директния въпрос дали съществуват задачи, чиито решения могат да бъдат проверени за полиноминално време, но тяхното решение изискава експоненциално време е безмислен.
Обявената за него награда се дължи на идеята, че решението му ще изисква нови идеи в методите за оценка и намиране на нови класове универсални оптимални алгоритми.

П.П. Задачарта за търговския пътник е много добър пример за NP задача, в която липсата на директна връзка между решенията при смяна на размерността я прави изключително трудна за намиране на ефективен оптимален алгоритъм.