Неориентированный граф в объединение путей с минимальной стоимостью

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

С какой проблемой я имею дело, возможные алгоритмы решения? Я предполагаю, что это должен быть вариант минимального остовного дерева (что означает использование узла пересечения в качестве начальной точки для путей вместо конечной точки)


path graph algorithm tree minimum
person DelicateBehemoth    schedule 14.12.2012    source источник
comment
Ну, я тебя не понял. Непонятно, что на самом деле дано в этой задаче.   -  person dreamzor    schedule 14.12.2012
comment
То, что дано, является графом узлов. Требование состоит в том, чтобы пройти все узлы, чтобы общая стоимость прохождения была минимальной. Прохождение осуществляется начальными путями из произвольных узлов с периферии графа, достигающими одного определенного (заданного) узла в центре графа. Узлы можно посещать более одного раза, поэтому путь может идти на посещение узла, а затем возвращаться к ранее пройденному при продолжении (если это удовлетворяет условию минимальной стоимости).   -  person DelicateBehemoth    schedule 15.12.2012
comment
Альтернативным решением было бы начать наоборот - вместо того, чтобы добраться от начальных узлов до центрального узла, начать с центрального узла и распространить маршруты на периферийные узлы. Таким образом, почему я упомянул связующее дерево, но тогда ветви должны быть маршрутами.   -  person DelicateBehemoth    schedule 15.12.2012

Ответы (2)


arrow_upward
0
arrow_downward

Это называется проблемой гамильтоновой цепи минимальной стоимости.

Здесь вы можете узнать больше об этом.

person dreamzor    schedule 14.12.2012
comment
Спасибо за ответ, но структура не является схемой. Он должен иметь звездообразную форму, встречающуюся в одном заранее определенном узле, с неизвестным количеством гамильтоновых путей. - person DelicateBehemoth; 14.12.2012

arrow_upward
0
arrow_downward

Это дерево, которое вы ищете, и проблема заключается в минимальном связующем дереве - MST: построение дерева, которое охватывает все узлы в графе, и стоимость ребер в дереве минимально возможна. Это полиномиальная задача. У Прима и Крускала есть хорошо известные алгоритмы решения. См. http://en.wikipedia.org/wiki/Kruskal's_algorithm для алгоритма Крускала.

Примечание: проблема является NP-полной, когда предполагается, что дерево охватывает заданное правильное подмножество узлов, а не все узлы в графе. На этот раз она известна как задача Штейнера о минимальном дереве.

person ashley    schedule 15.12.2012
comment
Спасибо за ответ, но на самом деле это, вероятно, должен быть вариант MST, который дает дерево с несколькими путями, каждый из которых представляет собой всего одну ветвь/путь от центрального узла к периферийному узлу, передавая узлы по пути, и не охватывающий несколько ветвей. - person DelicateBehemoth; 15.12.2012
comment
Возможно, вам следует более четко сформулировать свою проблему. для меня это все еще выглядит как MST или дерево кратчайшего пути. - person ashley; 16.12.2012
comment
Ну, как я уже сказал, это вариант MST, с той разницей, что это направленные пути на неориентированном графе (он начинается с периферийного узла и ПОСЕЩАЕТ узлы в последовательности на пути к ДАННОМУ узлу) с возможностью для узел/ребро, которое нужно посетить больше раз. - person DelicateBehemoth; 16.12.2012
comment
Например, чтобы сделать это более ясным, мы можем рассматривать это как задачу заставить несколько автомобилей проехать через все города в регионе и все добраться до центрального узла, не важно, сколько автомобилей, а просто сделать общее количество настолько дешевым, насколько это возможно. возможно. Если бы у нас был перегон, то несколько машин начали бы поездку, но встретились бы в точке и повторили бы часть маршрутов при подъезде к центральному узлу, что увеличило бы общую стоимость. Это не учитывается в классической постановке задачи MST. - person DelicateBehemoth; 16.12.2012