Разница между гамильтоновым путем и ST

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

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

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

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

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

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

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

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