Разница между гамильтоновым путем и ST - PullRequest
11 голосов
/ 23 июля 2011

Я читал алгоритмы для нахождения минимального остовного дерева (в случае взвешенных графов) и для определения, имеет ли граф гамильтонову путь (который зависит от наличия гамильтонова цикла).Я все испортил.Так в чем же разница между гамильтоновым путем и остовным деревом?Оба охватывают все вершины графа.Хотя у нас могут быть эффективные алгоритмы для поиска остовного дерева (возможно, минимального остовного дерева), почему у нас не может быть алгоритмов для нахождения гамильтоновой схемы ??Мы можем продолжать добавлять и удалять по одному ребру за раз, пока не достигнем цикла, и, возможно, мы могли бы найти гамильтонов цикл ...

Ответы [ 4 ]

7 голосов
/ 23 июля 2011

Две проблемы совершенно разные. Представьте, что минимальное связующее дерево - это проблема соединения мест, где вам нужно заплатить только один раз, чтобы построить дорогу, но вы можете использовать ее столько раз, сколько захотите. Легко придумать самую дешевую конфигурацию дорог (например, по алгоритму Крускала), которая позволяет вам путешествовать из любого места в любое другое.

Гамильтонов цикл, с другой стороны, требует, чтобы вы минимизировали фактическое расстояние перемещения, то есть каждое перемещение из одного места в другое считается. (Он также просит вас никогда не посещать место дважды, но это незначительная деталь.) Эта проблема принципиально нелокальна, в том смысле, что вы не можете определить, правильно ли вы поступаете, просто локально исследуя варианты следующий шаг. Для сравнения, алгоритм жадного MST гарантированно выберет правильное следующее ребро для добавления к дереву на каждом шаге.

Кстати, никто не говорит, что «у нас не может быть эффективных алгоритмов для HP». Возможно, мы просто еще не нашли: -)

3 голосов
/ 03 марта 2014

Обе проблемы хотят соединить все вершины друг с другом.

Для минимального остовного дерева вам все равно, к какой вершине подключена вершина a , поэтому вы можете просто подключить a до ближайшей вершины.Поскольку вы соединяете только те вершины, которые еще не соединены, это дает дерево, и у вас есть свой алгоритм.

Однако для гамильтонова пути вам важно, к какой вершине (например, b )вы соединяете вершину a , поскольку вы не можете снова использовать b (иначе это уже не путь).Таким образом, чтобы определить, к какой вершине вы должны подключиться a , вы должны попробовать все возможности и посмотреть, что произойдет.То есть никто еще не нашел эффективный путь, который, конечно, не означает автоматически, что его нет.

2 голосов
/ 17 сентября 2014

В гамильтоновом пути все вершины, кроме источника и приемника, имеют степень 2. Это не обязательно имеет место с MST (или ST, если хотите).

2 голосов
/ 23 июля 2011

Гамильтонова траектория и, в особенности, минимальный гамильтонов цикл Быстрое решение выглядит как кривая Гильберта, особый вид кривой заполнения пространства также используется для уменьшения сложности пространства и для эффективной адресации. Mst - это то же самое, что соединить все вершины вместе с самыми дешевыми затратами на соединение (т. Е. Путешествовать) независимо от порядка или пересечения. Полезно решить такую ​​проблему, как поиск дорог, поиск водоканала, поиск интернет-кабеля.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...