注：旅行が開始した場所と同じ場所で終了しないという事実と、すべてのポイントを訪問している限り、すべてのポイントを複数回訪問できるという事実のため、これは実際にはTSPバリアントではありませんが、問題のより良い定義が不足しているため、私はそれを置きました。
それで..
n個の興味のあるポイントでハイキング旅行に行くとします。これらのポイントはすべてハイキングコースでつながっています。すべてのトレイルとその距離を示す地図があり、有向グラフが表示されます。
私の問題は、A地点から始まり、nの関心のあるすべての地点を訪れるツアーを概算し、開始地点以外の場所でツアーを終了する方法です。ツアーをできるだけ短くしたいと思います。
ハイキングの性質上、高地から低地への移動は他の方法よりも明らかに簡単なので、これは残念ながら対称的な問題ではないと考えました（または、非対称のグラフを対称のグラフに変換できますか？）。
また、aからbに移動する方が、aからcに移動する非常に長くて奇妙な道路を使用するよりも高速である可能性があるため、三角不等式が満たされない非メトリックグラフで機能するアルゴリズムである必要があると思います。直接。三角不等式がまだ成立するかどうかを検討しました。すべてのポイントを訪問する限り、各ポイントを訪問する回数に制限はないためです。つまり、aからcまでの2つの異なるパスの最短を常に選択するため、決して長くて奇妙な道をたたく。
私の問題はTSPよりも簡単だと思うので、これらのアルゴリズムはこの問題に適合しません。最小全域木を使用することを考えましたが、非メートル法の非対称有向グラフに適用できることを確信するのに苦労しています。
私が本当に望んでいるのは、n個のポイントすべてを通るほぼ最適なツアーを見つける近似アルゴリズムをどのように考え出すことができるかについてのいくつかの指針です。