1

私は現在、グリッドを表すために 2D 配列を使用して貪欲な最良の最初の検索を実装しています。私の実装は現在、開いているノードを返します。PriorityQueue を使用しています。通過したパス/開いたノードを返し、ノードを見ると、アルゴリズムがグリッドの一方の側から別の側に何度かジャンプしているように見えます。これを行うことになっていますか？プレイヤーがグリッドをトラバースするときに、グリッドの反対側のセルにジャンプして、そこのヒューリスティックが優れているという理由だけでジャンプするのは意味がありません。私はこのグリッドを使用しています: グリッド

これらは、開かれたすべてのノードの (y, x) 座標です (2D 配列を表すのは y, x であることに注意してください)。

0,0 Goes across the top of the board
0,1
0,2
0,3
0,4
0,5
1,5 Goes down one cell
1,4 goes left
1,6 goes right 2 spaces
0,6 goes up
1,7 goes down the side of the board
2,7 \/
3,7 \/
4,7 \/
5,7 \/
0,7 jumps up across the board
6,7
1,2 jumps up across the board
2,2
3,2
4,2
3,1
4,1
3,0
2,1
5,2
5,1
4,0
2,0
7,7 jumps up across the board
7,6
7,5
6,5
5,5
5,4
4,4
3,4
3,5
4

1 に答える 1

1

優先度付きキューにノードを追加するときに各ノードの親を追跡する場合、キューはノードだけでなくパスセグメント全体を追跡していると考えることができます。キュー内の各ノードは、そのノードで終了する実行可能なパスセグメントを表します。

たとえば、5,7に到達した時点で、このパスがこれまでで最も有望であると判断しました。

(0,0 0,1 0,2 0,3 0,4 0,5 1,5 1,6 1,7 2,7 3,7 4,7) [5,7]

（ノード[brackets]とそのノードに到達するためのパスを配置しました(parentheses)。親のチェーンを逆方向にたどるとパスが生成されます。）

5,7ノードがパンアウトしない場合は、5,7の後続ノードをすべてキューに追加してから、キューから次のノードをプルします。この時点で、5,7の後継者の1人を獲得していないことがわかります。代わりに、ヒューリスティック関数は別のノードを試すことを決定します。

(0,0 0,1 0,2 0,3 0,4 0,5) [0,6]

これを試み、目標に到達せず、続行します。ここで、5,7の後継者の1つを検討することに戻ります。

(0,0 0,1 0,2 0,3 0,4 0,5 1,5 1,6 1,7 2,7 3,7 4,7 5,7) [6,7]

等々。

于 2012-11-17T20:50:49.170 に答える