4430
правок
Евклидова задача коммивояжера: различия между версиями
Материал из WEGA
Евклидова задача коммивояжера (посмотреть исходный код)
Версия от 14:40, 23 января 2014
, 23 января 2014→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 70: | Строка 70: | ||
Техники, разработанные Аророй [1] и Митчеллом [13], нашли множество вариантов применения в разработке схем аппроксимации с полиномиальным временем исполнения для задач геометрической оптимизации. | Техники, разработанные Аророй [1] и Митчеллом [13], нашли множество вариантов применения в разработке схем аппроксимации с полиномиальным временем исполнения для задач геометрической оптимизации. | ||
Для заданного множества S из n точек в евклидовом пространстве | ''Евклидова задача нахождения минимального дерева Штейнера''. Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R} ^d</math> найти путь минимальной стоимости, соединяющий все точки S (стоимость сети равна сумме длин дуг, ее определяющих). | ||
'''Теорема 7 ([1, 15]). Для каждого константного значения d евклидова задача нахождения минимального дерева Штейнера на | '''Теорема 7 ([1, 15]). Для каждого константного значения d евклидова задача нахождения минимального дерева Штейнера на <math>\mathbb{R} ^d</math> имеет PTAS.''' | ||
''Евклидова задача нахождения k медиан'' | ''Евклидова задача нахождения k медиан'' | ||
Для заданного множества S из n точек в евклидовом пространстве | Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R} ^d</math> и целого числа k найти k медиан между точками S, таких, что сумма расстояний от каждой точки S до ближайшей к ней медианы минимальна. | ||
'''Теорема 8 ([5]). Для каждого константного значения d евклидова задача нахождения k медиан на | '''Теорема 8 ([5]). Для каждого константного значения d евклидова задача нахождения k медиан на <math>\mathbb{R} ^d</math> имеет PTAS.''' | ||
''Евклидова задача коммивояжера с k точками'' | ''Евклидова задача коммивояжера с k точками'' | ||
Для заданного множества S из n точек в евклидовом пространстве | Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R} ^d</math> и целого числа k найти путь минимальной длины, проходящий не менее k точек множества S. | ||
''Евклидова задача нахождения минимального дерева Штейнера с k точками'' | ''Евклидова задача нахождения минимального дерева Штейнера с k точками'' | ||
Для заданного множества S из n точек в евклидовом пространстве | Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R} ^d</math> и целого числа k найти кратчайшее дерево, содержащее не менее k точек множества S. | ||
'''Теорема 9 ([1]). Для каждого константного значения d евклидовы задачи коммивояжера с k точками и нахождения минимального дерева Штейнера с k точками на | '''Теорема 9 ([1]). Для каждого константного значения d евклидовы задачи коммивояжера с k точками и нахождения минимального дерева Штейнера с k точками на <math>\mathbb{R} ^d</math> имеют PTAS.''' | ||
''Евклидова задача нахождения k-связного подграфа минимальной стоимости'' | ''Евклидова задача нахождения k-связного подграфа минимальной стоимости'' | ||
Для заданного множества S из n точек в евклидовом пространстве | Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R} ^d</math> и целого числа k найти подграф полного графа S минимальной стоимости, являющийся k-связным. | ||
'''Теорема 10 ([9]). Для каждого константного значения d и константного k, евклидова задача нахождения k-связного подграфа минимальной стоимости на | '''Теорема 10 ([9]). Для каждого константного значения d и константного k, евклидова задача нахождения k-связного подграфа минимальной стоимости на <math>\mathbb{R} ^d</math> имеет PTAS.''' | ||
Техники, разработанные Аророй [1] и Митчеллом [13], также привели к созданию квазиполиномиальных схем аппроксимации – то есть алгоритмов с временем исполнения n°^°&n\. К примеру, Арора и Карокостас [4] создали схему аппроксимации с квазиполиномиальным временем исполнения для решения евклидовой задачи нахождения минимального времени ожидания; Реми и Стегер [16] предложили схему аппроксимации с полиномиальным временем исполнения для решения задачи триангуляции с минимальным весом. | Техники, разработанные Аророй [1] и Митчеллом [13], также привели к созданию квазиполиномиальных схем аппроксимации – то есть алгоритмов с временем исполнения n°^°&n\. К примеру, Арора и Карокостас [4] создали схему аппроксимации с квазиполиномиальным временем исполнения для решения евклидовой задачи нахождения минимального времени ожидания; Реми и Стегер [16] предложили схему аппроксимации с полиномиальным временем исполнения для решения задачи триангуляции с минимальным весом. | ||
Более подробные обзоры можно найти в [2] и [10]. | Более подробные обзоры можно найти в [2] и [10]. | ||
== Расширение на планарные графы == | == Расширение на планарные графы == | ||
