ПРИМЕЧАНИЕ: из-за того, что поездка не заканчивается в том же месте, в котором она началась, а также из-за того, что каждую точку можно посетить более одного раза, если я все еще посещаю их все, это на самом деле не вариант TSP, но Ставлю из-за отсутствия лучшего определения проблемы.
So..
Предположим, я собираюсь в поход с n достопримечательностями. Все эти точки связаны пешеходными тропами. У меня есть карта, на которой показаны все тропы с их расстояниями, что дает мне ориентированный график.
Моя проблема заключается в том, как приблизить тур, который начинается в точке A и посещает все n достопримечательностей, а заканчивается тур в любом месте, кроме точки, с которой я начал, и я хочу, чтобы тур был как можно короче.
Из-за характера пеших прогулок я подумал, что это, к сожалению, не будет симметричной проблемой (или я могу преобразовать свой асимметричный график в симметричный?), Поскольку переход с большой высоты на малую, очевидно, проще, чем наоборот.
Также я считаю, что это должен быть алгоритм, который работает для неметрических графов, где неравенство треугольника не выполняется, поскольку переход от a к b к c может быть быстрее, чем по очень долгому и странному пути от a к c напрямую. Я действительно учел, сохраняется ли неравенство треугольника, поскольку нет ограничений относительно того, сколько раз я посещаю каждую точку, пока я посещаю все из них, что означает, что я всегда буду выбирать самый короткий из двух различных путей от a до c и, следовательно, никогда такр долгий и странный путь.
Я считаю, что моя проблема проще, чем TSP, поэтому эти алгоритмы не подходят для этой задачи. Я думал об использовании минимального остовного дерева, но мне трудно убедить себя, что они могут быть применены к неметрическому асимметричному ориентированному графу.
Что мне действительно нужно, так это несколько указателей на то, как я могу придумать алгоритм аппроксимации, который найдет почти оптимальный тур по всем n точкам.
