Реальные приложения, в которых используется структура данных связующего дерева
Кто-нибудь из вас знает какие-либо реальные приложения, в которых используется структура данных связующего дерева?
1 ответ
В сети мы часто используем алгоритм минимального связующего дерева. Таким образом, проблема заключается в том, что, как указано здесь, с учетом графа со взвешенными ребрами найти дерево ребер с минимальным общим весом, которое удовлетворяет этим трем свойствам: связное, ациклическое и состоящее из |V| - 1 ребро. (Фактически, любые два из трех условий подразумевают третье условие.)
В качестве примера,
Например, если у вас большая локальная сеть с большим количеством коммутаторов, может быть полезно найти минимальное связующее дерево, чтобы по сети передавалось только минимальное количество пакетов, а несколько копий одного и того же пакета не прибывают по разным путям (помните, что любые два узла связаны только одним путем в связующем дереве).
Другие реальные проблемы включают в себя прокладку электрических сетей, как сообщается, первоначальную мотивацию для алгоритма Борувки, одного из первых алгоритмов поиска минимальных остовных деревьев. Не должно быть удивительно, что было бы лучше найти минимальное остовное дерево, чем просто любое старое остовное дерево; если одно связующее дерево в сети будет использовать самый перегруженный, самый медленный путь, это, вероятно, не будет идеальным!
Есть много других приложений, кроме компьютерных сетей, я перечислил ссылки ниже:
Проектирование сети:- телефонная, электрическая, гидравлическая, телевизионный кабель, компьютер, дорога. Стандартное приложение для такой проблемы, как проектирование телефонной сети. У вас есть бизнес с несколькими офисами; Вы хотите арендовать телефонные линии, чтобы соединить их друг с другом; и телефонная компания взимает разные суммы денег, чтобы соединить разные пары городов. Вам нужен набор линий, соединяющий все ваши офисы с минимальной общей стоимостью. Это должно быть связующее дерево, так как если сеть не является деревом, вы всегда можете удалить некоторые ребра и сэкономить деньги.
Алгоритмы аппроксимации для NP-сложных задач:- задача коммивояжера, дерево Штейнера Менее очевидное применение состоит в том, что минимальное связующее дерево можно использовать для приближенного решения задачи коммивояжера. Удобный формальный способ определения этой проблемы - найти кратчайший путь, который посещает каждую точку хотя бы один раз.
Обратите внимание, что если у вас есть путь, посещающий все точки ровно один раз, это особый вид дерева. Например, в приведенном выше примере двенадцать из шестнадцати остовных деревьев на самом деле являются путями. Если у вас есть путь, посещающий некоторые вершины более одного раза, вы всегда можете опустить некоторые ребра, чтобы получить дерево. Таким образом, в целом вес MST меньше веса TSP, потому что это минимизация по сравнению со строго большим набором.
С другой стороны, если вы рисуете трассировку пути вокруг минимального остовного дерева, вы дважды прослеживаете каждое ребро и посещаете все точки, так что вес TSP меньше чем вдвое вес MST. Поэтому этот тур в два раза лучше.
Непрямые приложения: - максимальное число узких мест - коды LDPC для исправления ошибок - регистрация изображений с помощью энтропии Реньи - изучение характерных особенностей для проверки лица в реальном времени - сокращение объема хранения данных при секвенировании аминокислот в белке - модельное расположение взаимодействий частиц в турбулентных потоках жидкости - протокол автоматической настройки для моста Ethernet, чтобы избежать циклов в сети
Кластерный анализ: проблема кластеризации k может рассматриваться как нахождение MST и удаление k-1 самых дорогих ребер.
Вы можете прочитать подробности здесь, и здесь, и для демо-проверки здесь, пожалуйста.