Dijkstraアルゴリズムの最適化課題

JavaOne2007で行ったナビゲーションシステムのデモは、TheServerSide.COMで取り上げられてから日の目を見ていませんが、いろいろ可能性を秘めたものなんです。なによりも大きな可能性というのは、動的な最適化が可能であるということです。

Dijkstraのアルゴリズムというのは、検索対象のノード数をNとすると、基本的にNの2乗に比例して検索時間がかかります。例えば、渋谷駅から、1KMにある原宿と、2KMにある代々木では、検索時間に4倍の差が生じます。純粋Dijkstraは、コストを出発地からの距離とした場合、同心円状に検索が広がるからです。

最適化というのは、このDijkstra基本性能を克服するために行われます。しかしまずこの最適化を進める上で、重要な前提条件があります。それは、「検索品質と検索時間に依存関係がない」、ということです。というのも、もし依存関係がある場合、検索品質（結果ルートの品質）を向上させると検索時間が長くなり、その逆もまたしかり、となって光と影の関係が生じてしまうからです。

検索品質・・・Dijkstraアルゴリズムで存在するコストは、正の値であり、次のノードへのコスト、とだけ定められており、特に距離である必要はありません。ここでは、何らかの品質を示すものとなるでしょう。動的な最適化を行うモデルでは、このコストは検索時に動的に算出されます。具体的には、右左折や道路幅、直進性や信号機など、運転する時に考慮すること、と考えて差し支えないでしょう。

検索時間・・・ここは腕の見せ所ですが、状態遷移モデルを考えています。どういうことかというと、出発地付近（細街路、主要道）、高速、目的地付近（主要道、細街路）というような”状態”が遷移した場合、検索対象となるノードが切り替わる仕組みです。これによって、検索対象ノード数Nを絞り込むことが可能なため、検索時間のコントロールにつながります。これは、ルーターがネットワーク上探索しながら、最終的に目的地にたどり着くような仕組み動きに似ています。たぶん経由地も活用することになるかと。

あまり複雑なモデルでは破綻するため、ある一定量の検索はやむをえないと考えます。しかしながら将来的には、もっと野心的な仕組みを考えることができるかもしれません。それは、過去のデータを生かす仕組みです。例えばあるファミリーカーが通る道というのは、それほどランダムであるはずがありません。となると、好き嫌いといった条件や、過去に同じような条件で走ったルート情報を考慮することによって、提示する経路の品質を向上させることができると思います。

ところで、これは妄想ですが、ウィキペディアのように、地図作れないもんだろうか・・・。