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