1313
правок
Задача коммивояжера с несколькими внутренними точками: различия между версиями
Материал из WEGA
Задача коммивояжера с несколькими внутренними точками (посмотреть исходный код)
Версия от 04:27, 7 декабря 2024
, 7 декабря 2024→Литература
Irina (обсуждение | вклад) м (→Применение) |
KVN (обсуждение | вклад) |
||
| (не показаны 4 промежуточные версии 1 участника) | |||
| Строка 60: | Строка 60: | ||
Метод, разработанный Кнауэром и Спиллнером [12], можно применить и к задаче коммивояжера. Согласно их результату, наилучшая известная на данный момент временная сложность алгоритма для TSP составляет | Метод, разработанный Кнауэром и Спиллнером [12], можно применить и к задаче коммивояжера. Согласно их результату, наилучшая известная на данный момент временная сложность алгоритма для TSP составляет <math>2^{O(\sqrt{k} \; log \; k)} poly(n).</math> | ||
== Открытые вопросы == | == Открытые вопросы == | ||
На данный момент не найдено нижней границы временной сложности. В частности, возможно ли при наличии разумных теоретико-сложностных предположений доказать невозможность существования алгоритма решения задачи коммивояжера с временем выполнения | На данный момент не найдено нижней границы временной сложности. В частности, возможно ли при наличии разумных теоретико-сложностных предположений доказать невозможность существования алгоритма решения задачи коммивояжера с временем выполнения <math>2^{O(\sqrt{k})} poly(n)</math>? | ||
== См. также == | == См. также == | ||
О задаче коммивояжера: | О задаче коммивояжера: | ||
* [[Евклидова задача коммивояжера]] | |||
* [[Гамильтоновы циклы в случайных графах пересечений]] | |||
* [[Конкурс по реализации эвристик для задачи коммивояжера]] | |||
* [[Метрическая задача коммивояжера]] | |||
Об алгоритмах с фиксированными параметрами: | Об алгоритмах с фиксированными параметрами: | ||
* [[Нахождение ближайшей подстроки]] | |||
* [[Параметризованная задача выполнимости КНФ]] | |||
* [[Кернелизация вершинного покрытия]] | |||
* [[Вершинное покрытие и деревья поиска]] | |||
О других вопросах: | О других вопросах: | ||
* [[Триангуляция с минимальным весом]] | |||
== Литература == | == Литература == | ||
| Строка 122: | Строка 124: | ||
19. Spillner, A.: Optimal convex partitions of point sets with few inner points. In: Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG), 2005, pp. 34-37 | 19. Spillner, A.: Optimal convex partitions of point sets with few inner points. In: Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG), 2005, pp. 34-37 | ||
[[Категория: Совместное определение связанных терминов]] | |||
