北国ぺんぎん

制作中のスクリプトは行数がさらにスゴイっす。
計算量を減らすために小規模なテーブルを作ったんっすけど、
要素数が1,600個ちょいっす。
普通は小規模と言えるんっすけど、
64KB制限の中だと、そこそこの大きさかもっすね。
どうもぺんぎんっす( ◎v◎ )


反復深化探索のみで進めた場合は、
1.制限時間内に解けない
2.パスすることによって手数が伸びる
っていう問題があったっす。

まず取り組んだのは、高速化っす。
当然と言えば当然っすね。

一番のポイントは「マンハッタン距離の計算」だったっす。
マンハッタン距離の定義通り計算するとなると、
正しいパネル位置を(X,Y)、現在のパネル位置を(x,y)として、
|X - x| + |Y - y|
コレをパネル15枚分について計算して、合算するっす。

枝刈りの判別のために何回も計算する必要があったっすから、
マンハッタン距離の計算は全体のコストとしても大きいっす。
for(i = 0; i < 15; i++)なんてやるよりかは、
提出したスクリプトのSub1内の関数IDSでやっているように
親局面からの差分で求めた方が明らかに早いっす。
for文でやってるのは最初の1回だけ、関数Searchの中での計算だけっす。

2月10日まではこんな感じで高速化に取り組んでたんっすけど、
次第に限界を感じ始めたっす。
このあたりから別のアルゴリズムも「併用」しようと考えたっす。

このあとSub2の制作が始まるんっすけど、また今度っす。