An 8-puzzle solver in Scheme

コードも雑然としていますがとりあえず,…

  • ソースプログラムはこちら → heuristic-search (ダウンロード後に,拡張子をscmに直してください;2011年6月20日バグ修正(以前のプログラムは,best-firstがa-starと同じになってたので,正しいものに置き換えました)
  • 8パズルソルバーのローディング.上記のファイルが置かれたディレクトリでscheme (jakld)を立ち上げ,
    (load “heuristic-search.scm”)
    として,heuristic-search.scmに書かれたSchemeの関数定義式を実行する.
  • 8パズルソルバーの実行:
    (8-puzzle-solve-and-show ‘(2 1  3 4 5 6 7 8 0) ‘a-star)
    などで,実行できる.8パズル問題は長さ9のリストで表す.第1要素が中央.第2要素以下は,左上から右回りになっている.また,0はパネルのない場所を指す.
    例えば,(2 1  3 4 5 6 7 8 0)というリストは,
    1 3 4
    0 2 5
    8 7 6
    という初期状態を表す.この問題は7ステップで簡単に解ける(8,7,6,5,4,3を右に回し,2を上に送ればよい).
  • 実行例1:(2 1  3 4 5 6 7 8 0)
    この例は,
    1 3 4
    0 2 5
    8 7 6
    を扱う.breadth-firstは212状態を調べ,7ステップの最適解を出力する(log).hill-climbingは28状態を調べ,27ステップの解を出力する(log).best-firstは9状態を調べ,7ステップの解を出力する(log).a-starは初期状態を含めて11個の状態を調べ,7ステップの最適解を探し出す(log).
  • 実行例2:(3 2 4 0 6 5 7 8 1)
    この実行例では,
    2 4 0
    1 3 6
    8 7 5
    という問題を,hill-climbing, best-first, breadth-first, a-starで解いている.
    ・ breadth-firstは10ステップの最適解を見つけているが,探索量は1028状態(log)
    ・ hill-climbing:探索量はわずか194状態だが,見つかった解も186ステップある.(log)
    ・best-firstは解の品質が向上している. 217回の探索を行い,20ステップの解を見つけている.(log)
    ・a-starはbreadth-firstと同様最適解を見つけるが,50個の状態空間しか探索していない.(log)
  • 実行例3:(0 2 4 6 5 8 1 7 3)
    2 4 6
    3 0 5
    7 1 8
    はなかなかタフ.hill-climbingを使うと,1599通りの可能性を調べるだけで解を出力するが,その解の実行には1562ステップを要し,最適解からは程遠い(log). a-starは8648通りの可能性を調べ,20ステップの最適解を探し出す(log).

カテゴリー: 未分類 パーマリンク