問題タブ [shortest]

ダイクストラ以外のほぼ完全なグラフの最短経路を計算する別の方法はありますか? 約 8,000 のノードと約 1,800 万のエッジがあります。私はスレッド「マップ上の a から b」を調べて、Dijkstra を使用することにしました。Boost::Graph ライブラリを使用して Perl でスクリプトを作成しました。しかし、結果は私が期待したものではありません。呼び出し $graph->dijkstra_shortest_path($start_node,$end_node); を使用して 1 つの最短パスを計算するのに約 10 分以上かかりました。

エッジがたくさんあることは理解していますが、それが実行時間が遅い理由かもしれません。私は水の中で死んでいますか？これを高速化する他の方法はありますか？

2D平面にはn個の点があります。ロボットはそれらすべてを訪問したいのですが、水平または垂直にしか移動できません。それがカバーする総距離が最小になるように、どのようにそれらすべてを訪問する必要がありますか？

mysqlの正規化された隣接リストを使用して加重グラフを設計しました。次に、指定された2つのノード間の最短パスを見つける必要があります。

私はPHPでダイクストラを使おうとしましたが、それを実装することができませんでした（私には難しすぎました）。私が感じたもう1つの問題は、ダイクストラを使用する場合、すべてのノードを考慮する必要があるということでした。これは、大きなグラフではおそらく非常に非効率的である可能性があります。それで、誰かが上記の問題に関連するコードを持っていますか？少なくとも誰かがこの問題を解決する方法を教えてくれたら素晴らしいと思います。私はここでほぼ一週間立ち往生しています。助けてください。

与えられた有向非重み付けグラフで2つのノード間のすべての最短経路を見つける必要があるという問題に取り組んでいます。私はBFSアルゴリズムを使用して作業を行いましたが、残念ながら、すべてではなく1つの最短パスしか印刷できません。たとえば、長さが3の4つのパスの場合、アルゴリズムは最初のパスのみを印刷しますが、すべてを印刷したいと思います。 4つの最短経路。次のコードで疑問に思っていたのですが、2つのノード間の最短パスをすべて出力できるように変更するにはどうすればよいですか？

私はあなたのすべての大きな助けに感謝しますありがとう、アンドラ

問題の最短経路または最適/最適な解決策を見つけることについて話している多くのアルゴリズムとアプローチを見つけました。しかし、私がやりたいのは、ある点から別の点への最初の K 最短経路を見つけるアルゴリズムです。私が直面している問題は、ツリーを検索するようなものです。各ステップで、それぞれに重みのある複数のオプションがある場合です。この種の問題に直面するために、どのような種類のアルゴリズムが使用されていますか?

いくつかの都市とそれらの間の距離を保存してから、最短経路を検索する必要があります。都市と距離はファイルから読み取られます。マトリックスの作成から始めましたが、スペースが多すぎる（2倍以上）ことがわかったので、リストに変更しました。各リスト項目には、point1、point2、およびそれらの間の距離の 3 つが格納されます。

たとえば、次のファイルがあります。

アテネ ストックホルム 34
ストックホルム プラハ 23

私が読んだとき、これは次のように配列に格納されます：

それから私はいくつかの疑問を抱きました..これは確かにスペースを節約しますが、通過するのにもっと時間がかかりますか? リストは配列ですが、接続（エッジ）は任意の方法で配置されているため、マトリックスを使用する場合よりも時間がかかる可能性があると考え始めました。

このプログラムは、左から右への最短経路の重みを 2 次元配列で返す必要があります (上と下をまたぐことができるため、水平の円柱のようなものです)。(ここに完全なquestion_linkがあります)配列内で最初に上に移動し、次に右に移動し、最後に下に移動して、再帰的にチェックしようとしています。このプログラムを実行すると、行の右方向と下方向のコメントを外すと、「セグメンテーション違反」が発生します。誰かが私の再帰関数で間違っていることを教えてくれれば。前もって感謝します！

私の特定のケースでは、グラフは隣接リストとして表され、無向でスパースです。nは数百万単位で、dは3です。A^ d（Aは隣接行列）を計算し、ゼロ以外を選択します。エントリは機能しますが、行列の乗算を含まないものが必要です。すべての頂点の幅優先探索もオプションですが、時間がかかります。

最短の文字列を見つける方法、最初に返されるはずの文字列

私はこの弦を持っています。td を閉じる blabla を値に含む td を探しています。例：

この文字列だけが欲しい

私は.netでこの正規表現を使用しています

私は正規表現が初めてです...

だれか抜け道を教えてくれませんか。

A*アルゴリズムの実装についてサポートが必要です。アルゴリズムを実行すると、目標は見つかりますが、パスは間違いなく最短ではありません:-P

これが私のコードです。バグを見つけるのを手伝ってください！私の問題は再構築パスかもしれないと思いますが、よくわかりません。

}

すべての素晴らしい答えをありがとう！私のA*アルゴリズムは、皆さんのおかげで完全に機能するようになりました。:-)

これは私の最初の投稿であり、このフォーラムは本当に素晴らしいです！