北国ぺんぎん

チューリップが早くも咲きそうっす。
今年は球根を作るのはあきらめたっす。
どうもぺんぎんっす( ◎v◎ )


スクリプトはRekal Thorに置いてあるっす。
左上のリンクからどうぞっす。
1階の角の黒い箱っす。

今回は「最初に考えたアルゴリズム」っす。
結論から言うと、反復深化探索っす。
最初から大会に提出するまで変わらなかったっすね。

大会は手数が勝敗を決めるっす。
タイムは同一手数のときのみ判定材料になるっす。
なので、時間がかかっても最短手数となるルートを
見つけることを目指したっす。

となると、もう選択肢は1つ、反復深化に限られたっす。
(自分が知ってるのはコレだけだったんっすけど、他にあるっすか?)
幅優先探索は容量不足が明らかっすから却下っす。
最適解の保証がない、単純な深さ優先探索も使えないっすね。

問題は時間計算量がO(b^d)ってことっす。
指数関数オーダーっす。
「解けるまで待つ」という姿勢はこのときからっす。
1手を犠牲にしてでも、探索する時間を稼いだっす。

---

この考え方は「探索を終えるまでが短時間」ならOKっす。
実際には「ムダな手を指してでも完成させる」よりも、
「パスし続けて(リンクメッセージで16を送って)最短」の方が
圧倒的に手数が掛かってるっす。

最初に組み上げた(2月3日作成)ものでは、
制限時間の10分で解ける問題の範囲が
「最短手数が16手以下」に限られてたっす。
解けるまでパスし続けていたわけっすから、
16(解答手順)+20(パスした回数)=36手で解いていたっす。
20手問題だと30分くらいっすね。
20+60=80手っす。

反復深化のみだと、
1.制限時間内に解けない
2.パスすることによって手数が伸びる
っていう2つの問題が出てきたっす。


これを解決するために・・・
っと長くなったので次回っす。