2011-10-01から1ヶ月間の記事一覧

アルゴリズムクイックリファレンス 7.4 A*探索の実装

先週書いたアルゴリズムクイックリファレンス 7.4 のA*探索を Python で実装してみた。 8パズルの各ピースは、左上を起点とした (X座標, Y座標) のタプルで管理している。 8枚のピース全体は Board クラス。 いろいろ手抜き。 def CalcManhattanScoreCoords(…

アルゴリズムクイックリファレンス 7.4 A*探索での GoodEvaluator

8パズルの評価関数の例として挙げられている GoodEvaluator。 P(n)+3*S(n)、P(n)は、各駒の「ホーム」からのマンハッタン距離の和。 S(n)は、升目を順に調べて付けた点数。正しい次の駒が後に続いていなかったら2、その他の駒は、0。ただし、中央に位置する…