油売り算がまったく解けた気になれません。 - プログラミングの作業に何の価値も見出せなくなってしまったd金魚による日記

http://algorithm-study.g.hatena.ne.jp/bbs/7
via http://karetta.jp/article/blog/ll-spirit/033840
より
関数型言語が使えない私はRubyでいそいそとプログラムを組んでいました。
ですが、まったく解けた気になれません。
私の頭の方が直感で勝手に解いてしまいます。



AからCへ3移す

CからBへ3移す

AからCへ3移す

CからBへ3移す

AからCへ3移す

CからBへ1移す

BからAへ7移す

CからBへ2移す

AからCへ3移す

CからBへ3移す

もう、いろんな所でボケているようです。前日のエントリと同様に･･･

トイレに入っているときにふと思いつきました。
一番小さいビンの容量のｎ倍が他のビンの容量の＋−１が出れば解けるのではないか･･･　ちがうちがうちがうちがう。
何かが違う･･･。でもそのような気もする。

プログラミング脳も腐敗してきました。

追記：2007/09/13
id:h0shu氏より
http://d.hatena.ne.jp/h0shu/20070909/p1
様々な情報と見解を教えていただきました。

google:油売り算等で検索したらさまざまなプログラムを使ってかかれていました。

どうやらPrologなる言語をチョイスするのがよさげらしい。
http://www.unfindable.net/~yabuki/blog/2007/08/mathematica_2.html

Haskellでgoogle:モデル検査という手法をからめて。
http://www.tom.sfc.keio.ac.jp/~sakai/d/?date=20070710#p02
非常に興味深いです。

追記：2007/09/19
Rubyでいそいそと書いていたのですが、どうもRubyの文法を勘違いしている部分があってバグを誘発させてしまっています。
まず戻り値がうまく返せないと言う不思議な現象に見舞われました。多分、私がどこかにバグを内在させています。
乱数で適当にいろいろと試すようなアホなアルゴリズムで回しているのですが、10000回試行しても目的には達しませんでした。例えば、



AからCへ3移す

CからAへ3移す

といった元に戻す事を何回もやってしまう残念なアルゴリズムだったからです。
真面目に探索木みたいな、スタックを使う形式で真面目に探していくものにすればよかったのです。
恐らく、乱数で試行する方法を決めて進めていくと乱数が真性乱数だとしても、確率的にはかなり天文学的数値になるのではないかと思いました。
その確立を求める方法がよく分かっていないので私はかなり確立には弱いようです。自分の知識の弱点が分かってよかったと思います。
それと、確立についてちょっと調べていたら面白いページを見つけました。

Teao 分布
http://chasen.org/~taku/teao/
興味深いプログラムが掲載されていました。

次にこの問題の成果を発表する時は新しいエントリーに書きたいと思いますので今回の追記でこのエントリーの更新は終了です。