Задача коммивояжера с несколькими внутренними точками

Ключевые слова и синонимы

Задача коммивояжера; поиск гамильтонова контура минимальной стоимости; поиск гамильтонова контура с минимальным весом; поиск гамильтонова цикла минимальной стоимости; поиск гамильтонова цикла с минимальным весом

Постановка задачи

В задаче коммивояжера (traveling salesman problem, TSP) имеются n городов 1, 2, .., n с попарными расстояниями d(i, j) между городами i и j. Задача заключается в поиске кратчайшего пути, который обходит все города строго по одному разу и в конце возвращается в исходный город. TSP – одна из самых известных задач комбинаторной оптимизации – является NP-полной. Более подробное изложение можно найти в книге Лоулера, Ленстры, Ринной Кана и Шмойса [14].

Специальным случаем задачи коммивояжера является так называемая евклидова задача коммивояжера, в которой города расположены на евклидовой плоскости, а расстояния представляют собой просто евклидовы расстояния. В свою очередь, специальным случаем евклидовой задачи коммивояжера является выпуклая евклидова задача коммивояжера, в которой города образуют выпуклую конфигурацию. Евклидова задача коммивояжера также является NP-полной [4, 17], но ее выпуклый вариант решить довольно просто: объезд по границе выпуклой оболочки представляет собой кратчайший путь. В свете этих двух фактов возникает естественный вопрос: как влияет количество внутренних точек на сложность задачи? Здесь под внутренней точкой конечного множества точек P понимается точка из P, лежащая во внутренней области выпуклой оболочки P. Интуитивно можно предположить, что чем меньше внутренних точек, тем проще решить задачу.

Последующие результаты подтверждают это соображение при помощи простых точных алгоритмов.

Основные результаты

Теорема 1. Специальный случай евклидовой задачи коммивояжера с несколькими внутренними точками может быть решен со следующими затратами времени и памяти (обозначим за n общее число городов, а за k – число городов во внутренней области выпуклой оболочки): (1) за время O(k!kn) с затратами O(k) памяти; (2) за время [math]\displaystyle{ O(2^k k^2 n) \; }[/math] с затратами [math]\displaystyle{ O(2^k kn) \; }[/math] [1] памяти.

Предположим, что выпуклая область для заданного множества точек уже определена, на что потребовалось O(n log n) времени и O(n) памяти. Заметим, что приведенные границы памяти не учитывают память, необходимую для хранения входных данных, но только используемую оперативную память (как это принятии в теории вычислительных машин и систем).

Из теоремы 1 следует, что с точки зрения параметризованной сложности [2, 3, 16] эти алгоритмы представляют собой алгоритмы с фиксированными параметрами, принимая за параметр число внутренних точек k – и, следовательно, задача принадлежит к классу разрешимых с фиксированным параметром. (Время выполнения алгоритма с фиксированным параметром составляет [math]\displaystyle{ O(f(k) poly(n)) \; }[/math], где n – размер входных данных, k – параметр, а [math]\displaystyle{ f: \mathbb{N} \to \mathbb{N} }[/math] – произвольная вычислимая функция. Например, алгоритм с временем выполнения [math]\displaystyle{ O(5^k n) \; }[/math] является алгоритмом с фиксированным параметром, тогда как алгоритм с временем выполнения [math]\displaystyle{ O(n^k) \; }[/math] не является таковым). Заметим, что второй алгоритм дает точное решение с полиномиальным временем выполнения при k = O(log n).

Этот метод может быть расширен на определенные обобщенные версии задачи коммивояжера (TSP). В частности, Дейнеко и др. [1] заявили, что задача коммивояжера со сбором наград и частичная задача коммивояжера могут быть решены аналогичным образом.

Применение

Данная теорема рассматривает задачу с теоретической стороны. Практического применения результата не предполагалось.

Что же касается теоретического применения, то этот подход (представленный в разделе «Постановка задачи») применялся к различным другим геометрическим задачам. Перечислим некоторые из них.

Задача триангуляции с минимальным весом

Пусть имеется n точек на евклидовой плоскости. Необходимо найти триангуляцию этих точек с минимальной суммарной длиной. Сегодня известно, что это задача является NP-полной ([15]).

Хоффман и Окамото [10] доказали, что задача является разрешимой с фиксированным параметром, считая параметром количество внутренних точек k. Временная сложность предложенного ими алгоритма составляет [math]\displaystyle{ O(6^k n^5 log \; n) }[/math]. Грантсон, Боргельт и Левкопулос [6] улучшили ее до [math]\displaystyle{ O(4^k k n^4) \; }[/math], а Спиллнер [18] – до [math]\displaystyle{ O(2^k k n^3) \; }[/math]. Еще один алгоритм с фиксированным параметром был предложен Грантсон, Боргельтом и Левкопулосом в работах [7, 8]. Наилучший известный на данный момент результат временной сложности получили Кнауэр и Спиллнер; он составляет [math]\displaystyle{ O(2^{c \sqrt{k} \; log \; k} k^{3/2} n^3) }[/math], где [math]\displaystyle{ c = (2 + \sqrt{2})/(\sqrt{3} - \sqrt{2}) \lt 11 }[/math].

Задача минимального выпуклого разбиения

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

Грантсон и Левкопулос [9] предложили алгоритм с временем выполнения [math]\displaystyle{ O(k^{6k - 5} 2^{16k} n) \; }[/math]. Позднее Спиллнер [19] улучшил эту временную сложность до [math]\displaystyle{ O(2^k k^3 n^3) \; }[/math].

Задача выпуклого разбиения с минимальным весом

Пусть имеется n точек на евклидовой плоскости. Необходимо найти выпуклое разбиение этих точек с минимальной суммарной длиной.

Грантсон [5] предложил алгоритм с временем выполнения [math]\displaystyle{ O(k^{6k - 5} 2^{16k} n) \; }[/math]. Позднее Спиллнер [19] улучшил эту временную сложность до [math]\displaystyle{ O(2^k k^3 n^3) \; }[/math]. ()

Задача построения остовного дерева без пересечений ребер

Пусть дан геометрический граф с n вершинами (т. е. граф на евклидовой плоскости, каждое ребро которого является отрезком прямой, соединяющим две точки). Необходимо определить, имеется ли у него остовное дерево, ребра которого не пересекаются. Дженсен и Вегингер [11] доказали, что эта задача является NP-полной.

Кнауэр и Спиллнер [12] предложили алгоритмы с временем выполнения [math]\displaystyle{ O(175^k k^2 n^3) \; }[/math] и [math]\displaystyle{ O(2^{33 \sqrt{k} \; log \; k} k^2 n^3) }[/math].

Метод, разработанный Кнауэром и Спиллнером [12], можно применить и к задаче коммивояжера. Согласно их результату, наилучшая известная на данный момент временная сложность алгоритма для TSP составляет [math]\displaystyle{ 2^{O(\sqrt{k} \; log \; k)} poly(n). }[/math]

Открытые вопросы

На данный момент не найдено нижней границы временной сложности. В частности, возможно ли при наличии разумных теоретико-сложностных предположений доказать невозможность существования алгоритма решения задачи коммивояжера с временем выполнения [math]\displaystyle{ 2^{O(\sqrt{k})} poly(n) }[/math]?

См. также

О задаче коммивояжера:

• Евклидова задача коммивояжера
• Гамильтоновы циклы в случайных графах пересечений
• Конкурс по реализации эвристик для задачи коммивояжера
• Метрическая задача коммивояжера

Об алгоритмах с фиксированными параметрами:

• Нахождение ближайшей подстроки
• Параметризованная задача выполнимости КНФ
• Кернелизация вершинного покрытия
• Вершинное покрытие и деревья поиска

О других вопросах:

• Триангуляция с минимальным весом

Литература

1. Delneko, V.G., Hoffmann, M., Okamoto, Y., Woeginger, G.J.:The traveling salesman problem with few inner points. Oper. Res. Lett. 31,106-110(2006)

2. Downey, R.G., Fellows, M.R.: Parameterized Complexity. In: Monographs in Computer Science. Springer, New York (1999)

3. Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science An EATCS Series. Springer, Berlin (2006)

4. Garey, M.R., Graham, R.L., Johnson, D.S.: Some NP-complete geometric problems. In: Proceedings of 8th Annual ACM Symposium on Theory of Computing (STOC '76), pp. 10-22. Association for Computing Machinery, New York (1976)

5. Grantson, M.: Fixed-parameter algorithms and other results for optimal partitions. Lecentiate Thesis, Department of Computer Science, Lund University (2004)

6. Grantson, M., Borgelt, C., Levcopoulos, C.: A fixed parameter algorithm for minimum weight triangulation: Analysis and experiments. Tech. Rep. 154, Department of Computer Science, Lund University (2005)

7. Grantson, M., Borgelt, C., Levcopoulos, C.: Minimum weight triangulation by cutting out triangles. In: Deng, X., Du, D.-Z. (eds.) Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC). Lecture Notes in Computer Science, vol. 3827, pp. 984-994. Springer, New York (2005)

8. Grantson, M., Borgelt, C., Levcopoulos, C.: Fixed parameter algorithms for the minimum weight triangulation problem. Tech. Rep. 158, Department of Computer Science, Lund University (2006)

9. Grantson, M., Levcopoulos, C.: A fixed parameter algorithm for the minimum number convex partition problem. In: Akiyama, J., Kano, M., Tan, X. (eds.) Proceedings of Japanese Conference on Discrete and Computational Geometry (JCDCG 2004). Lecture Notes in Computer Science, vol. 3742, pp. 83-94. Springer, New York (2005)

10. Hoffmann, M., Okamoto, Y.: The minimum weight triangulation problem with few inner points. Comput. Geom. Theory Appl. 34,149-158(2006)

11. Jansen, K., Woeginger, G.J.: The complexity of detecting crossing-free configurations in the plane. BIT 33, 580-595 (1993)

12. Knauer, C., Spillner, A.: Fixed-parameter algorithms for finding crossing-free spanning trees in geometric graphs. Tech. Rep. 06-07, Department of Computer Science, Friedrich-Schiller-Universitat Jena (2006)

13. Knauer, C., Spillner, A.: A fixed-parameter algorithm for the minimum weight triangulation problem based on small graph separators. In: Proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG). Lecture Notes in Computer Science, vol. 4271, pp. 49-57. Springer, New York (2006)

14. Lawler, E., Lenstra, J., Rinnooy Kan, A., Shmoys, D. (eds.): The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, Chichester (1985)

15. Mulzer, W., Rote, G.: Minimum Weight Triangulation is NP-hard. In: Proceedings of the 22nd Annual ACM Symposium on Computational Geometry (SoCG), Association for Computing Machinery, New York 2006, pp. 1-10

16. Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications, vol.31. Oxford University Press, Oxford (2006)

17. Papadimitriou, C.H.: The Euclidean travelling salesman problem is NP-complete. Theor. Comput. Sci. 4, 237-244 (1977)

18. Spillner, A.: A faster algorithm for the minimum weight triangulation problem with few inner points. In: Broersma, H.,Johnson, H., Szeider, S. (eds.) Proceedings of the 1st ACiD Work shop. Texts in Algorithmics, vol.4, pp. 135-146. King's College, London (2005)

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