LostMemories

後輩から、縦型探索をするために有利なグラフの標準形について教えてもらいました。今の研究テーマと少し違っているので、忘れてしまう可能性大。せっかくなので、ここにメモしておきます。

ここに、今から述べるグラフの例を示します。この図に書かれた2つのグラフは、パッと見れば分かると思いますが同じものです。ですが、計算機でグラフを探索する場合は、このような全体像が分かっているわけがないので、あるノードから順番に探索を行っていくことになります。左のグラフでは「B」と書かれたノード、右のグラフでは「A」と書かれたノードから始めることにします。

ここで注意しておきたいのが、グラフの探索方法が縦型であるということ。左側では、「B」→「A」→（「B」）→「C」と探索していくのに対し、右側では「A」→「B」→「C」と探索することになります。縦型探索を行う場合、なるべくならばロールバック（つまり、すでに探索したノードに戻る作業）は発生しない方がいいので、右側のグラフを標準形としたいことになります。

さて、これまでの話を踏まえた上で、標準形を選び出すための表記方法を述べます。上図のように、探索する順番がすでに最後まで分かっていて、それをノードの番号とします。その上で、１つの新しいノードに到達する探索工程を１単位と定めます。１単位での表記法は、「（ノード番号）（全体のノード数 - そのノードとつながっている探索済みのノード番号）」です。このように表記し、昇順に並べたときに最も先頭に来るものが標準形とします。左のグラフでは「22 32」、右のグラフでは「22 31」となり、右のグラフが標準形になります。