避難経路探索では時系列ネットワーク上の最短路問題を複数回計算する必要がある。時系列ネットワークはいわば、静的な情報なので前処理を用いた高速な探索を行う事ができる。探索時間を短縮する事ができれば、静的な情報をあたかも動的な情報として扱う事ができるだろうと思い、ちょうど良い前処理を探していたのだ。
しかしながら、時空間ネットワークは非常に特殊な構造を持っていて、greedy algorithm でもほぼ最短路が出てしまうため、前処理による高速化は期待できないそうだ。なんでもダイクストラ法を走らせるためのポテンシャルの初期化すらボトルネックになるそうだ。
しかしながら、時空間ネットワークは非常に特殊な構造を持っていて、greedy algorithm でもほぼ最短路が出てしまうため、前処理による高速化は期待できないそうだ。なんでもダイクストラ法を走らせるためのポテンシャルの初期化すらボトルネックになるそうだ。
※コメント投稿者のブログIDはブログ作成者のみに通知されます