以下のようなテンプレートを用意します。
■■■■■■■■■ ■十十十十十十十■ ■-------■ ■--○○○--■ ■--○○○--■ ■--○○○--■ ■-------■ ■大------■ ■■■■■■■■■ 丸印を可変部分とし、すべての組み合わせを調べます。荷物をすべてゴールに運べないのが、死に手パターンと言えます。とても簡単に数え上げることができます。 もちろん、反転・回転による一致と、「スペース→荷物→壁」変換による一致によって、パターンを絞り込みます。その結果、前述の4パターンが出てくるはずです。 3x3の四角形だけでなく、いろんな形でこの方法が使えます。また、ゴールを含めたパターンも発見できます。 このアイデアは10年くらい前から持っているんですが、まだ深くはやってません。卒論や修論の題材を探している方、やってみませんか。 #
by sokoban
| 2006-12-26 23:26
| パターン算出
このブログでは、フォントが固定長であることが前提です。
たとえば、 ■■■ 日大日 --- ↑こういうのがちゃんと正方形に見えなければなりません。 最近気づいたのですが、FireFoxではフォントの設定をどうしようとも、全角の四角形「■」のサイズが小さくなってしまいます。困ったものです。 FireFoxは好きでしたが、これにはがっかりです。私は普段、Operaを使ってます。おすすめです。 #
by sokoban
| 2006-12-26 22:48
| コラム
えらく久しぶりに書きます。
以前紹介した小田原氏の論文が、いつのまにかPDFダウンロード可能になってました。面をいくつかに分割する手法のようです。ゴールが一箇所に集中している面向け。パターンマッチングでは小さいパターンに限定されるのに対し、この方法では大きさに強いという印象でした。 #
by sokoban
| 2006-12-26 22:45
| 文献
このパターンでの基準座標は2つでした。
改めて、4つ3x3パターンについて基準座標を数えると、A,B,C.Dでそれぞれ2,2,4,2です。よって、マッチングの回数は2*8+2*8+4*8+2*8=80ということになります。 1手ごとにマッチングをするとしても、たいしたコストではありません。どの程度の効果があるかは検討の余地がありますが、これによって還って解けなくなる、という心配はありません。メモリの圧迫はなく、消費するのは時間だけだからです。 #
by sokoban
| 2005-02-06 23:12
| アルゴリズム
3x3パターンマッチングについてです。ここではこの形を例にします。
-■- 日-■ 日日- さて、動かした荷物を基準としたマッチングでは、基準座標を決めます。このパターンでは、3つの座標がありえます。以下に×印で示しました。 1) -■- ×-■ 日日- 2) -■- 日-■ ×日- 3) -■- 日-■ 日×- このパターンは線対称なので、(1)と(3)は同じです。よって、基準座標は2つです。 それぞれについて回転・反転の8つの形でマッチングをすることになります。 なお、(2)は線対称なので、反転形を省くことができます。 #
by sokoban
| 2005-01-14 02:01
| アルゴリズム
|
カテゴリ
以前の記事
フォロー中のブログ
その他のジャンル
ファン
記事ランキング
ブログジャンル
画像一覧
|
ファン申請 |
||