紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

5puzzle

ゲーム理論の課題でA*探索を実装した.

↓コード

gist.github.com

 

↓実行結果

f:id:umashika5555:20161030020036p:plain

紙とペンを使って実行したもの同じになった.

g:=世代 h:=盤面Aの各マスの盤面Goalへのマンハッタン距離の和 f:=h+g

として[f,g,"前回に移動した向き",盤面]のデータ構造でPriority-Queueを用いて求めた.

 

実装している中で幾つか重要なことに気づいた.

1. Python のPriority-Queueは小さいものから出ていく.

 C++は大きいものからだったようなきがする. 大きい順に出したいときは-1倍して入れれば良い.

2. リストのスコープについて

 f:id:umashika5555:20161030020722p:plain

このコードの実行結果は

 f:id:umashika5555:20161030020752p:plain

こうなる. 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はそのまま