4551
правка
Задача коммивояжера с несколькими внутренними точками: различия между версиями
Перейти к навигации
Перейти к поиску
м
Задача коммивояжера с несколькими внутренними точками (посмотреть исходный код)
Версия от 11:00, 25 мая 2018
, 25 мая 2018→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Применение) |
||
| Строка 42: | Строка 42: | ||
Пусть имеется n точек на евклидовой плоскости. Необходимо найти разбиение выпуклой оболочки этих точек на минимальное количество выпуклых областей, содержащих некоторые точки в качестве вершин. | Пусть имеется n точек на евклидовой плоскости. Необходимо найти разбиение выпуклой оболочки этих точек на минимальное количество выпуклых областей, содержащих некоторые точки в качестве вершин. | ||
Грантсон и Левкопулос [ ] предложили алгоритм с временем выполнения O( | Грантсон и Левкопулос [9] предложили алгоритм с временем выполнения <math>O(k^{6k - 5} 2^{16k} n) \;</math>. Позднее Спиллнер [19] улучшил эту временную сложность до <math>O(2^k k^3 n^3) \;</math>. | ||
| Строка 50: | Строка 50: | ||
Грантсон | Грантсон [5] предложил алгоритм с временем выполнения <math>O(k^{6k - 5} 2^{16k} n) \;</math>. Позднее Спиллнер [19] улучшил эту временную сложность до <math>O(2^k k^3 n^3) \;</math>. () | ||
'''Задача построения остовного дерева без пересечений ребер''' | '''Задача построения остовного дерева без пересечений ребер''' | ||
Пусть дан геометрический граф с n вершинами (т.е. граф на евклидовой плоскости, каждое ребро которого является отрезком прямой, соединяющим две точки). Необходимо определить, имеется ли у него остовное дерево, ребра которого не пересекаются. Дженсен и Вегингер [11] доказали, что эта задача является NP-полной | Пусть дан геометрический граф с n вершинами (т. е. граф на евклидовой плоскости, каждое ребро которого является отрезком прямой, соединяющим две точки). Необходимо определить, имеется ли у него [[остовное дерево]], ребра которого не пересекаются. Дженсен и Вегингер [11] доказали, что эта задача является NP-полной. | ||
Кнауэр и Спиллнер [12] предложили алгоритмы с временем выполнения <math>O(175^k k^2 n^3) \;</math> и <math>O(2^{33 \sqrt{k} \; log \; k} k^2 n^3)</math>. | |||
Метод, разработанный Кнауэром и Спиллнером [ ], можно применить и к задаче коммивояжера. Согласно их результату, наилучшая известная на данный момент временная сложность алгоритма для TSP составляет | |||
Метод, разработанный Кнауэром и Спиллнером [12], можно применить и к задаче коммивояжера. Согласно их результату, наилучшая известная на данный момент временная сложность алгоритма для TSP составляет | |||
== Открытые вопросы == | == Открытые вопросы == | ||