Застревание при решении задачи минимального спанивающего дерева

Я уменьшил свою проблему до нахождения минимального связующего дерева на графике. Но я хочу иметь еще одно ограничение: общая степень для каждой вершины не должна превышать определенный постоянный коэффициент. Как смоделировать мою проблему? Является ли MST неправильным путем? Знаете ли вы какие-либо алгоритмы, которые мне помогут?Застревание при решении задачи минимального спанивающего дерева

Еще одна проблема: мой график имеет повторяющиеся веса ребер, поэтому есть способ подсчитать количество уникальных MST? Существуют ли алгоритмы, которые это делают?

Thank you.

Редактировать: По степени, я имею в виду общее количество ребер, соединяющих вершину. По удвоенному весу края я имею в виду, что два края имеют одинаковый вес.

источник

2009-05-20 unj2

Вы можете просто применить алгоритм kruskal, удалив из списка узлы, которые связаны с узлами с максимальной суммарной степенью, но я не знаю, определяет ли это оптимальное решение (и если оно определяет решение вообще!) – akappa

В противном случае вы можете применить полный алгоритм kruskal, а затем использовать некоторые методы локального поиска, чтобы получить действительное остовное дерево. – akappa

.? В этой статье показано, как найти в полиномиальное время , Остовное дерево максимальной степени г + 1, что по крайней мере так же хорошо, как любого остов максимальной степени д: http://www.andrew.cmu.edu/user/mohits/mbdst.pdf

// Edit Оригинальный ссылка в настоящее время неактивно, попробуйте http://research.microsoft.com/pubs/80193/mbdst.pdf вместо этого.

источник

2009-06-09 04:33:03 Dave

Havent прочитал все, но выглядит очень полезным. Благодарю. – unj2

Ну, это легко доказать, что не может быть решением: просто сделать свой вклад граф дерева, который имеет вершину со степенью выше, чем ваш предел ..

источник

2009-05-20 22:43:42

Что делать, если я ставлю коэффициент нагрузки выше общего ограничения веса? То есть я готов согласиться на второй минимальный или даже третий минимум. Но это влечет за собой эвристику, которая может создать больше проблем. Например, как вы решаете, какой край заменить? У Бога есть другой способ решить эту проблему? – unj2

Я не знаю; вы не сказали нам, в чем заключается ваша проблема :-) Но если вы хотите иметь остовное дерево со всеми вершинами, имеющими deg <= n ... ну, я могу придумать график, где любое связующее дерево (минимальное или другое) включает по крайней мере, одна вершина со степенью n + 1. Эвристика вам не поможет в этой ситуации. –

Garey Джонсон эта проблема сводится к Хэмильтон: (Таким образом, это один помог Аппроксимируя первый:. http://caislab.icu.ac.kr/Lecture/data/2003/spring/ice514/project/m03.ppt Однако лучше рабочие модели оценены ...

Counting:. http://mathworld.wolfram.com/SpanningTree.html в соответствии с этим, Mathematica имеет функцию Любые предложения в этой одной

источник

2009-05-21 14:55:02 unj2

Хорошо, если вы вникнете в теорему о матричном дереве (ссылка на mathworld), возможно, вы можете найти способ систематически превратить одно связующее дерево в другое. Если вы можете это сделать, вы можете прокручивать окулярные деревья до тех пор, пока не найдете тот, который подходит вашим целям. Тем не менее, все это дикая догадка; нет гарантий :-) –

Застревание при решении задачи минимального спанивающего дерева

ответ

Смежные вопросы