問題タブ [shortest-path]

私は頭がおかしくなっているか、A* アルゴリズムを誤って実装しているようです。

以下は私のコードです。入力した値に関係なく、常に 360 が返されるようです。重要な情報が欠落していませんか? また、誰かが「はい」と尋ねる前に、これは私が受けた機械学習の課題に関連しています。

public class A_Star {

}

と

public class SearchNode {

public SearchNode(int cost, int xCoordinate,int yCoordinate){
this.cost=cost;
this.xCoordinate = xCoordinate;
this.yCoordinate = yCoordinate;
}
public int getCost() { コストを返します。}

}

「アルゴリズムの概要、第3版」の演習24.3-5では、これが間違っている（常に正しいとは限らない）例が必要です。それは可能ですか？私の考えでは、現在の頂点へのパスがすでに決定されているときにすべてのエッジが緩和されるため、これは不可能です。

一言一言：

N教授は、ダイクストラのアルゴリズムが正しいことを証明していると主張しています。彼は、ダイクストラのアルゴリズムは、グラフ内のすべての最短パスのエッジを、パスに表示される順序で緩和するため、パス緩和プロパティは、ソースから到達可能なすべての頂点に適用されると主張しています。ダイクストラのアルゴリズムが最短経路のエッジを順不同に緩和できる有向グラフを作成して、教授が間違っていることを示します。

だから私はGoogle Maps APIをいじるためにjavascriptを学んでいます。私が直面しているこの問題に対するエレガントな解決策を誰かが持っているかどうか疑問に思っていました。

Google マップのルート リクエストには、origin、destination、travelMode の 3 つが含まれている必要があります。私のtravelModeは常にDRIVINGです。オリジンは、常にユーザーがいる場所です。

ただし、宛先は変更する必要があります。私はいくつかのウェイポイントを持っており、ユーザーが訪問し、選択されたウェイポイントとユーザーがどこにいるかに応じて、可能な限り最短の旅行を提供したいと考えています。 ..バツ）。

すべての可能なパスを計算し、最短距離 (または時間、または私が評価しているもの) を持つものを確認する以外に、これを行う方法はありますか? それは法外にコストがかかるようです (O(n!))。

編集: 提案された optimizeWaypoints フラグを true に設定すると、これは O(n!) ではなく O(n) の問題になりますが、短期間にあまりにも多くのリクエストを発行するという問題があります。

フィボナッチ ヒープを使用したダイクストラの実装を考案しようとしています。私が理解しようとしているのは、O(logn) (削除あり) の最小距離以外に、特定のノードの隣接ノードを表すことができるかどうかです。それとも、これはフィボナッチ ヒープ構造に違反していますか? そうしないと、隣人リストとフィボナッチ ヒープを作成する必要があります。

Dijkstra のアルゴリズムと Floyd-Warshall アルゴリズムについて調べています。Dijkstra は 1 つのノードから他のすべてのノードへの最適なルートを見つけ、Floyd-Warshall はすべてのノードのペアリングの最適なルートを見つけることを理解しています。

私の質問は、すべてのペアリング間の最適なルートを見つけるために、すべてのノードで実行すると、ダイクストラのアルゴリズムがフロイドのアルゴリズムよりも効率的であるかということです。

Dijkstra の実行時間は O(E + VlogV) で、Floyd の実行時間は O(V ³ ) です。ダイクストラが失敗した場合、この場合のランタイムはどうなるでしょうか? ありがとう！

オープン ストリートマップ プロジェクトからいくつかの事実をダウンロードしました。ここからダウンロードできますhttp://www.mediafire.com/?15pttpp847ld71x このプログラムは、ユーザーがある場所から別の場所への旅程を取得し、最短ルートを提供するのに役立ちます。パスを検索するためにダイクストラのアルゴリズムを実装する方法を誰かが教えてくれます。また、この述語を念頭に置いていました -compute_path(User, Start , End, PathNodes) ここで、User は amsterdam.pl のユーザー値と一致します運転手、 ...）。Prolog は、適切なルートを構築するときにこの情報を考慮に入れます。たとえば、サイクリストは高速道路を使用できません。· ユーザー指定の場所を明示的に訪問する出発地と到着地の間の旅程を要求できるようにします (つまり、ユーザーは A から B 経由で C に行きたいと指定できます)。· Prolog に、「午前 10 時にアムステルダムの B 地点に行くには、A 地点を何時に出発すればよいですか?」などの情報を尋ねることができるようにします。· ユーザーが次のような入力を使用してシェルと対話できるように、あなたが作成したようなヒューマン ランゲージ インターフェイスを使用します。これを実装するために、私はとても感謝しています.Prologの初心者であり、速い学習者になろうとしています.

これは私が思いついたコードです

私の事実がプロローグデータベースでどのように見えるべきかを決めることはできません...そして私の割り当ては、この問題を解決するために私が考えている2つの地下鉄駅間の最短経路を与える述語を書くことですが、私が困っているのは効率的に表現する方法です路線の駅なので、アイデアと共有するものがあれば、やってください:)とthx

グラフ内のノード間の最短経路は、いくつかのアルゴリズム（Dikstra、A-starなど）によって見つけることができます。

しかし、この問題にはどのようなアプリケーションがありますか？（私はすでにかなりの数を知っていますが、もっと多くの例を見たいと思います）。

応募/回答は1つだけお願いします！アプリケーションと、それを最短経路問題に変換する方法を説明します。

双方向グラフのプロローグで駅Aから駅Bへの最短ルートを見つけたいと思います（AがBに接続されている場合、BがAに接続されている場合）、グラフには枝に重みがありません。質問はこのように投稿されます

始発駅。
終着駅。
最短ルートで通過したすべてのステーションのパス リスト。グラフ内の任意の 2 つの直接接続ステーション間の距離は等しくなります。実際、ベースは次のようになります。

地下鉄路線は、2 つの駅を直接結ぶ路線の数です。2 番目と 4 番目の引数が同じ場合、ステーションは直接接続されます。

編集:私は問題を解決しようとしましたが、BFS を使用するとより速く動作することがわかりました。
ここに私が書いた解決策があります：

?-宛先ノードへ
のパスを含むリストである必要があります 唯一の問題は、宛先ノードへのパスを返す方法がわからないことです。
ありがとうございます。

大学のデータ構造とアルゴリズムのクラスでは、論文で提示されたアルゴリズムを実装する必要があります。論文はここにあります。だから私はアルゴリズムを完全に実装しましたが、まだいくつかのエラーが残っています（しかし、それが私がこの質問をしている理由ではありません。これまでの実装方法を確認したい場合は、ここで見つけることができます）

Stackoverflowについて質問する本当の理由は、割り当ての2番目の部分です。アルゴリズムを改善する必要があります。私はいくつかの方法を考えていましたが、それらはすべて理論的には良いように聞こえますが、実際には実際にはうまくいきません。

• ソースノードとエンドノードの間に線を引き、その線の中央に最も近いノードを検索し、「パス」を再帰的に2つに分割します。基本的なケースは、単一のダイクストラが計算を行う場合、より小さなグラフになります。これは実際には現在のアルゴリズムの調整ではありませんが、これが最適なソリューションを提供しないことは明らかであると考える人もいます。
• エンドノードを指すエッジに高い優先度を与えることにより、アルゴリズムに方向性を与えるようにしてください。これも最適ではありません。

だから今、私はすべてアイデアがなく、ここの誰かが私に可能な調整のための少しのヒントを与えることができることを望んでいます。アルゴリズムを実際に改善する必要はありません。彼らが私たちにこれを行うように頼んだ最初の理由は、背後にあるものを知らずに論文からアルゴリズムを実装するだけではないからだと思います。

（Stackoverflowがこの質問をするのに適切な場所でない場合は、お詫びします:)）

アルゴリズムの簡単な説明：アルゴリズムは、どのノードが有望に見えるかを選択しようとします。約束するということは、彼らが最短経路に横たわる可能性が高いということです。ノードがどの程度有望であるかは、その「リーチ」によって表されます。パス上の頂点の到達範囲は、始点と終点までの距離の最小値です。グラフ内の頂点の到達範囲は、すべての最短経路での頂点の到達範囲の最大値です。ダイクストラのアルゴリズムでノードが優先キューに追加されているかどうかを最終的に判断するために、test（）関数が追加されています。

Harm De Weirdt