Алгоритм аппроксимации для варианта TSP, фиксированное начало и конец в любом месте, кроме начальной точки + РАЗРЕШЕНО многократное посещение каждой вершины

ПРИМЕЧАНИЕ :В связи с тем, что поездка не заканчивается в одном и том же месте это началось, а также то, что каждую точку можно посетить более одного раза, пока я все еще посещаю их все, это не совсем вариант TSP, но я поставил его из-за отсутствия лучшего определения проблемы.

Итак..

Предположим, я отправляюсь в поход с n достопримечательностями. Все эти точки связаны пешеходными тропами. У меня есть карта, показывающая все тропы с указанием их расстояний, что дает мне ориентированный график.

Моя проблема заключается в том, как аппроксимировать тур, который начинается в точке A и посещает все n достопримечательностей, заканчивая тур в любом месте, кроме точки, где я начал, и я хочу, чтобы тур был как можно короче.

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

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

Я считаю, что моя задача проще, чем TSP, поэтому эти алгоритмы не подходят для этой задачи. Я думал об использовании минимального остовного дерева, но мне трудно убедить себя, что их можно применить к не-метрическому асимметричному ориентированному графу.

Что мне действительно нужно, так это несколько указаний относительно того, как я могу придумать алгоритм аппроксимации, который найдет почти оптимальный маршрут через все n точек