Как оптимально обойти все вершины графа?

Question

[Risent Veber]

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

Answer 1

[Labunsky]

Очевидно, с помощью обходов графа.
Какой из алгоритмов лучше использовать и какие модификации можно внести - зависит уже от конкретных особенностей графа, то есть у произвольного заранее неизвестно, какая вариация окажется самой оптимальной.
Если возможно, то нужно собрать статистику и посмотреть на возможные особенности обрабатываемых графов. Так, например, для "звезд" будет оптимальным обход центра с BFS, после чего обработка лучей с помощью DFS.

Comments

[Risent Veber]

Смотри какая тема - есть лабиринт с монетками как оптимально обойти его за минимальное число шагов(лабиринт - не дерево!) - точка старта - зафиксирована

[Risent Veber]

Я думал построить минимальное остовое дерево с помощью алгоритма Крускала - и потом на нем сделать обход в глубину, но не думаю что это самое оптимальное решение.

[Labunsky]

Risent Veber: если вся структура лабиринта заранее неизвестна - то его лучше обходить с помощью обхода в ширину - он гарантирует нахождение самого оптимального пути и сам является оптимальным. Для использования с монетками можно попробовать манипулировать с длинами ребер, ведущим к ним, при инициализации графа.
Более оптимальным кажется подход с последовательным использованием алгоритмов A* и B*: отправной точкой является старт, а целями монетки, при этом, после нахождения каждой монетки, алгоритм запускается заново, используя в качестве старта позицию последней найденной монеты.

Answer 2

[xmoonlight]

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

Comments

[Risent Veber]

Как именно - нужно не просто найти кратчайшие пути из одной вершины в другую - ты все равно уходишь от объяснения алгоритма выбора монет по кратчайшим расстояниям между которыми ты будешь делать обход

[xmoonlight]

Risent Veber: как именно я ухожу?

[Risent Veber]

xmoonlight: хорошо - нашли все пары кратчайших расстояний между монетками с помощью алогоритма Дейкстры, дальше - каков порядок выбора монеток?

[xmoonlight]

1. Кратчайший путь по алгоритму Дейкстры от текущей вершины
2. Ищем ближайшую к текущей вершине (минимальная длина ребра)
3. Удаляем из графа текущую и перемещаемся к новой
4. Принимаем новую, за текущую вершину
5. GOTO 1

[Risent Veber]

xmoonlight: я понял - обычный жадный алгоритм - не всегда приводящий к оптимальному решению

Answer 3

[tomatho]

Для количества вершин порядка 15: (больше 15 вершин будет работать уже сравнимо дольше)

1. Запускаем флойда чтобы получить матрицу 15х15 путей как из одной вершины быстрее всего попасть в другую. Либо 15 обходов в глубину (та же скорость, тот же эффект).
   
2. Перебираем все перестановки чисел от 1 до 15, которых как известно 15! = 1307674368000.
   
3. С помощью матрицы полученной на первом шаге, считаем общее количество шагов,
   которые получились бы если бы мы проследовали по вершинам в порядке перестановки.