コンデンサの隣からひとこと

DevQuiz：スライドパズルのソースコード(C言語)

技術

GDD2011のDevQuizのチャレンジクイズである、スライドパズルのソースコードを晒します。

たいへんぐちゃぐちゃなので、恥ずかしい…。

これで２日くらい５プロセス回すと、4500/5000くらい解くことができます。（自分の結果は4427/5000でした。合計してDevQuizの成績は144.3点でした）

おそらく最短手が得られているはずです。

全問解答するためには、これに色々ヒューリスティックな改造をする必要があります。＞と思ったのですが、色々工夫するとヒューリスティック抜きでもいいところまでいけるようです。

アルゴリズムの方針としては、反復深化深さ優先を基本としてます。加えて終了局面を起点として幅優先で正解局面を展開してハッシュに溜めて、深さ優先の終了チェックに使用します。終了局面との距離には普通のマンハッタン距離を使用してます。それだけです。

他の方のツイートをみると、壁を考慮したマンハッタン距離を使うのが普通のようで、確かにすっかり考えから抜けていて大変悔しかったり。

改善版では、手数は伸びるけれど深いところまで探れることを期待して山登り法を試していて、確かに解けない問題も解けては居たんですが、爆発的に手数が増えてしまって困っているところでタイムアップでした。あと無計画に実装したソースコードが手に負えなくなってきて、詰まったというのもあり…orz

ソースはgithubに上げておきます。

https://github.com/kishima/SlidePuzzle

ツイートする

Permalink | コメント(0) | トラックバック(2) | 12:40