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