#問題
Python
1maze = [ 2 [9, 9, 9, 9, 9, 9], 3 [9, 0, 0, 0, 0, 9], 4 [9, 0, 0, 0, 0, 9], 5 [9, 0, 0, 0, 0, 9], 6 [9, 0, 1, 0, 0, 9], 7 [9, 9, 9, 9, 9, 9] 8]
なる番兵処理迷路を用意しました。ここで、9は障壁、0は未踏地点、1がゴールとなっています。
「Pythonではじめるアルゴリズム入門」(増井敏克著)のコードに従ってこれを解く深さ優先探索のプログラムを作成していたのですが、部分的に誤った出力が確認されておりますので、質問させて頂きます。
#ソースコード
Python
1maze = [ 2 [9, 9, 9, 9, 9, 9], 3 [9, 0, 0, 0, 0, 9], 4 [9, 0, 0, 0, 0, 9], 5 [9, 0, 0, 0, 0, 9], 6 [9, 0, 1, 0, 0, 9], 7 [9, 9, 9, 9, 9, 9] 8] 9 10 11def dfs(x, y, d): 12 if maze[x][y] == 1: 13 print(d) 14 exit() 15 16 maze[x][y] = 2 17 18 if maze[x - 1][y] < 2: 19 dfs(x - 1, y, d + 1) 20 if maze[x + 1][y] < 2: 21 dfs(x + 1, y, d + 1) 22 if maze[x][y - 1] < 2: 23 dfs(x, y - 1, d + 1) 24 if maze[x][y + 1] < 2: 25 dfs(x, y + 1, d + 1) 26 27 maze[x][y] = 0
#質問
上の関数を用いると、例えばdfs(1, 1, 0) = 4 となりこれは正しいです。しかし、他でいくつか実験してみると、dfs(3, 2, 0) = 7 (ゴールの真上にある地点なので本来は1)となり、これは明らかに最短距離ではありません。dfs(1, 4, 0) = 11(期待する答えは5)となりこれもまたおかしいです。似たプログラムを幅優先探索で実装したときには全てうまくいったのですが、どのようなことが原因かがはっきり見えませんでした。該当のアルゴリズムを知り日が浅いのでやや丸投げのような形になってしまい、素人質問にて恐縮ですが、お力添えいただける箇所がございましたら、ご教授のほどよろしくお願い申し上げます。
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2021/07/13 01:48