5puzzle
ゲーム理論の課題でA*探索を実装した.
↓コード
↓実行結果
紙とペンを使って実行したもの同じになった.
g:=世代 h:=盤面Aの各マスの盤面Goalへのマンハッタン距離の和 f:=h+g
として[f,g,"前回に移動した向き",盤面]のデータ構造でPriority-Queueを用いて求めた.
実装している中で幾つか重要なことに気づいた.
1. Python のPriority-Queueは小さいものから出ていく.
C++は大きいものからだったようなきがする. 大きい順に出したいときは-1倍して入れれば良い.
2. リストのスコープについて
このコードの実行結果は
こうなる. C++とかだと関数内だけにしか適用されないのでこのミスに1時間程気づかず痛い目を見た.
もとのリストに変更を加えずリストの要素をいじりたいときは B=list(A)のようにして新たなリストBをつくるとよい. B=Aとしてしまうと, BはAを参照するという意味になってしまいBも同じく変化してしまう.
ex)
>>>A=[1,2,3,4]
>>>B=A
>>>C=list(A)
>>>A[0]="a" #リストの要素をいじる
>>>A
["a",2,3,4]
>>>B
["a",2,3,4] #Aと同じ
>>>C
[1,2,3,4] #変化しない(オリジナルのA)
>>>A=[5,6,7,8] #新たなリストの定義, 要素をいじってるわけではない
>>>B
["a",2,3,4] #Bはそのまま
