uDiary

◆ 格子点上の経路を数える（つづき）

格子点上の経路を数えるの続き。 まだ途中なので、メモ書きの羅列。

「"Selected Papers on Computer Science" より、 Counting the Paths on a Grid (p.39)」 とか言っても、本を持っていない人にはなんのこっちゃわからないですね。 "Coping with Finiteness" に収録されているので、本を買わなくても、この論文を読めば書いてあります。 ( http://www.sciacchitano.it/Spazio/Coping%20with%20Finiteness.pdf に落っこちている？ *1)

バックトラックを実装してみたんだけど、予想通り推定値は経路の数が増える方向に （つまり、正解から離れる方向に）振れた。

バックトラックによって判明した、袋小路行きのパスを可能性から排除して計算しても、 なお大きすぎる値がでる。

Knuth ろんぶん中の例では、各格子点に経路候補の数が書いてあるんだけど、 袋小路行きのパスを除いたりはしていないように見える。

やっぱり、経路生成の際にバックトラックしてしまうと、もはや random とはいえないような。

「random に経路を選択していたらゴールにたどり着きませんでした」という事象も、 ちゃんとカウントすべきなのではないか。

バックトラックはしない、かつ、失敗事象も生成回数にカウントするようにしてみたら、 「正解」に近づいた感じがする。だけど、 試行回数を増やしていくとある値に漸近していくって感じの挙動ではないみたい。 まだ不安定。

もしかして、不安定なのは、乱数の品質が悪いから？

そもそも、平均の求めかたが変？

以上の事柄を整理してみよう。いままで試したバリエーションは、 それぞれ別のやっつけプログラムになっているので、まとめて （オプションで挙動を変えられるようにして）しまう。デバッグもする。

追記

正直いって、自分が作ったプログラムが正確には何を計算していることになるのかが、 いまいち理解できていない。

僕が、自信をもって信頼区間つきで推定できる日は遠そうだぜ。

いま得られている結果を整理したら、この問題に固執するのではなく一旦手を離して、 ほかの同様の題材にあたってみようかな。

◆ [本] 「妖女サイベルの呼び声」を読んでいる → 読了

いま、６章を読み終わったところ。すごいなー。すごい。 いや、なにも書かないでおこう。 いまから読もうとする人の楽しみを、少しでも奪ってはいけない。

（追記）読了。おもしろかった。