離散物理としてのグラフ理論
有本さんの本は、深谷さんとの対談だけ読んでほっておいたが、すごく面白いことが書いてある。第2章「最適化とアルゴリズム」の最初を読んで「ホエーッ」と感心。しばらく、このあたり(以下に書く)を調べて考えてもいいと思った。
光の粒子性と波動性という話は、量子力学を持ち出さなくても、古典幾何光学のレベルでもモノスゴク面白い。有本さんによると、フェルマーの原理(変分原理)とホイヘンスの原理に対して、ベルマン(Bellman)の原理(最適性の原理; Principal of Optimality)とダイクストラのアルゴリズムが対応するそうだ。
ダイクストラのアルゴリズムは、波頭集合(ウェーブフロント)を追いかける方式になっている。測地線を求めるときなどは距離の三角不等式が成立しているから「急がば回れ」があり得ないが、局所距離とは限らない一般的コスト関数では「急がば回れ」がある。そのため、波頭が目的地に到着しても“回り込んで(遠回りして)”伝搬する別な波頭とのコスト比較がありえる。
局所三角不等式、測地線、ほんとの最短経路、距離などの意味を再認識できる。
光や音の場合、衝撃による球面波を一種のアトム(基本要素)と考えて、球面波の重ね合わせで一般の波(特に平面波)が合成できる。ある一点での波の影響は、すべての波源(衝撃の発生地点)の影響を積分するばよい。
この“積分”の対応物は、フロイド/ウォーシャル・アルゴリズムになっている。僕が以前から興味を持っていた、行列絵算(pictorial matrix calculation)がフロイド/ウォーシャル計算と同じだ(絵を使うが)。これは、ファインマンの経路積分と似ているし、クリーニ(クリーネ)・スターの計算にも使える(僕は、ファインマン/クリーネの経路和公式と呼んでいる)。
波頭集合は、媒質空間内で超局面(の族)となる。この超局面族に直交する曲線族をとると、それが(粒子的な)光の進行経路となる。ホイヘンスの原理で局所的に積み上げた波頭集合に対する直交経路が、結果的に変分原理を満たすってところが面白い。さらに、経路に沿った総和が遠隔作用を与える。
光や音のモデルは、競争(ゲーム)やウィルスの感染などとも通じる。コストとなるスカラーをマックス・プラス代数を取ると、最適化に便利。これがまたトロピカル幾何に繋がったりする。ここらのことは『差分と超離散』にも少し出ていた。
- ホイヘンス(Huygens; ハイゲンス)「光についての論考」(ライデン, 1690年, 初版)http://www.kanazawa-it.ac.jp/dawn/169001.html
- Vaughan Pratt, ENRICHED CATEGORIES AND THE FLOYD-WARSHALL CONNECTION (April, 1989) - http://boole.stanford.edu/pub/am4.pdf
- ワーシャル-フロイド法 - Wikipedia - http://ja.wikipedia.org/wiki/%E3%83%AF%E3%83%BC%E3%82%B7%E3%83%A3%E3%83%AB-%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E6%B3%95
- C++によるFLOYD-WARSHALL法の記述 http://www.prefield.com/algorithm/graph/floyd_warshall.html
- Exotic Semirings - http://d.hatena.ne.jp/m-hiyama-memo/20060622/1150962733
- Yetterの線形代数と行列計算 - http://d.hatena.ne.jp/m-hiyama-memo/20070427/1177658550