Рубрики

Приложения задачи минимального остовного дерева

Задача минимального связующего дерева (MST): для заданного связного графа G с положительными весами ребер найдите набор ребер с минимальным весом, который соединяет все вершины.

MST является фундаментальной проблемой для различных приложений.

Проектирование сети.
— телефон, электрика, гидравлика, ТВ кабель, компьютер, дорога
Стандартное приложение для такой проблемы, как дизайн телефонной сети. У вас есть бизнес с несколькими офисами; Вы хотите арендовать телефонные линии, чтобы соединить их друг с другом; и телефонная компания взимает разные суммы денег, чтобы соединить разные пары городов. Вам нужен набор линий, соединяющий все ваши офисы с минимальной общей стоимостью. Это должно быть связующее дерево, так как если сеть не является деревом, вы всегда можете удалить некоторые ребра и сэкономить деньги.

Аппроксимационные алгоритмы для NP-сложных задач.
проблема коммивояжера , дерево Штейнера
Менее очевидное применение состоит в том, что минимальное связующее дерево может использоваться для приблизительного решения задачи коммивояжера. Удобный формальный способ определения этой проблемы — найти кратчайший путь, который посещает каждую точку хотя бы один раз.

Обратите внимание, что если у вас есть путь, посещающий все точки ровно один раз, это особый вид дерева. Например, в приведенном выше примере двенадцать из шестнадцати остовных деревьев фактически являются путями. Если у вас есть путь, посещающий некоторые вершины более одного раза, вы всегда можете опустить некоторые ребра, чтобы получить дерево. Таким образом, в целом вес MST меньше веса TSP, потому что это минимизация по сравнению со строго большим набором.

С другой стороны, если вы рисуете трассировку пути вокруг минимального остовного дерева, вы дважды прослеживаете каждое ребро и посещаете все точки, поэтому вес TSP составляет менее чем вдвое вес MST. Поэтому этот тур в два раза больше оптимального.

Косвенные приложения.
— максимальное количество узких мест
— коды LDPC для исправления ошибок
— регистрация изображений с энтропией Рени
— изучение характерных особенностей для проверки лица в реальном времени
— сокращение хранения данных при секвенировании аминокислот в белке
— модельная локальность взаимодействия частиц в турбулентных потоках жидкости
— протокол автоматической настройки для моста Ethernet, чтобы избежать циклов в сети

Кластерный анализ
Проблема кластеризации k может рассматриваться как поиск MST и удаление k-1 наиболее
дорогие края.

Источники:
http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/mst.pdf
http://www.ics.uci.edu/~eppstein/161/960206.html

Рекомендуемые посты:

Приложения задачи минимального остовного дерева

0.00 (0%) 0 votes