DAG-Shortest-Paths algorithm (有向非巡回グラフ 最短路アルゴリズム)。有向非巡回グラフ(DAG: Directed Acyclic Graph)の最短路を求めるアルゴリズム。 DAG G =(V,E)のEdgeに対し次の操作を行う：1. DAG G に対し、Topological sortを行い、 線形順序を与…

Bellman-Ford Algorithm (ベルマン・フォード アルゴリズム)。 "負の重みの辺を許す"一般的な、 Single-Source Shortest-Path Problem (単一始点最短路問題)、を解くことができる。 "始点から到達可能な負の重みを持つ閉路が存在するかどうか"の判定も行う。…

Relaxation (緩和法)。 各Vertexの最短路重みの上界： d[v] 各vertex v∈V に関し、始点 sから、vへの最短路の重みに関する 上界 d[v]を、vertexの属性として管理する。 d[v] ：最短路の推定値(shortest-path estimate) 初期化：Initialize-Single-Source(G,s…

"Shortest-Path Problem (最短路問題)"とは、 "最短路(shortest path)"を求める問題。 『vertex(頂点) u からvertex vへの最短路』とは 『経路重みが、最短路重みに等しい経路』。 。 ※ここで、"辺重み","経路重み", "最短路重み"の定義は以下：[辺重み] Edg…

Topological Sort (トポロジカル ソート)： Directed Acyclic Graph（DAG：非循環有向グラフ) G=(V,E)に対し、 全vertexに対する線形順序で、G が edge (u, v) を含んでいれば、線形順序の中で uがvより先に現れる形へのVertex Sort。 Topological-Sort(G) 1…

Depth-First Search (深さ優先検索). (Reference："Introduction to Algorithms, Second Edition") 可能ならば常に"より深く"、グラフを探索する。 未探索の edge(辺) が残されている vertex(頂点) の中で、最後に発見した頂点vのedgeを探索。vのedge全て全…

Edward F. Moore の Breadth First Seach Algorithm。[Original]Edward F. Moore, "The shortest path through a maze": Proceedings of the International Symposium on the Theory of Switching, pages 285-292 Harvard University Press, 1959. Algorithm…

最近、"新しいクラス"のグラフ理論(Graph Theory)の構築／取扱いを進行。 それに関連し、共有のため、 離散数学／グラフ理論／組合せ最適化、等、の基礎や関連Topicsも紹介していこうと思います。

本日のジョッギングは、浅草まで。１時間ほど。雷門、朝日ビールビルなど、生まれて初めて浅草に行った(写真は朝日ビールビル)。 道沿いにあるお店も、いくつか素敵。 また走りに行き、見てみよう。

MESA (Manufacturing Execution System Association)から、 2008/03/25に出された"MES Product Report 2007/2008"を、読み進める。[MES Product Report 2007/2008]： http://www.mescc.com/mes-report.html MESA Internationalは、1992年、MES(Manufacturing…