Графы: неполное минимальное остовное дерево

Max

Вычисление длины пути между всеми парами вершин графа производится за время пропорциональное кубу от числа вершин при помощи алгоритма Флойда. Так же при этом можно построить матрицу по которой можно востановить путь между любой парой вершин, за время пропорциональное числу вершин в нём.

 

Max

Как раз определить длину всех путей несложно. Как мне кажется, проблема в том, что толку от этого мало, т.к. пути могут иметь общие рёбра, поэтому сумма весов рёбер искомого дерева не есть сумма длин путей. Ответ на вопрос, нужно ли включать некоторое ребро в остов, зависит от того, какие рёбра мы уже включили. Думаю, от перебора никуда не деться (после "обработки" некоторых частных случаев).

 

Stiver, why do you keeping silent? Is it working or not?
p.s. beer is rulezz!

 

Max

В смысле твоя последняя программа? Да нет конечно Например:

nodes=6

0-1,3

1-2,3

2-3,3

3-4,3

0-5,1

2-5,4

4-5,4

M=0,2,4

Правильный ответ: {(0-5),(5-2),(5-4)} Твоя программа выдает {(0-1),(1-2),(2-3),(3-4)}. То, чем ты занимаешься, называется подгонять решение под ответ..

 

Max

Смотри мой пост выше. Он специально заточен на то, чтобы правельным ответом не было остевое дерево для G и минемальный путь из вершины 1-2,5 не был верным решением. Как и предыдущий атач твоя прога выдает.

nodes=6



prime tree



M nodes=

M ribs:



Прислушайся Артема, он говорит дельные вещи.Да и не только он.

Artem

От "перебора" не деться, но вопрос как "переберать" только нужное. А это уже зависет от того, как хранить данные.

 

Pavia

У тебя граф в примере несвязный, узел 0 ни с чем не соединен. Противоречие между nodes=6 и нумерацией от 1? Потому и ответа нет, я так понимаю. Если привести его к виду:

nodes=5

0-1,5

0-2,4

0-4,3

1-2,3

2-4,3

4-3,3

M=0,1,3

ответ будет, даже частично верный, но несвязный. Отличный пример, когда



Max

не работает, т.к. можно удалить только часть пути.

 

Stiver, а такая идея тебе не приходила: раз задача NP-полная, то известно сведение задачи к задаче о гамильтоновом цикле наименьшей стоимости (я прав?). А последняя задача решается более эффективно, чем простой перебор, с помощью сведения задачи к задаче о назначениях (см. http://rain.ifmo.ru/cat/view.php/vis/graph-circuits-cuts/salesman-assignments-2002/algorithm).

 

Объясните пожалуйста что именно требуется, то есть нужен исходник или же бинарник для решения общей штейнеровской проблемы. Если первое, то могу предложить свой код, кроссплатформенный, но там одно "ядро" более чем на метр (притом что это без ЛП). Мой код решает графы небольшой сложности, примерно до 2000-3000 ребер. Если нужна более мощная программа, могу указать где взять самый чемпионский exe но только под виндовз, это работа Польцина-Вахдати. Входной формат - везде STP, см http://elib.zib.de/steinlib/format.php. В открытом доступе есть только исходник Закариассена 98 года, но он для евклидовой проблемы, там генератор FST-шек и солвер на ЛП. Универсальный код Польцина-Вахдати вряд ли будет выставлен, отчасти потому что он использует платную библиотеку LEDA его руководителя проф. Мельхорна из Саарского юнивера. Следующий по производительности код принадлежит Учоа и Арагону из университета Рио, он старше (конец 90х) и тоже не опубликован. Коммерческих пакетов решающих эту задачу увы не существует в природе, хотя на практике она очень важна в биологии, в дизайне сетей, VLSI.


Если нужно приближенное решение есть эвристики со средним зазором 1-3% по отношению к оптимуму, но метод в худшем случае гарантирует примерно 1.5x от оптимума - вы вероятно знаете что "приблизить" штейнеровскую проблему полиномиально нельзя.

Литературы масса, в основном статьи. Рекомендую T.Polzin 2003 The Steiner Problem in Networks, это диссер.

 

я встречал в литературе пяток разных красивых сведений штейнеровской проблемы, но прямые методы на практике эффективнее чем скажем такое сведение к TSP со скармливанием Конкорду.

 

Одна из наиболее эффективных эвристик такова. Это примподобный и дейкстроподобный обход, то есть в ширину с очередью, критерием будет минимальное расстояние тестируемой вершины до уже построенного фрагмента дерева. Дан связный неориентированный граф. Начинаем с произвольного терминала. Как только видим новое ребро просто обновляем расстояние до вершины-конца ребра, индексируя еще и наилучшего "предшественника". А когда встречаем новый терминал то добавляем к графу весь сохраненный путь к этому терминалу, ЗАНОВО ВСТАВЛЯЯ В ОЧЕРЕДЬ ВСЕ НЕТЕРМИНАЛЫ НА ЭТОМ ПУТИ (УЖЕ С НУЛЕВЫМ РАССТОЯНИЕМ) - иначе получится что мы измеряем расстояние от начальной вершины а не от всего строящегося графа. Этот трюк крайне эффективен и дает нам время e + v * log v (конечно если очередь не уступает в эффективности Фибоначчиевой). Метод желательно использовать несколько раз подряд, то есть выбирать новый начальный терминал и строить новое дерево, потом выбрать наилучшее. Скажем псевдослучайным образом взять 50-100 терминалов и повторять обход. Впервые опубликовали Арагон и Вернек где-то в начале 2000х - почему-то раньше никто из решателей Штейнера до такого простого но эффективного трюка не доходил. На практике он гораздо лучше чем все эвристики основанные на метрическом МСТ Мельхорна.

 

Valery
LEDA разве платная? Или бесплатна только её часть, которая лежит у меня на винте?

 

когда я последний раз проверял - была платная