katsutoshi ito
itou.****@rens*****
2004年 2月 24日 (火) 10:05:18 JST
すみません。 自宅の環境整ってないので遅くなりました。m(_ _)m Shiro Kawai wrote: > > yes... 実際には私の作ろうとしてたのもさっきのようなストリームをさらに 40 〜 60 位生成して > > 全ての組み合わせを順に調べながら、全体としてある条件に match するような組み合わせを > > 取得するという処理ですんで変数束縛しちゃいけないとなると結構厄介ですね。 > > ストリームの各要素は何か複雑な系列なんでしょうか。 > n番目の要素がどんぴしゃで計算できるならそれに越したことはないわけですが… どんぴしゃではないですが頭を使えば実は結構絞り込めます。 やろうとしていたことをぶっちゃけてしまいます。 イラストロジックというのご存知ですかね。 ｎ×ｍの桝目があって、各列、各行の”連続して塗りつぶす桝目の数のリスト”が問題として列記してあるパズルです。 通常の問題とかは解は一つになりますが、一般には複数の解があったりもします。 （絵的にはまったく面白くないですけど） これの解析スクリプトを作ってみようかということです。 Lisp でパズルの解析例っていうと、いつも n-queen だったりするのでこういうのもいいのでは？と思って。 世の中にイラストロジックの解析ソフトは結構存在しているようですが、 今回は自分なりにいい勉強になるだろうという動機から着手しようかと。 で、おっしゃるような絞り込みも可能なのですが、今回は何にも考えずに総当りで条件に合うパターンだけを 抽出してやろうとしてます。 つまり問題を解くための戦略は何も考えずに問題のデータにマッチするものを探索する方式です。 > また、ストリームの履歴は重要なんでしょうか。つまり、ストリームsに対して > s[n]だけを見ればいいんじゃなくて、s[n-k], s[n-k+1], ..., s[n-1], s[n]が > 必要になる? kがboundedなら必要な分だけ取っておけばいいですね。 > バックトラックなんかで最悪全部必要とかなると厄介ですが。 というわけで必要ないです。ある瞬間に必要になるのは一つのストリーム中でただ一つの要素のみ。 ただ、今の方針では最初に生成した全パターンから一旦絞り込んだものをストリームとして 捕らえておくことになるのではないかなぁと思ってます。 例えば 1 行 10 マスとして一行だけデータ例を出すと (3 5) という問題データが与えられたとします。 これは 10 マスの内、塗りつぶされるのが連続 3 マスが最初にあって、その後何ヶ所か空白 さらに 5 マスの連続塗りつぶしがあるよという問題データです。 したがって、 (1 1 1 0 1 1 1 1 1 0) (0 1 1 1 0 1 1 1 1 1) (1 1 1 0 0 1 1 1 1 1) この三つのパターンが候補になります。 この候補パターンは一旦保持しておくことになるだろうかな？という意味です。 もちろんこれもいくつ候補が出てくるか分らないのでストリームとしてってことになるのかなと。 これを全ての行について行い、各パターンの組み合わせを求めて列データと照合して矛盾の無い解を抽出しようと。 今は １．全部のパターンをストリームにする。（これが先のメールです。。。） ２．１のストリームを各行の問題データにマッチするものだけフィルタリング（これが上の事例） ３．各候補行パターンの組み合わせを生成。（未着手） ４．３の組み合わせ候補が列の問題データと一致するものを抽出（未着手） という程度のめちゃめちゃざっくりした計画（無計画）で進めてます。 以下は蛇足ですが。。。 さっきの (3 5) の候補も頭を使えば、おっしゃるようにドンぴしゃでは無いけど絞り込める部分もあります。。。 まず、 3+5=8 マス塗りつぶし！ 要素数 2 だから間に必ず 0 が 1 個は入り、ここまでで９マス埋まる。 残り 1 マスが自由度で、この塗りつぶし無し(0)の場所をどの位置に入れるかという組み合わせの問題なので より高速にこの 3 パターンを選択できます。 (3 0 5) に 0 を一ヶ所入れる場合の組み合わせ => (0 3 0 5) or (3 0 0 5) or (3 0 5 0) から連続する塗りつぶしを 1 に展開するという具合です。 ただ今回はこういった戦略すら考えない。 ちなみに人の思考ルーチンに近いってのは、このパターンでいうと候補リストを全部パターンマッチして行き (* 1 1 * * 1 1 1 1 *) という具合に必ず塗りつぶすところを確定して行き、それを行方向列方向に一回スキャンして更新された マス目だけ色でも変えて表示してやれば次の一手になるというわけです。 ＃この確定したパターンを各行についてスキャンすると列側は候補がさらに絞り込まれる。 ＃すると絞り込まれた候補内でパターンマッチを行い確定場所が増える・・・の繰り返し ＃この例では 1 だけですが、実際は 0 が確定する場合もあります。（絶対塗りつぶされないというやつ） おそらくストリーム・継続・バックトラックなどの勉強になるのではないかなぁと。
