メディア演習

メディア演習
第二回
2005 5/24 0321604 大石貴弘
今回のテーマ
パズル『箱入り娘』の解法の仕組みついて
「箱入り娘」とは？
パネルの形が一定ではないスライドパズル
最終的には「娘」のパネルが
一番下まで来ればクリア
横型探索法
横型探索法
現在の状態から計算可能な状態をすべて計算した
あと、計算された新しい状態について同じ操作を繰
り返すやり方
特徴
多量の記憶容量が必要
存在するなら必ず解が見つかる
解までの最短手順が見つかる
実際の手順
図のようにパネルに数字を割り振る
3223＊4224＊6666＊3553＊
4014という文字列でパネルの
配列を表現
手順-2
パネルの移動をチェックする文字列を各種用意し、順
番に当てはめる
例横長のパネルを下に移動できるかチェックする文字列は
ｓ/55（….）01/01ｓ｛1｝55/
新しい配列が見つかればそれを保存
以上を繰り返す
次回以降の予定
1.Perlで書かれている箱入り娘のプログラムを
C言語で再現する
2.それを応用して16パズルについて考える

Download Report