Есть граф, как найти в нем гамильтонов путь, или любой другой минииальный маршрут, пересекающий все вершины, граф разный, но компланарный (при изображнэении на плоскости ребря не пересекаются, по факту соеденины только соседние вершины), надо найти какой–то маршрут что бы минимальное количество раз проходить по одним и тем же вершинам.
З.ы. Забыл самое главное, алгоритм должен работать из любой вершины графа
да, по постановке задачи, самая близкая это задача коммивояжера.
самым рациональным(с точки зрения реалий) на мой взгляд алгоритмом оказался «алгоритм составления минимального остовного дерева», возможно, чуть чуть измененный.
Если нужен гамильтонов цикл(цепь) то тут только перебор с возвратом. А вот «минимальное количество раз проходить по одним и тем же вершинам», тут, наверное, надо сначала пытаться найти гамильтонов цикл(цепь), а потом увеличивать макс. возможное число вхождений вершин.
Простой
