回答編集履歴
2
後半部分の表現変更
answer
CHANGED
|
@@ -14,9 +14,12 @@
|
|
|
14
14
|
要するに「格子の数値はスタート地点からその格子へたどり着くための最短経路の距離」だと思えばよいです。また初期化する際の「0」という値にはそれほどの意味はなく「最短経路の距離」と区別できる値なら何でもよいでしょう。
|
|
15
15
|
|
|
16
16
|
---
|
|
17
|
+
最適化について：
|
|
18
|
+
上記はA*の戦略の基本部分を述べたものです。比較的小さな領域なら上記のままでもよいと思います。ただ領域が大きくなってくると以下のような最適化の必要性が高まると思います。
|
|
19
|
+
|
|
17
20
|
- A*と上の論理の違い
|
|
18
|
-
A*
|
|
21
|
+
A*と上の論理の違いは、(4)で「最もゴールに近そうな格子から先に調べる」という工夫をしているだけです。ただ計算量的には大変重要な工夫です！
|
|
19
22
|
|
|
20
23
|
- (4)のnextの見つけ方
|
|
21
|
-
毎回二次元の格子を端から順番に調べるというのは素朴ではありますが愚策です。10x10だとすると毎stepごとに100個のサーチをせねばならずその殆どがスカなのですから。
|
|
22
|
-
|
|
24
|
+
毎回二次元の格子を端から順番に調べるという素朴な方法もありますが、領域が大きめになってくると計算量が問題になってきます。例えばスタート地点やnextに値を書き込むとき、その周りの0の格子を調べてそれをキューに入れると効果的と思います。そうしておくと、キューに入る格子の数はたかだか数個ですので、全部の格子を調べるよりはるかに高速にnextを見つけられます。
|
|
25
|
+
(実際問題として10x10程度の領域であれば大した問題ではありません。しかし100x100ぐらいになると1stepあたり10000回、最短経路を見つけるまでに最悪100万回オーダーのスキャンが必要になるためこうした工夫も考えたくなります)
|
1
誤記訂正
answer
CHANGED
|
@@ -11,7 +11,7 @@
|
|
|
11
11
|
|
|
12
12
|
(4)<->(5)を繰り返しつつ、(4)がゴールの格子だったときが最短経路を見つけたことになります。具体的な最短経路はゴールの数値がMだとするとその格子の周りをみてM-1の格子を見つけ、さらのその格子の周りをみてM-2の格子を見つけ・・・を1の格子(つまりスタート)が見つかるまで繰り返せばよいです。
|
|
13
13
|
|
|
14
|
-
要するに「格子の数値はスタート地点からその格子へたどり着くための最短経路の距離」だと思えばよいです。初期化する際の「0」という値にはそれほどの意味はなく「最短経路の距離」と区別できる値なら
|
|
14
|
+
要するに「格子の数値はスタート地点からその格子へたどり着くための最短経路の距離」だと思えばよいです。また初期化する際の「0」という値にはそれほどの意味はなく「最短経路の距離」と区別できる値なら何でもよいでしょう。
|
|
15
15
|
|
|
16
16
|
---
|
|
17
17
|
- A*と上の論理の違い
|
|
@@ -19,4 +19,4 @@
|
|
|
19
19
|
|
|
20
20
|
- (4)のnextの見つけ方
|
|
21
21
|
毎回二次元の格子を端から順番に調べるというのは素朴ではありますが愚策です。10x10だとすると毎stepごとに100個のサーチをせねばならずその殆どがスカなのですから。
|
|
22
|
-
こういう点も工夫が必要です。スタート地点やnextに値を書き込むとき、その周りの0の格子を調べてそれをキューに入れるとう方法がよいと思います。そうしておくと、キューに入る格子の数はたかだか数個ですので、100個のサーチをするよりはるかに高速にnextを見つけられます。
|
|
22
|
+
こういう点も工夫が必要です。スタート地点やnextに値を書き込むとき、その周りの0の格子を調べてそれをキューに入れるという方法がよいと思います。そうしておくと、キューに入る格子の数はたかだか数個ですので、100個のサーチをするよりはるかに高速にnextを見つけられます。
|