プログラミングによる 各種パズル解法の研究 －「箱入り娘」「１６パズル」「ルービックキューブ」－ 北海道情報大学 情報メディア学部 情報メディア学科 新井山ゼミ 0321604 大石 貴弘 発表内容（目次） • 研究概要 • 研究目的 • 研究内容 – 箱入り娘 – １６パズル – ルービックキューブ • 評価 • 考察 • 今後の課題 研究概要 • 研究目的 – プログラミングによるパズルの解法の導出 • 以下のパズルを解くプログラムを制作 – 箱入り娘 – １６パズル – ルービックキューブ • 成果 – ルービックキューブについては未達成 – その他は達成 研究目的 • プログラミングによるパズルの解法の導出 – 使用言語 • C言語 – プログラムの制作 • 解く速度 • できるだけ小さい手数 • 無駄な動作を省略 研究内容 「箱入り娘」 • 横型探索とハッシュ法を利用 – 横型探索の特徴 • • • • すべての点を探索 探索ごとに同じ内容の点がないか確認 最短解を発見 作業が膨大 – ハッシュ法の特徴 • ハッシュ値とデータの格納位置を関連 • ハッシュ表によるデータ参照の高速化 研究内容 • 箱入り娘 – ハッシュについて • できるだけハッシュ値が重ならないように計算 • 同じハッシュ値がないかハッシュ表を確認 • 同じハッシュ値を持ち、盤面の内容が違う場合 ハッシュ値を改めて計算し同じハッシュ値をもつ盤面 を線形リストに保存 研究内容 • 箱入り娘 研究内容 「１６パズル」 • 反復深化を利用 – 反復深化の特徴 • 深さ優先探索の改良 • 横型探索よりメモリの消費が少量 • 探索する深さに上限を設定 したうえでの再帰 • 下限値枝狩り法による作業の 軽減 研究内容 • １６パズル – 反復深化と下限値枝狩り法 • 「下限値」＝盤面を完成させるための最低限の手数 • 「下限値」＋「現在の深さ」＞「深さ制限」⇒探索中断 研究内容 • １６パズル – 下限値算出方法 • 各コマ（「１」～「１５」）の現在の位置と 完成時の位置との距離の合算 • コマ「６」の距離： ３ • コマ「１４」の距離： ２ コマ「１２」の距離：３ ∴合計・・・３＋３＋２＝８ 研究内容 • １６パズルの解導出 研究内容 • ルービックキューブ – 横型探索とハッシュ法の併用 – スタート地点とゴール地点から探索する 「双方向探索」 • あらかじめゴール地点からある程度の深さまで 均一に探索 研究内容 • ルービックキューブ – ２×２のルービックキューブの解導出 • １０手以内の盤面 – ３×３のルービックキューブ • １０手以上の盤面は不可 • 作業量の限界 研究内容 • ルービックキューブの解導出 評価 • 箱入り娘 – 即座に最短解を導出 • １６パズル – 大抵の盤面の最短解を導出 • ルービックキューブ – ２×２については最短解の導出が可能 – ３×３は不満 考察 • 箱入り娘 – 探索空間が狭いため、横型探索とハッシュ法が うまく動作 • １６パズル – パズルとしての構造が単純 – 苦手な盤面の存在 • ルービックキューブ – 作業が膨大 – ヒューリスティックな探索方法が困難 今後の課題 • １６パズル – 下限値の計算方法の改良 • 探索速度は下限値の精度に比例 • 盤面に対する得手・不得手 • ルービックキューブ – ３×３の解の導出 • 可能であれば常に最短解 • サブゴールの設定 – 計算の途中に到達すべき点を設定 • 評価値の導入 – 盤面の状態を数値で評価 参考文献 • • • • M. Hiroi’s Home Page – http://www.geocities.co.jp/SiliconValley-Oakland/1680/ コンピュータ＆パズル – http://www.ic-net.or.jp/home/takaken/ C MAGAZINE 「悩めるプログラマに効くアルゴリズム」 – ソフトバンク 刊 2000年11月号 pp.12-39 「Perl書法」 – 増井俊之 著，アスキー出版局 刊 1993年6月
© Copyright 2024 ExpyDoc
