Я читал алгоритмы поиска минимального остовного дерева (в случае взвешенных графов) и для нахождения, если граф имеет гамильтонов путь (который зависит от наличия гамильтонова цикла). Я все испортил. Итак, какова разница между гамильтоновским путем и остовным деревом? Оба охватывают все вершины графа. Хотя мы можем иметь эффективные алгоритмы для поиска связующего дерева (возможно, минимального остовного дерева), почему мы не имеем алгоритмов для нахождения гамильтоновой схемы? Мы можем продолжать добавлять и удалять один ребро за раз, пока не достигнем цикла, и, возможно, мы могли бы найти гамильтонов цикл [
Разница между гамильтоновским путем и ST
Ответ 1
Две проблемы совершенно разные. Подумайте о минимальном остовном дереве как о проблеме соединения мест, где вам нужно заплатить только один раз, чтобы построить дорогу, но вы можете использовать ее столько раз, сколько захотите. Легко придумать самую дешевую конфигурацию дорог (например, алгоритмом Крускаля), которая позволяет вам путешествовать из любого места в любой другой.
Гамильтоновский цикл, с другой стороны, хочет, чтобы вы минимизировали фактическое расстояние перемещения, т.е. каждый переход из одного места в другое учитывался. (Он также просит вас никогда не посещать место дважды, но это небольшая деталь.) Эта проблема в основном нелокальная, в том смысле, что вы не можете сказать, делаете ли вы правильные вещи, просто изучая варианты следующий шаг. Для сравнения, жадный алгоритм MST гарантированно подберет правый следующий край для добавления к дереву на каждом шагу.
Кстати, никто не говорит, что "у нас не может быть эффективных алгоритмов для HP". Возможно, мы еще ничего не нашли: -)
Ответ 2
Обе проблемы хотят соединить все вершины друг с другом.
Для минимального связующего дерева вам не важно, к какой вершине подключена вершина a, поэтому вы можете просто подключить ее к ближайшей вершине. Поскольку вы только соединяете вершины, которые еще не подключены, это дает дерево, и у вас есть свой алгоритм.
Однако для гамильтонова пути вы заботитесь о том, в какой вершине (скажем, b) вы соединяете вершину a, поскольку вы не можете снова использовать b (иначе это не путь). Поэтому, чтобы определить, к какой вершине вам нужно подключиться, вы должны попробовать все возможности и посмотреть, что происходит. То есть никто еще не нашел эффективного способа, который, конечно, автоматически не означает, что его нет.
Ответ 3
Гамильтонов путь и особенно минимальный гамильтонов цикл полезен для решения проблемы командира-продавца, т.е. кратчайшего пути. Быстрое решение выглядит как кривая гильберта, особый вид кривой заполнения пространства также используется для уменьшения сложности пространства и для эффективной адресации. Mst похоже на соединение всех вершин вместе с самой дешевой стоимостью для подключения (т.е. Путешествия) независимо от порядка или пересечения. Полезно решить проблему, например, найти дороги, найти водопровод, найти интернет-кабель.
Ответ 4
В гамильтоновском пути все вершины, кроме источника и стока, имеют степень 2. Это не обязательно имеет место с MST (или ST, если вы этого хотите).