私は現在、ヨーロッパを経由するためのナビゲーションシステムを実装しています。これまでのところ、最短経路を実装しています（ダイクストラとA *）。それは簡単な部分でした、今私は最速のパスのためにいくつかのアルゴリズムが必要です。それは速くて信頼できるものでなければなりません。
道路の品質（たとえば、高速道路1つ、幹線道路2つなど）に値を割り当て、これらの値にルートコストを掛けて、最終的にダイクストラまたはA *を使用するだけで実行できることはわかっていますが、十分に洗練されていません。
より正確なアルゴリズムを探しています。地図自体には、道路の質、制限速度、信号機の位置など、あらゆる種類のデータが含まれているので、それを利用したいと思います。
これに適したアルゴリズムはありますか？または、少なくともA *の適切な変更ですか？
最短経路の実装では、エッジの重みとして距離を選択しました。
ここで、最速のパスを見つけたい場合は、代わりにエッジの重みとして予想移動時間を選択するだけです。同様に、最も信頼性の高いパスが必要な場合は、エッジの重みとして「信頼性」の測定値を選択します。
A *（ヒューリスティック関数に依存しているため、常に最適であるとは限りません）は、このタイプのアプリケーションにおそらく最適なオプションです。A *の精度が十分でない場合は、ダイクストラ法を使用するか、ヒューリスティック関数の調整と改善に時間をかけることをお勧めします。
それはあなたが「最速の」道によって何を意味するかによります。道路の各セグメントを移動できる平均速度がわかっている場合は、グラフを変換して、エッジに「距離」ではなく「移動にかかる時間」が含まれるようにすることができます。次に、新しいグラフに対して最短経路アルゴリズムを実行できます。
とはいえ、それだけでは不十分だとおっしゃっていたようです。問題は、「最速」の意味を定義する必要があることだと思います。道路の質は速度にどのように影響しますか？信号はどうですか？これらはすべて、説明する方法を見つける必要がある変数です。人間として使用するメトリックがわからない場合は、コンピューターにそれを実行させるのは困難です。