risentveber
@risentveber
fullstack web developer

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

Нужно обойти все вершины неориентированного связного графа, точечно перемещаясь по ребрам. Граф - произвольный (не Эйлеров и не Гамильтонов, кроме связности ничего не дано). Переход по ребру - один шаг. Как сделать это за минимальное число шагов? Возвращаться в исходную вершину, как в задаче с коммивояжером не обязательно главное посетить каждую вершину хотя бы раз.
  • Вопрос задан
  • 3452 просмотра
Пригласить эксперта
Ответы на вопрос 3
Labunsky
@Labunsky
Я есть на хабре
Очевидно, с помощью обходов графа.
Какой из алгоритмов лучше использовать и какие модификации можно внести - зависит уже от конкретных особенностей графа, то есть у произвольного заранее неизвестно, какая вариация окажется самой оптимальной.
Если возможно, то нужно собрать статистику и посмотреть на возможные особенности обрабатываемых графов. Так, например, для "звезд" будет оптимальным обход центра с BFS, после чего обработка лучей с помощью DFS.
Ответ написан
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
Если говорить про монетки: это нахождение кратчайшего пути, на котором лежат все монетки. Я бы использовал алгоритм Дейкстры.
Ответ написан
@tomatho
Для количества вершин порядка 15: (больше 15 вершин будет работать уже сравнимо дольше)
  1. Запускаем флойда чтобы получить матрицу 15х15 путей как из одной вершины быстрее всего попасть в другую. Либо 15 обходов в глубину (та же скорость, тот же эффект).
  2. Перебираем все перестановки чисел от 1 до 15, которых как известно 15! = 1307674368000.
  3. С помощью матрицы полученной на первом шаге, считаем общее количество шагов,
    которые получились бы если бы мы проследовали по вершинам в порядке перестановки.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы