目的地（下の赤い点）といくつかの関心のあるポイント（黄色、緑、青の点）が記載された地図があります。
目的地へのパスを見つけようとしていますが、出発点は定義されていません。ルートを遠回りにすることなく、できるだけ多くの関心のあるポイントを通過させたいだけです。
たとえば、この場合、次の（ピンクの線）が適切なルートになります。
黄色の点は目的地から最も遠いPOIであり（この場合は役に立ちません）、緑色の点は次に4つ遠いPOIです。
誰かがこれに適したアルゴリズムを提案できますか？
これはグラフに変換するのに適した問題ですか？「あまり遠回りではない」という要件はそれを示唆しているようですが、途中でできるだけ多くのPOIを渡したいとどうやってそれを調整するのでしょうか。
編集：「あまり遠回りではない」要件を明確にするため。たとえば、すべてのコーナーの合計で最大90度回転するなど、もっともらしいルートにしたいだけです。POIは常に目的地の近くにあるため、長さは実際には問題になりません。
The problem can definetly be reduced to a graph G=(V,E) where V are all your POI, and E in this case is V x V (edge between all vertices). You also need to produce a weight function w:E->R such that w(u,v) = distance between u and v
The problem is actually a variation of the Traveling Salesman Problem, so it is NP-Hard (So there is no known polynomial solution) - but have a look around, there are many heuristics for this problems.
Also - if you do not expect many POIs (say 20-30) - a dynamic programming solution can be used to find the optimal path between all points.
それをグラフに変換して、関心のある各ポイントに負の重みを割り当て（おそらく、そのポイントにつながるエッジの値を減らすことによって）、そのグラフをベルマンフォードアルゴリズムに接続できるようです] 1、これにより、負の長さのエッジが可能になります。2つのPOIが非常に接近している場合にのみ問題が発生する可能性があるため、何らかのプルーニング方法が必要になる可能性があります。