最短経路問題を解く自己安定アルゴリズム

点击翻译按钮获取中文摘要

従来の計算幾何学の分野で扱われている最短経路問題では,出発地点と目的地点が1対1もしくは1対多である場合が多い.また,一般的には、障害物などの状況はアルゴリズムを実行中は変化しないと仮定され,動的に変化する状況を仮定したアルゴリズムの研究は,ほとんど行なわれていない.しかし,刻一刻と道路の状況,天候,事故情報などが変化する自動車会社における交通網に,従来の最短経路を求めるアルゴリズムを当てはめようとすると1.求めたい出発地点と目的地点の組合せが,多対多であるために複数の同じプログラムを同時に実行しなければならない.そのため他のプログラムの計算結果を利用することができない.2.最短経路を求めている間に道路状況が変化すると,せっかく求めた解が意味をもたなくなる.などの問題が生じる.そこで,本研究では,このような問題を解決するために分散アルゴリズムの1分野である自己安定(self-stabilizing)分散アルゴリズムの考え方を計算幾何学の分野に導入することとした.自己安定分散アルゴリズムは,状況が変化しても十分に時間がたてば解が求まるのが特徴である.つまり,状況が変化するまでの時間よりも解の収束が速ければ,最短経路を常に求めることができる.しかし,自己安定アルゴリズムを利用するにあたり,次のような問題点が明らかになった.1.自己安定アルゴリズムは,いつ解が収束したのか判定が難しい.2.解の収束が遅く,たとえ自己安定アルゴリズムが開発されても,現実社会では利用しにくい.今後は,自己安定アルゴリズムより収束が速い実時間システムと呼ばれる手法の導入を考えている.