ダイクストラはめ込みから離散物理とマンダラの圏へ - (保存用) 檜山正幸のキマイラ飼育記 メモ編
計算のマンダラ圏を昔から考えていた。いろいろな定式化があるが（そもそも、多数のマンダラがあるだろう）、それが二重圏や半環圏である可能性が高い。 最近、必要があって明瞭オートマトンを考えて、ホイヘンス原理に従いダイクストラ波動に沿ってはめ込みを構成した。はめ込みとは、局所的には単射だが、全域的には単射性を要求しない写像。ラベル付きグラフ（正確には、辺ラベル付き有向グラフ）とは、台であるグラフ（underlying graph）に、半環係数の1-形式（1-ラベリング）を与えたものだと思って良い。1-形式が力学系の生成元を与えるので、ラベル付きのグラフは、力学系が載っている離散空間だと思って良い。この力学系の長時間挙動は、生成行列の指数関数＝プロパゲータ＝クリーネスターで与えられる。 PropA(n; j←i) = (1 + A)n[j, i] 時間的に効果が蓄積する場合の伝搬記述 ダイクストラ
フーム、驚いた、もろに離散物理 - (保存用) 檜山正幸のキマイラ飼育記 メモ編
最近、Catyでの必要性から、明瞭正規表現と明瞭オートマトンつう概念を考えて、その同値性とか包含関係とかを考えていたが、離散物理とかDFD（Discrete Field Dynamics）とかに関係する、つうか、離散物理そのものだということが分かって驚いている。 言語の包含関係（正規表現型のサブタイプ関係）を示すために、決定性オートマトンの包含関係を調べるのだが、このとき2つのオートマトンのあいだに模倣対応関係（ラベル付きグラフの圏の射）を構成する。2つのオートマトン上で同時にダイクストラ法を実行する。ダイクストラ法で区別が付かないなら、同値なオートマトンである。 ダイクストラ法 http://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95 ベルマン-フォード法 ht
離散物理としてのグラフ理論 - (保存用) 檜山正幸のキマイラ飼育記 メモ編
有本さんの本は、深谷さんとの対談だけ読んでほっておいたが、すごく面白いことが書いてある。第2章「最適化とアルゴリズム」の最初を読んで「ホエーッ」と感心。しばらく、このあたり（以下に書く）を調べて考えてもいいと思った。 光の粒子性と波動性という話は、量子力学を持ち出さなくても、古典幾何光学のレベルでもモノスゴク面白い。有本さんによると、フェルマーの原理（変分原理）とホイヘンスの原理に対して、ベルマン（Bellman）の原理（最適性の原理; Principal of Optimality）とダイクストラのアルゴリズムが対応するそうだ。 ダイクストラのアルゴリズムは、波頭集合（ウェーブフロント）を追いかける方式になっている。測地線を求めるときなどは距離の三角不等式が成立しているから「急がば回れ」があり得ないが、局所距離とは限らない一般的コスト関数では「急がば回れ」がある。そのため、波頭が目的地に
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
