いくつかのノードを訪問するグリッドマップの最短経路アルゴリズム

Question

グリッドマップがあり、2つのノード間の最短経路を見つける必要がありますが、そのパスにはいくつかのノードが含まれていなければなりません。

すべての並べ替えを試してみましたが、最適なアルゴリズムを使用したいので、マップサイズと必須ノードの数は可変です。

マップはこれに似たものになります。 map

-Dark brown square at Y18 is the start point 
-Light brown squares from B20 to S20 are the end point (can make just one end point if needed) 
-White squares are walls (you cannot go through them) 
-Blue squares means that the point in front of it is a must-pass (for example, the blue square at q5-q6 means must pass zone of p5-p6) 

私は、Javaを使用するつもりだ、と私はそれがそれらの間の接続でグラフをマップするようになります（たとえばS10はS9と接続され、 o10およびs11）。

ご質問ありがとうございました。

Answer 1

これは2つの問題の組み合わせです。出発点、目的地ノード、および必須の中間ノードがあります。最短パスを決定するには、開始ノードとすべての中間ノード、すべての中間ノードのペア、および各中間ノードからデスティネーションまでの距離を計算する必要があります。負でないエッジ加重のみが関与する場合は、Dijkstraのアルゴリズムでこれを行うことができます。

すべての距離が計算されたら、開始ノードから宛先ノードまでのすべての中間ノードが使用される最適なHamiltonian pathを計算する必要があります。しかし、この問題はNP-hardであるため、効率的なアルゴリズムを使用して解決することはできません。すべての順列のブルートフォースが実現可能かもしれない。

Answer 2

ハミルトンパスを解く必要があるため、これは役に立ちませんが、すべてのノード間の距離を計算するには、Floyd-Warshallを使用して少し速度を上げてください。