14

このようなグリッドがあるとしましょう (ランダムに作成):

グリッド

では、白いボックスの 1 つからランダムに出発する車があるとします。白いボックスのそれぞれを通過する最短経路は何でしょうか? 各ホワイト ボックスには何度でもアクセスできますが、ブラック ボックスを飛び越えることはできません。ブラックボックスは壁のようなものです。簡単に言えば、ホワイト ボックスからホワイト ボックスにのみ移動できます。

斜めにも、どの方向にも移動できます。

2 つのサブ質問:

  1. 移動する前に、すべてのブラック ボックスの位置がわかっていると仮定します。
  2. ブラック ボックスに隣接するホワイト ボックス内にいる場合にのみ、ブラック ボックスの位置を知っていると仮定します。
4

6 に答える 6

4

問題は、2 つのノード (白いボックス) 間の距離がそれらのノード間の最短経路の長さである完全なグラフとしてモデル化する必要があります。これらのパスの長さは、 Floyd-Warshallアルゴリズムによって計算できます。その後、 glowcoder が書いたように、「巡回セールスマン」として扱うことができます。

編集: より明確にするために: 一連の異なる白いボックスによって、迷路を通るそれぞれの「興味深い」パスを説明できます。各ホワイト ボックスにアクセスする任意のパスがある場合、それをサブパスに分割し、それぞれがまだアクセスしていない新しいホワイト ボックスで終わるようにすることができます。このホワイト ボックス A から B への各サブパスは、A から B への最短サブパスに置き換えることができます。そのため、ノードのすべてのペア間の最短パス行列が必要です。

于 2010-05-20T17:10:34.873 に答える
1

Docはそれを持っています。ブラックボックスは、ホワイトボックスのすべてのペア間の距離のみを変更することを追加します。さらに詳しく説明します-2つの白いボックスの間の対角線上に黒いボックスがある場合（簡単にチェックできます）、距離を取得するために最短経路を計算する必要があります。距離行列ができたら、他のすべてのノードに対して長さがゼロのダミーノードを作成した後、TSPを解くことによってTSPまたはハミルトンパスを解きます。

重要なのは、TSP（またはその問題に関する問題の定式化）を定式化して解決するには、最初に距離行列が必要であるということです。距離行列は最初は指定されていないため、最初から作成する必要があります。

于 2010-05-20T20:09:37.450 に答える
1

TSP ベースのヒューリスティックは合理的なアプローチですが、最適な答えが得られるかどうかは明らかではありません。問題は (Moron が指摘しているように) スパニング トレイル問題であり、コメントで提供されているリンクには、線形時間の最適解がある多くの特殊なケースがあります。OP の問題を、引用された論文で使用されているグリッド グラフの定式化とは異なるものにする 1 つの問題は、斜めに移動できることです。これにより、ゲームがかなり変わります。

于 2010-06-30T20:56:42.357 に答える
1

これは NP-Complete の問題のようです。

グリッド グラフのハミルトン パスは NP-Complete であり、ここに示されています:グリッド グラフのハミルトン パス。

グリッド グラフ = 完全なグリッドのサブグラフに注意してください。

もちろん、その論文は読んでいないので、まず確認してください、特に斜め移動許可部分。

于 2010-05-20T18:16:42.500 に答える
0

これは、ナイツ ツアーの問題に似ており、典型的な解では、開始広場から始まる可能性のあるすべてのルートが評価されます。ツアーを完了できない場合は、バックトラックを使用して前の決定をバックアップします。正方形を複数回訪問できるため、問題はより緩和されます。Knights tour と Traveling Saleman の問題では、通常、各広場を 1 回だけ訪れる必要があります。

http://en.wikipedia.org/wiki/Knight's_tourを参照

于 2010-05-20T16:59:43.460 に答える
-1

グラフとして作成してみて (各ノードには最大 8 つのノードがあります)、http://en.wikipedia.org/wiki/Travelling_salesman_problemのように扱ってください。

于 2010-05-20T16:57:42.890 に答える