4551
правка
Евклидова задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
Евклидова задача коммивояжера (посмотреть исходный код)
Версия от 15:04, 23 января 2014
, 23 января 2014→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 74: | Строка 74: | ||
''Евклидова задача нахождения минимального дерева Штейнера''. Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R} ^d</math> найти путь с минимальной стоимостью сети, соединяющий все точки S (стоимость сети равна сумме длин дуг, ее определяющих). | ''Евклидова задача нахождения минимального дерева Штейнера''. Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R} ^d</math> найти путь с минимальной стоимостью сети, соединяющий все точки S (стоимость сети равна сумме длин дуг, ее определяющих). | ||
'''Теорема 7 ([1, 15]). Для | '''Теорема 7 ([1, 15]). Для любого константного значения d евклидова задача нахождения минимального дерева Штейнера на <math>\mathbb{R} ^d</math> имеет PTAS.''' | ||
''Евклидова задача нахождения k медиан''. Для заданного множества 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]). Для | '''Теорема 8 ([5]). Для любого константного значения d евклидова задача нахождения k медиан на <math>\mathbb{R} ^d</math> имеет PTAS.''' | ||
| Строка 87: | Строка 87: | ||
''Евклидова задача нахождения минимального дерева Штейнера с k точками''. Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R} ^d</math> и целого числа k найти кратчайшее дерево, содержащее не менее k точек множества S. | ''Евклидова задача нахождения минимального дерева Штейнера с k точками''. Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R} ^d</math> и целого числа k найти кратчайшее дерево, содержащее не менее k точек множества S. | ||
'''Теорема 9 ([1]). Для | '''Теорема 9 ([1]). Для любого константного значения d евклидовы задачи коммивояжера с k точками и нахождения минимального дерева Штейнера с k точками на <math>\mathbb{R} ^d</math> имеют PTAS.''' | ||
''Евклидова задача нахождения k-связного подграфа минимальной стоимости''. Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R} ^d</math> и целого числа k найти подграф полного графа S минимальной стоимости, являющийся k-связным. | ''Евклидова задача нахождения k-связного подграфа минимальной стоимости''. Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R} ^d</math> и целого числа k найти подграф полного графа S минимальной стоимости, являющийся k-связным. | ||
'''Теорема 10 ([9]). Для | '''Теорема 10 ([9]). Для любого константного значения d и константного k, евклидова задача нахождения k-связного подграфа минимальной стоимости на <math>\mathbb{R} ^d</math> имеет PTAS.''' | ||