カテゴリ:同一チェック( 3 )
メモリ調整
メモリを調整し、512MBまで使用可能にして試しました。3種4x3について、重複排除まで。

全組合せは3の12乗で531441個、重複排除後では134865個。
かかった時間は9分10秒でした。元は30分たってもできなかったので、同一チェックの改善は効果的だったといえます。

他のサイズの場合では、メモリ調整によって多少速くなりました。35秒が31秒になるという程度です。

インデックス法ではこの辺が限界かなと思います。4x4や3x5の場合は必要時間がぐっと増えるでしょう。ゴールを含めた4種についても考えると、さらに工夫が必要になりそうです。とりあえずはこのスピードでよしとして、3種4x3の規模までに限定して実験を進めることにします。
[PR]
by sokoban | 2007-01-13 01:06 | 同一チェック
インデックス法
同一チェックを、インデックス法を採用して工夫しました。
考え方は単純で、3種の場合はそのうちの2種について、それぞれの数をインデックスとします。2種の数が一致する範囲では、全探索します。

たとえばこんなパターンとします。
 ABB
 AAA
 AAC
3種の数をそれぞれ数えると、Aが6個、Bが2個、Cが1個です。この場合はa=6,b=2をインデックスとします。AとBの数が決まればCの数が決まるので、これで十分です。

これだけですが、かなり時間は短くなりました。
2種4x4の場合3分以上かかっていたのが、30秒ほどになりました。
3種3x3の場合は13秒ほどだったのが1秒ほどです。
しかし3種4x3では、メモリ不足で失敗しました。あらためて、メモリの使用許可サイズを増やしてやってみることにします。
[PR]
by sokoban | 2007-01-12 01:36 | 同一チェック
重複排除までのコスト
3種3x3パターンの算出において、全組合せに対して同一チェックをして、「重複排除後」として2862個が残るまでにかかる時間に注目します。この場合、13秒ほどでした。
これが2種3x3だと0.1秒もかかりません。2種4x3だと1秒程度、2種4x4だと3分以上になります。
3種4x3では、30分たっても終わりませんでした。このように、ちょっと広くなったり種類が増えたりすると、急激にコストが増大します。

今のところ、同一チェックにはたいした工夫がありません。いわゆるバカサーチで、全探索をしています。荷物や壁の数ごとにまとめておくとか、インデックスのようなものがあると良いでしょう。
同一チェックで定番なのはハッシュ法ですが、ちょっと複雑になるので、とりあえずは単純な手法でやってみようと思います。
[PR]
by sokoban | 2007-01-11 01:50 | 同一チェック