graph - グラフ内のすべての目的のポイントへの最短経路を見つける

Question

インタビューで次の質問をされました

4X4グリッドが与えられます。グリッド上のいくつかの場所には宝物が含まれています。あなたの仕事は、宝物を含むすべての場所を訪れてそれを集めることです。隣接する4つのセル（上、下、左、右）を移動できます。「宝物収集」の各移動とアクションは、単一のユニットコストです。グリッド全体をトラバースし、グリッド上のすべての宝物を収集して、かかるコストを最小限に抑える必要があります。

私が正しく思い出すことができるならば、これは与えられたサンプルグラフです：

U..X
..X.
X..X
..X.

ここで、Uは私の現在の位置であり、Xは宝物の位置を示します。

私が提示した解決策は、グラフを横断する幅優先探索を使用し、その間に「宝物を収集する」ことでした。しかし、インタビュアーは、コストを最小限に抑えるためのより良い方法があると主張しました。あなたがそれを理解するのを手伝ってくれることを願っています。

Answer 1

これは小さな変装で巡回セールスマン問題であることを認識しておく必要があります。幅優先を使用すると、訪問する必要のあるさまざまな頂点間の最短の方法を決定できます。これにより、頂点間の重み付きエッジとしてそれらの方法だけを含む派生グラフが得られます。それ以来、それは古典的なTSPです。

Answer 2

同時にすべての方向に移動することはできないため、BFSだけでは解決できません。単一ソースの最短経路問題ではありません。宝物を収集すると、元の場所からではなく、現在の場所から次の経路への経路を開始するためです。

すべての宝物を集めるのにかかる時間は、ボックスにアクセスする順序によって異なりますX。そのうちの5つしかないため、120の注文すべてを試して、コストを計算し、最適なものを選択できます。

順序が固定されている場合、解決策は簡単であることに注意してください。セル間のマンハッタン距離を順番に合計し、最小の結果を選択します。