大学のデータ構造とアルゴリズムのクラスでは、論文で提示されたアルゴリズムを実装する必要があります。論文はここにあります。だから私はアルゴリズムを完全に実装しましたが、まだいくつかのエラーが残っています（しかし、それが私がこの質問をしている理由ではありません。これまでの実装方法を確認したい場合は、ここで見つけることができます）
Stackoverflowについて質問する本当の理由は、割り当ての2番目の部分です。アルゴリズムを改善する必要があります。私はいくつかの方法を考えていましたが、それらはすべて理論的には良いように聞こえますが、実際には実際にはうまくいきません。
- ソースノードとエンドノードの間に線を引き、その線の中央に最も近いノードを検索し、「パス」を再帰的に2つに分割します。基本的なケースは、単一のダイクストラが計算を行う場合、より小さなグラフになります。これは実際には現在のアルゴリズムの調整ではありませんが、これが最適なソリューションを提供しないことは明らかであると考える人もいます。
- エンドノードを指すエッジに高い優先度を与えることにより、アルゴリズムに方向性を与えるようにしてください。これも最適ではありません。
だから今、私はすべてアイデアがなく、ここの誰かが私に可能な調整のための少しのヒントを与えることができることを望んでいます。アルゴリズムを実際に改善する必要はありません。彼らが私たちにこれを行うように頼んだ最初の理由は、背後にあるものを知らずに論文からアルゴリズムを実装するだけではないからだと思います。
（Stackoverflowがこの質問をするのに適切な場所でない場合は、お詫びします:)）
アルゴリズムの簡単な説明：アルゴリズムは、どのノードが有望に見えるかを選択しようとします。約束するということは、彼らが最短経路に横たわる可能性が高いということです。ノードがどの程度有望であるかは、その「リーチ」によって表されます。パス上の頂点の到達範囲は、始点と終点までの距離の最小値です。グラフ内の頂点の到達範囲は、すべての最短経路での頂点の到達範囲の最大値です。ダイクストラのアルゴリズムでノードが優先キューに追加されているかどうかを最終的に判断するために、test（）関数が追加されています。
Harm De Weirdt