Теория Задачи Инструменты Социум Интересно

Личный Кабинет

Войдите или зарегистрируйтесь
Лаборатория LMatrix
Лаборатория Lmatrix занимается оптимизацией транспортных задач. Сюда можно отнести задачи поиска кратчайшего пути в ориентированных графах, применимые как к масштабам города и страны, классическую задачу обхода (коммивояжера), задачи оптимизации доставки грузов, задачи трехмерной упаковки.
Новости проекта

31.05.2013 - Универсиада. Маршрут по России и Татарстану. Официально и математически.

Огонь Универсиады приближается к финишу в Казани, но прежде пройдет по 43 городам республики Татарстан. Все об маршрутах огня в нашем анонсе.

Тематические статьи

26.07.2013 - Монитор в автомобиле будет дублировать экран смартфона

Водители смогут увидеть точную копию экрана своего смартфона на мониторе бортовой системы автомобиля. О сотрудничестве в этом направлении договорились разработчик ПО для удаленного управления устройствами RealVNC и производитель процессоров Texas Instruments.

29.03.2013 - Facebook на днях анонсирует собственный смартфон на Android

На следующей неделе Facebook собирается представить собственный смартфон с кастомизированной версией Android, утверждают источники. Ранее глава компании Марк Цукерберг опровергал слухи о выпуске собственного смартфона.

29.03.2013 - Основатель Facebook М.Цукерберг создает политическую организацию

Основатель социальной сети Facebook Марк Цукерберг создает политическую организацию, которая займется такими вопросами, как реформа образования, иммиграция и научные исследования, передает Associated Press со ссылкой на анонимный источник.

Алгоритм Борувки

5 июля 2011 года в 15:59   Просмотров: 140464

Алгори́тм Бору́вки — это алгоритм нахождения минимального остовного дерева в графе.

Впервые был опубликован в 1926 году Отакаром Борувкой в качестве метода нахождения оптимальной электрической сети в Моравии. Несколько раз был переоткрыт, например Флореком, Перкалом и Соллином. Последний, кроме того, был единственным западным ученым из этого списка, и поэтому алгоритм часто называют алгоритмом Соллина, особенно в литературе по параллельным вычислениям.

Алгоритм

Работа алгоритма состоит из нескольких итераций, каждая из которых состоит в последовательном добавлении рёбер к остовному лесу графа, до тех пор, пока лес не превратится в дерево, то есть, лес, состоящий из одной компоненты связности.

В псевдокоде, алгоритм можно описать так:

  1. Изначально, пусть T — пустое множество ребер (представляющее собой остовный лес, в который каждая вершина входит в качестве отдельного дерева).
  2. Пока T не является деревом (что эквивалентно условию: пока число рёбер в T меньше, чем V − 1, где V — число вершин в графе):
    • Для каждой компоненты связности (то есть, дерева в остовном лесе) в подграфе с рёбрами T, найдём самое дешёвое ребро, связывающее эту компоненту с некоторой другой компонентой связности. (Предполагается, что веса рёбер различны, или как-то дополнительно упорядочены так, чтобы всегда можно было найти единственное ребро с минимальным весом).
    • Добавим все найденные рёбра в множество T.
  3. Полученное множество рёбер T является минимальным остовным деревом входного графа.

Сложность алгоритма

На каждой итерации число деревьев в остовном лесу уменьшается по крайней мере в два раза, поэтому всего алгоритм совершает не более O(logV) итераций. Каждая итерация может быть реализована со сложностью O(E), поэтому общее время работы алгоритмы составляет O(ElogV) времени (здесь V и E — число вершин и рёбер в графе, соответственно).

Однако для некоторых видов графов, в частности, планарных, оно может быть уменьшено до O(E).[1] Существует также рандомизированный алгоритм построения минимального остовного дерева, основанный на алгоритме Борувки, работающий в среднем за линейное время.

Похожие новости

Нет похожих новостей.

Оставить комментарий

Пожалуйста, введите символы, показанные на рисунке.

Примеры решений задачи коммивояжера (TSP)
design by lmatrix
О проекте | Написать письмо | Ссылки | Литература | Карта сайта