問題タブ [shortest-path]

この有向グラフに 、すべてのペアの最短経路アルゴリズム（Floyd-Warshall ）を適用しています。

グラフは隣接行列で表されます。単純なコードは次のようになります。

}

上記は、アルゴリズムに関する限り正常に機能します。

ここで隣接行列を使用することで示されるように、任意のノードからそれ自体へのパスが必ずしもそうではない0ことを示しようとしていますが、他のノードを通る任意の可能なパスである可能性があります。B -...-...-...-B

B現在の表現を変更して、たとえばからへの最短経路Bがゼロではなく12、ルートをたどることを示す方法はありB-C-E-Bますか？隣接行列法をどうにかして修正することでそれを行うことができますか？

幅優先、全ペア (フロイド)、ダイクストラのように、グラフまたはグリッド内の 2 点間の最短経路を計算するために多くのアルゴリズムが利用できることを知っています。

しかし、私が気づいたように、これらのアルゴリズムはすべて、関心のある 2 点間のパスだけでなく、そのグラフまたはグリッド内のすべてのパスを計算します。

私の質問は: グリッド、つまり 2 次元配列があり、P1 と P2 などの 2 点間の最短経路を計算することに関心があり、グリッド上を移動できる方法に制限がある場合 (たとえば、斜めのみ、または斜めと上向きのみなど)、どのアルゴリズムがこれを計算できますか?

回答がある場合は、アルゴリズム自体ではなくアルゴリズムの名前を投稿していただきたいことに注意してください (もちろん、アルゴリズムも投稿するとさらに良いでしょう)。たとえば、それがダイクストラのアルゴリズムであるか、フロイドのアルゴリズムであるか、またはその他のものであるかどうか。

私を助けてください、私はこれについて何ヶ月も考えてきました!

わかりました、TOPCODER.COM でこのアルゴリズムを見つけました。ここのグリッドでは、(斜め上に) しか移動できませんが、これがどのようなアルゴリズムなのか理解できません。

私は次のプログラミングコンテストのために練習してきましたが、私は完全に当​​惑している質問に出くわしました。しかし、それは決して思い浮かばないということで、指を交差させるのではなく、今学ぶべき概念だと感じています。

基本的には、チェス盤の騎士の駒を扱います。開始位置と終了位置の2つの入力が与えられます。次に、目標の場所に到達するために騎士がたどることができる最短経路を計算して印刷することが目標です。

私は最短経路のようなものを扱ったことがなく、どこから始めればよいのかさえわかりません。これに取り組むために私はどのような論理を採用していますか？

PS関連性がある場合は、騎士の通常の動きを補うために、騎士が行うことができる（潜在的に）8つの動きによって形成される正方形の四隅に移動できるようにする必要があります。騎士の場所。

任意の開始ノードから最短の歩行距離を見つけて、すべてのノードが重みのある無向グラフで訪問されるようにするアルゴリズムまたはアルゴリズムのセットはありますか？ノードが複数回訪問されてもかまわないので、巡回セールスマンではありません。（最初に戻っても問題ありません。すべてのノードを訪問するのに最後に必要なノードである限り、ウォーカーは遠くのノードに到達する可能性があります。）これは最小スパニングツリーではありません。 A-> B-> C-> A-> Dに行くことは、A、B、C、およびDを訪問するための（一意ではない）最短経路である可能性があるためです。私の直感では、これはそうではないと言っています。 NP問題をそれほどトリッキーにする制限がないため、かなりNP問題です。もちろん、私は完全に間違っている可能性があります。

約70kのノードと250kのエッジがあり、グラフは必ずしも接続されていません。明らかに、効率的なアルゴリズムを使用することが重要です。おすすめは何ですか？

ちなみに、タスクを複数のマシンに分割する方法についてアドバイスをいただければ幸いです。この種の問題でも可能ですか？

ありがとう

これは、非機能的な方法で簡単に解決できる問題です。

しかし、Haskell でそれを解決すると、大きな問題が発生します。関数型プログラミングに関しては、私が未経験であることは確かに理由です。

問題：

同じサイズの長方形に分割された 2D フィールドがあります。シンプルなグリッド。一部の長方形は空のスペース (通過可能) ですが、他の長方形は通過できません。開始長方形Aと宛先長方形Bが与えられた場合、2 つの間の最短経路をどのように計算しますか? 移動は垂直方向と水平方向にのみ可能で、ステップは 1 つの長方形を大きくします。

Haskellでこれを達成するにはどうすればよいですか? コード スニペットは確かに歓迎されますが、必須ではありません。また、その他のリソースへのリンクも大歓迎です。

ありがとう！

10点あるとします。各ポイント間の距離を知っています。

すべてのポイントを通る最短ルートを見つける必要があります。

いくつかのアルゴリズム (Dijkstra、Floyd Warshall など) を試してみましたが、それらはすべて開始点と終了点の間の最短経路を提供してくれますが、すべてのポイントを含むルートを作成するわけではありません。

順列は問題なく機能しますが、リソースを大量に消費します。

この問題を調べるために、どのアルゴリズムをアドバイスしてもらえますか? または、上記のアルゴリズムでこれを行う文書化された方法はありますか?

2 つのノード間のグラフ内のすべてのパスと最短パスを検索するターボ プロローグのコードに問題があります。私が抱えている問題は、ノードがリストにあるかどうかをテストすることです(正確にはメンバーの節にあります)

これは私のコードです:

私は、ダイクストラアルゴリズムのCでのこの実装を理解しようとしていたと同時に、2つの特定のノード（送信元と宛先）間の最短パスのみが見つかるように変更しました。

しかし、私は正確に何をすべきかわかりません。私の見方では、何もすることはありません。これらの配列を変更しd[]たり、最短経路計算のためにいくつかの重要なデータを集約したりすることはできないようです。prev[]

私が考えることができる唯一のことは、パスが見つかったときにアルゴリズムを停止することです。つまり、mini = destination訪問済みとしてマークされたときにサイクルを中断します。

それを改善するために私ができることは他にありますか、それともそれで十分ですか？

編集：
私に与えられた提案に感謝しますが、人々はまだ私が質問したことを正確に答えることができません。私が知りたいのは、2つのノード間の最短パスのみを検索するようにアルゴリズムを最適化する方法です。今のところ、他のすべての一般的な最適化には興味がありません。私が言っているのは、ノードXから他のすべてのノードへのすべての最短パスを見つけるアルゴリズムで、特定のパスのみを検索するように最適化するにはどうすればよいですか？

forPS：ループが1までで始まることに気づきましたが<=、なぜそれがで始まり、まで続くことができないの0です<か？

有向の正の重み付きグラフがあります。各エッジには使用コストがあります。私はAのお金しか持っていません。ダイクストラアルゴリズムを使用して最短経路を計算したいのですが、ルート上のエッジコストの合計はA以下でなければなりません。

最小のダイクストラ修正でこれを実行したいと思います（ダイクストラの小さな修正で実行できる場合）。できればこれをしなければなりませんO(n*log(n))が、できると思います。

誰でもこれを手伝ってくれますか？