zaki日記(2010-08-23)_ パックマン 私の回答と探索に使用したソースコード。コードはムダに長いし地形の解析を途中まで実装したが探索には使っていない。 探索ロジックはあまり賢くない。たぶんLv2 は同じところをなんども回ってたり。一応工夫した点のメモを残す。 方針 パックマンの問題に記述されている仕様に則った動きや、ボードの情報、ある時点でのパックマン/敵/ドット/時刻の情報など探索ロジックによらない部分を共通クラスとして作成する。 ロジックは、最短を求める問題なのでまずは幅優先探索を実装する。 とはいっても探索済み状態による枝刈りが効かなそうなのに幅優先700 step の探索なんてメモリが足りないだろうから深さ優先の探索を実装する。 いずれにしろ完全な探索はリソース(メモリ/時間)食い過ぎなので探索の順序や打ち切り方法を工夫する。 うまくいかなかったらシミュレータも作って遊んでみる。よさそうな序盤の動きが見つ
