uDiary

◆ 格子点上の経路を数える

"Selected Papers on Computer Science" より、 Counting the Paths on a Grid (p.39) をやってみる。 これは、「コンピュータ科学者がめったに語らないこと」で紹介されていた題材で、 詳しく知りたかったので Selected 〜 を入手した。 ま、あんまり詳しくは書かれていなかったんだけど。

まずは、雰囲気を掴むために、ランダムに経路を生成して、単純に平均値を求めてみる (ソース)。

本を入手した動機としては、 Knuth せんせいが、どういう風に信頼区間を計算したのかが知りたかったのだが、 詳しい方法は本に書かれていなかった。

そこで、まず平均値だけでも合うかなぁ〜と思ってやってみたのだが……あってないね、これ。

まず、僕が今回作ったプログラムの出す値は、なんかとっても不安定だ。 とくに、経路の数が。

プログラムがバグってて、経路数の推定が間違っているんだろうなぁと思う。 だとすると、経路の平均長さとか、中心を通る確率の方がそこそこ合っているのが不思議。 いずれも、経路の数を使って計算してるからなぁ。たまたま合っているように見えるだけなのか…。

要デバッグだが、たぶんしばらく放っておくことになりそうなので、とりあえずメモっておく。

いくつか気になった点：

Selected 〜では、最初５つの経路を例に挙げているんだけど、それでも、 僕のプログラムで生成回数１０回とした場合よりもマシな推定になる。 Knuth せんせいが恣意的な選択をしていないのだとすると、この時点ですでに何かが変。

僕のプログラムは、バックトラックしていないので、袋小路にはまった経路は捨てている。 これが推定に影響しているんではないかと思う。

だだ、袋小路にはいりがちな経路というのは、曲がりくねっていると思われるので、 こういう経路を捨てずにきちんと拾うと、得られる推定値は、経路の数が多めに、 平均長さが長めに修正されることになるのではないか？ だが、それで正解に近づくとも思えない。

(追記) バックトラックを実装してみようと思うのだが、その前に、 浮動小数点演算のせいで計算が不安定になっていないかが気になった。 簡単なチェックとして、double を用いていたところを float に変えて計算結果を比較してみた。 そうすると、微妙に計算結果が変化したが、大幅に変わることはなかったので、たぶんおっけい。 計算結果がおかしいのは、浮動小数点演算のせいではないだろう。

(もういっこ忘れないうちに追記) 現時点のプログラムには、いろいろ問題がありそうなんだが、 それらを改善した後に試してみたいことがある。 それは、この確率的計算に用いる疑似乱数は、単純なものでもいいのではないかということ。 いまはお手軽に C 標準の rand を用いているんだが、もっと簡単な方法 (bit 数少なめの線形合同法とかかな) を用いても解の精度は悪化しないんじゃないかと思っている。 根拠レスだが。

ああ、そういえば、

The planet without laughter を読もうと思ったんだった。 自分自身の処理能力の驚くべき低さを思うと、人生はあまりにも（以下略。