задачу решить невозможно. Только за O(N!). А это значит, что даже для ста точек компьютер не успеет рассчитать маршрут (за реальное время, конечно же).5. Приближенные решения задачи Коммивояжера.
Нужно обойти все точки по самому короткому маршруту, не попадая в каждую дважды.
Это НП-полная задача, т.е. нет полиноминального алгоритма для ее решения. (В теории алгоритмов NP-полные задачи — это класс задач, лежащих в классе NP (то есть для которых пока не найдено быстрых алгоритмов решения, но проверка того, является ли данное решение правильным, проходит быстро), к которым сводятся все задачи класса NP. Это означает, что если найдут быстрый алгоритм для решения любой из NP-полных задач, любая задача из класса NP может быть решена быстро.) То есть за O(N^2) при задачу решить невозможно. Только за O(N!). А это значит, что даже для ста точек компьютер не успеет рассчитать маршрут (за реальное время, конечно же).
Значит нужно решить приближенно.
Метод №1. Можно запустить этот N!, а потом тормознуть когда-нибудь и выбрать лучший из найденных маршрутов. Проблема в том, что мы не узнаем насколько найденный хуже идеала.
Метод минимального остовного дерева. 12 вопрос.
Задача: есть n точек; необходимо построить сеть связей кратчайшей суммарной длины.
а) Найдем точку, ближайшую к начальной. Затем ближайшую к одной из найденных ранее, и так далее. Время решения - O(n).
Утверждение: если есть два подмножества S1 и S2, то минимальный отрезок, соединяющий их, обязательно принадлежит Евклидову остовому дереву.
Доказательство: если есть другое такое ребро e, то заменяем его на "не большее", и получаем таким образом новое остовое дерево.
б) Имеем n деревьев по одной точке, выстроим их в очередь. Берем первое дерево и ищем ближайшее к нему, объединяем их. Полученное новое дерево ставим в конец очереди (старые вычеркиваем). Повторяем алгоритм, пока в очереди не останется одно дерево. Время решения O(n^3).
в) Утверждение: кратчайший отрезок QP (Q принадлежит S2, P принадлежит S1) является ребром двойственного графа, то есть соединяет точки смежных областей диаграммы Вороного.
Доказательство (от противного):
М – середина QP
A не принадлежит QM
A <> M
Если А принадлежит PM, то существует точка R смежная P.
RQ < PQ -> противоречие, так как PQ – кратчайший отрезок.
R не принадлежит S1, R не принадлежит S2=> точка Q обязательно лежит в области смежной области, содержащей P.
Усовершенствуем алгоритм б).
При поиске просматриваем только смежные области (O(n) штук). Каждое из ребер двойственного графа просматривается К раз, так как на каждом шаге все ребра не рассматриваются (то, что внутри готовой области рассматривать не нужно).
Введем понятие этап.
Всем исходным деревьям (каждое из одной точки) присвоим номер этапа 1. Этап результата объединения равен минимуму из этапов объединяемых деревьев плюс один. Этап "один" закончится, когда пройдем все одиночные точки (O(n)). При каждом шаге рассматриваем только смежные точке ребра => каждое ребро рассматривается =< 2 раза.
Дерево каждого этапа не короче номера этапа.
Количество этапов logn.
Можно построить маршрут комевояжора, который длиннее оптимального не более чем в два раза.
Пусть есть множество из 2n точек, тогда разбиение этого множества на пары такое, что суммарная длина отрезков, соединяющих точки в парах, была бы минимальной, называется минимальным евклидовым парасочетанием.
Минимальное евклидово парасочетание не длиннее 0,5 оптимального маршрута комевояжора.
Помеченные точками ребра (через одно ребро из маршрута комевояжора) и не помеченные ребра образуют два парасочетания S1 и S2, каждое из которых не меньше минимального. Следовательно, S1 + S2 >= 2Smin.
Построим минимальное остовое дерево и минимальное евклидово парасочетание. Их суммарная длина не более 1,5 минимального маршрута комевояжора.
Для вершин с нечетными степенями остового дерева (их количество всегда четно) построим минимальное евклидово парасочетание за O(n^3). Его длина <= 0,5 оптимального маршрута комевояжора.
Строим эйлеров цикл. Если в процессе построения вершина встречается второй раз, то пропускаем ее и идем дальше (рассматриваем следующую вершину). Полученный маршрут не длиннее исходного, то есть <= 1,5 оптимального.
Оценка времени решения O(n^3) – дерево O(nlogn), парасочетания O(n3), обход O(n).
