最短経路アルゴリズムへの調整

Question

データ構造&アルゴリズムクラスの大学では、論文で提示されたアルゴリズムを実装する必要があります。この用紙はhereです。 私は完全にアルゴリズムを実装しましたが、まだいくつかのエラーが残っています（しかし、それはなぜ私がこの質問をしているのかを知りたいのであれば、hereです）

私がStackoverflowの質問をする理由は、割り当ての第二の部分です：私たちはアルゴリズムをより良くしようとする必要があります。私は心の中でいくつかの方法があったが、それらのすべてが理論的には良い音が、彼らは本当に実際には良いしないだろう。

• は、中央に最も近いノードを検索し、ソースとエンドノード間に線を引きます再帰的に2で "経路"を分割します。基本ケースは、単一のダイクストラが計算を行うという小さなグラフになります。これは現在のアルゴリズムの調整ではありませんが、考え方によっては最適な解決策が得られないことは明らかです。
• エンドノードを指すエッジに高い優先度を与えることで、アルゴリズムに方向感を与えようとします。これも最適ではありません。

ここで私はすべてのアイデアがなく、ここの誰かが私に可能な調整のヒントを与えてくれることを願っています。実際にはアルゴリズムを改善する必要はありませんが、私たちはこれを行うように頼んだのは最初の理由だと思います。なぜなら、背後にあるものを知らずにアルゴリズムを実装するだけではありません。 （stackoverflowのは、この質問をするために適切な場所ではない場合、私の謝罪:)）

は

アルゴリズムの簡単な説明： アルゴリズムは、ノードが有望に見えるかを選択しようとします。約束することによって、私は彼らが最短の道に横たわって良いチャンスを持つことを意味します。どのようにノードが有望であるかは、その「到達」によって表されます。パス上の頂点の到達距離は、開始点と終了点までの距離の最小値です。グラフ内の頂点の到達範囲は、最短のすべての経路上の頂点の到達範囲の最大値です。 最終的に、ノードがDijkstraのアルゴリズムで優先度キューに追加されているかどうかを調べるために、test（）関数が追加されました。テストは真を返します（グラフ内の頂点のリーチが、vが優先キューに挿入されるときの原点からvへのパスの重みより大きい場合、または等しい場合）。グラフはvから終点までのユークリッド距離よりも大きいか等しい）。

害デWeirdt

Answer 1

このようなケースではあなたの最善の策は、研究者のように考えることです。一般的に研究し、コンピュータサイエンスの研究は、特に漸進的な改善についてです、一人は、彼らがダイクストラのアルゴリズムを使用してより高速なものを計算することができることを示し後で彼らや他の人は、A *を使って同じことを少し速く計算できることを示しています。これは一連の小さなステップです。

つまり、論文のアルゴリズムを改善する方法を探すのに最適な場所は、今後の方向のセクションです。このペーパーでは、その方向で少し作業をしていますが、この場合の金鉱はセクション5とセクション6にあります。作者がさまざまな考え方を認めている場所は複数あります。これらのアプローチのいくつかを研究してみると、アルゴリズムの可能性のある改善または少なくとも議論の余地のある改善のいずれかにつながるはずです。 運が良かった！