ダイクストラ波動
ダイクストラ波動はグラフ(通常は有限グラフ)上を走る波動だが、連続現象の波動とは違う特徴を持つ。
- アルゴリズム時間=ステップ数 に沿って進行する。
- アルゴリズム時間は現象時間とは異なる。そもそも現象時間がないときもある。
- アルゴリズム時間は、あくまでアルゴリズムを遂行する上での便宜的なパラメータ。
- アルゴリズムの目的は、「最適経路=フェルーマー原理の経路=変分法の極値」を求めることである。
- 経路のステップ長さと距離(またはコスト)は違う概念になる。
- 波頭集合と掃過域集合は通常のように定義できる。
- しかし、特定の空間点(配位空間=頂点集合の要素)と別な空間点を結ぶ最短経路が初波の通過によって与えられるとは限らない。
- 大きなステップ数のほうが短い距離(コスト)のときがある。 よって、初波(の波頭)が通り過ぎた後からの後続波が最適経路を含むことがある。
- 最短経路と最短距離が確定した点の集合を確定集合と呼ぶと、掃過域集合と確定集合は違うことがある
- 掃過域集合内に、未確定集合が含まれるかもしれない。
- 確定集合と未確定集合の性質を調べることが大事。
- ダイクストラ波は、経路の集合の上にもダイナミズムを与える。
- 極値は、サイクルを持たない経路で与えられる。有限グラフでは、サイクルを持たない経路は有限個しかない。