海野秀之（うんのひでゆき）の外部記憶
Twitter (twilog) / RSS / アンテナ / ぶくま
格子点上の経路を数える（つづき）のつづき。
http://uhideyuki.sakura.ne.jp/files2008/count_paths.c.20080520.txt
今まで、ちょこまかと試してきたバリエーションをひとつのプログラムにまとめて、 コマンドオプションで選べるようにしてみた。
オプションは、つぎのようなかんじ：
b: バックトラックする r: max 以下の乱数を得るために、(max + 1) の剰余を計算する。 (デフォルトでは、3 以下の乱数を生成しておいて、max より大きかったらもう一度) f: ゴールに届かなかった試行も一回とカウントする m: メルセンヌ・ツイスタを用いる p: （おまけ）生成したパスを標準出力に表示
メルセンヌ・ツイスタの生成ルーチンは、 mt19937ar.c を用いました。
まだ、まとまった時間がとれなくて味見程度なんだけど、
まず、正解とされている数値：
| 生成回数 | 経路の数 | 経路の平均長さ | 中心を通る確率 |
| 正解 | 1.57e+24 | 91.9 | 79.3% |
というのがいいみたい：
./count_paths fm 500000 ---- Result ---- # of paths = 1.589540e+24, l = 92.590, hitc = 75.664
r オプションには、大した効果がないんじゃないかな：
./count_paths fmr 500000 ---- Result ---- # of paths = 1.588522e+24, l = 91.751, hitc = 75.581
C 標準の rand() にすると、正解から離れてしまう。乱数の質は大いに影響するみたい：
./count_paths f 500000 ---- Result ---- # of paths = 1.824872e+24, l = 92.579, hitc = 80.409
ゴールへたどり着くのを失敗した試行をカウントしない（なかったことにしてしまう）と、 推定値は上にぶれる：
./count_paths m 500000 ---- Result ---- # of paths = 3.217146e+24, l = 92.590, hitc = 75.664
バックトラックすると、よりいっそう悪い（時間もかかる）：
./count_paths bm 500000 ---- Result ---- # of paths = 1.457106e+25, l = 92.325, hitc = 77.607
経路数については、一桁ちがってしまってます。 バックトラックによって経路が延びる方向に何度も補正がかかるので、 もはやランダムとはいえない*1 のでしょう。
せっかくなので、プログラムのデバッグと、結果のまとめをやっときたいかな、そのうち。
ひとまずのメモとしては、
あと、今回の話と直接の関わりはないのですが、 よい乱数・悪い乱数という記事も面白い。
はじめからメルセンヌ・ツイスタを使っていたら、 これほど色々なことを試すハメにはならなかったかもしれません。
ま、個人的に面白かったのでよし。
さて、信頼区間をどうやって求めよう？うむむむ。
*1 「ランダムといえる」というのが何を意味するのか、僕は理解していないことに注意。
「ハミルトン経路」でググると、Wikipedia の「DNA コンピュータ」というページがトップにくる。 「ハミルトン路」、「ハミルトン閉路」だと、そのようにはならず、 グラフ理論関連のページが上位にくるようだ。
つまり、Hamiltonian path を「ハミルトン経路」と訳したのは、 萩谷先生が仕掛けたワナだったのか！
あ、どうでもいいすか。
気になっていたことを、さっき確認。
『最短経路の本』では、索引に「ハミルトン経路」という項目がある。 本文中では「ハミルトン路」と書かれているんですが……。
これまで僕はまったく読書家ではなかったので、 世の中はまさに未読の本で溢れている。 べたに有名な作品でも、平気で未読だ。
というわけで、べたに有名な小説を読んでみようと思って、いま読んでいるのが『三銃士』。
三銃士は、むかしチャーリー・シーンが出ている映画（たぶん これ）をみたくらいで、読んだことはなかった。 そんなところ、ブックオフで二巻組のうち 上巻 だけが 105 円で売られていたのを見つけて、ゲット *1。
読んでみると、けっこう面白い。これは、 下巻 も入手せねばなりますまい。こっちは定価でもいいや。
「このひと突きはアトス、これはポルトス、こんどはアラミス」って。 チャオズの分もおねがいします！
全体的に、三銃士が童話のヒーローばりに立派じゃないところが、おもしろい。
ビッグエンディアンがリトルエンディアンで、ヤフーがラピュタな『ガリヴァー旅行記』 はというと、ほったらかしになってたり……するんですが。
ま、いいよね。
*1 ほかにも、「グリム童話」や「フランケンシュタイン」を同じような値段で買った。
奇遇ですね。私も最近、「ごく普通に有名な本」を読んでみようかなぁとか思い始めたところです。<br>で、行きつけの本屋(普段は漫画しか買わない)にいったときに買おかなーっとか思ったんですが、<br>小さい本屋で、きれいな文庫本がなかったからなんとなくやめてしまった。んでそのうち、著名な本なら、図書館で借りよかなとか無謀なことを考えて、結局いまだ実行できず。