ソートしておく
一致を調べるときに重要なのは、ソートされていることです。これは倉庫番に限らず一般に言えます。ソート済みを前提とできるかどうかで、探索量がずいぶんちがいます。
たとえばこの場合では、「スペースが多いほど小さい」「壁が多いほど大きい」と定義し、昇順にソートしておきます。
また、最初のジェネレートの時に工夫すれば、最初からソートされた状態にもできます。この辺のテクニックは、規模が大きくなると効果が出てきます。
[PR]
by sokoban | 2007-01-07 20:19 | パターン算出


<< 変換による一致検査適用 変換による一致 >>