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).
