最短経路検索 Dijkstraを攻撃的にするには・・・

ここ数ヶ月、どっぷりDijkstraを使った経路検索に浸かっているんですが、どうも、保守的過ぎるんだよな。このDijkstra法とはどういうアルゴリズムかというと、要するに最も近い（正確にはコストが低い）ところから順に辿っていき、目的地に到達するというもの。これを分かりやすく、家から会社への道順に例えて言うと、まず家を出ると左右に道があるとする、まず左から進むと、すぐに交差点にぶつかり、次に右へ出ると、T字路にぶつかる。この時点で次に調べるべきは、交差点の３本と、T字路の２本となるわけだ。これらのうちで、家からの距離が最も近いのが交差点を左折する道だとすると、次はそれを調べることになる。こうして、コストが最も低いものから順にどんどん調べていって、目的地に到達する、というアルゴリズムなのです。

単純に距離だけをコストにすると、これは出発地から同心円上に検索が広がっていきます。つまり東京から名古屋へ行くには、同時に仙台の方も入念にチェックするという具合なのです。もちろんこれではあまりに現実的ではないので、実際にはいろんな要素をコストにします。

ただどうも、このアルゴリズムの血筋は変えられないもので、「出発地からのコストが低い順に探索する」という特性はどうにもならないわけです。これはどういうことかというと、もう名古屋インターを降りてもう目的地、という時に、依然として出発地の近所のコンビニ付近も念のためチェックするという、これ以上ないというぐらいの念の入れようなわけです。

この保守的なDijkstraに、どうしたら攻撃的な血を入れられるのか・・・。もっともっと一気に目的地に突っ走ってしまうやつ。それでいて、保守的なDijkstraの性質もあるので探索にコケルようなことはないもの。昨夜から頭を離れないアイデアがある。ひとつやってみるか。