問題タブ [dijkstra]

キャンパス周辺 (学生寮、サッカー場など) と建物内 (オフィス、カフェテリアなど) を案内する地図プログラムを作成したいと考えています。それを容易にするのに役立つものはありますか？

別の方法としては、キャンパス周辺のポイントとパスの独自のマップを作成し、道順のパス ファインディングを行う必要があるようです。

編集: 明確にするために、パスの徒歩ルートを生成するために、パスファインディング プログラムに空間認識を追加する方法について知りたいと思っています。例: 廊下に入るパスを許可する 2 つのノードがあるオフィスでいっぱいの廊下の場合、特定のオフィスが一方のノードの左側にあり、別のノードの右側にあるかどうかをどのように知ることができますか?

ダイクストラは、最も多作なコンピューター科学者の1人でした。彼は有名なEWDを書きました。それらすべてを読むことは現実的ではありません。しかし、私たち全員が読まなければならないものがあると思います。

それらのどれが必読ですか？

マリオ AI コンペティションの参加者が何をしているかを見ていましたが、そのうちの何人かは A* (A-Star) Pathing Algorithm を利用して非常に優れたマリオ ボットを作成しました。

( Mario A* ボットの動作のビデオ)

私の質問は、A-Star は Dijkstra と比べてどうですか? それらを見てみると、それらは似ているように見えます。

なぜ誰かが一方を他方よりも使用するのでしょうか? 特にゲームのパスのコンテキストでは?

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

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

正のエッジ重みのみを持つ有向連結グラフを考えると、フィボナッチヒープを使用するダイクストラよりも、2つの頂点間の最短経路を見つけるためのより高速なアルゴリズムはありますか？

ウィキペディアによると、ダイクストラはO（| E | + | V | * log（| V |））にあります（フィボナッチヒープを使用）。

たとえば、実行時間の半分の最適化ではなく、時間計算量が異なるアルゴリズム（O（n * log n）からO（n）への移行など）を探しています。

さらに、以下のアプローチについてのご意見をお聞かせください。

1. すべてのエッジの重みのGCDを決定します。
2. グラフを均一なエッジの重みを持つグラフに変換します。
3. BFSを使用して、指定された2つの頂点間の最短経路を見つけます。

ポイント2の例：
GCDが1であると想像してください。次に、エッジ
A ---> B（エッジの重み3）
を
A-> A'-> A''-> B（エッジの重み1の3倍）に変換します。
この変換には一定の時間がかかり、エッジごとに1回実行する必要があります。したがって、このアルゴリズムはO（| E |）（変換）+ O（| E | + | V |）（BFS）= O（2 * | E | + | V |）= O（| E | + | V |）

私の質問を読むために時間を割いてくれてありがとう、そして私はあなたの時間を無駄にしないことを望みます^^。良い１日を。

次の問題を解決したい：

実行する必要がある都市とそれらの間のジョブを含む DAG があります。仕事は、定義された制限を積載できるトラック用です。トラックの積載量が多いほど、ツアーはより良いものになります。何かをロードするためのジョブもあれば、定義されたものをロードするためのジョブもあります。都市 a から都市 b までは、たとえ仕事がなくても、いつでも車で行くことができます。最後の制限は、トラックのホームがあるため、常に都市 a で開始して a に戻る必要があることです:)

最初に考えたのは、ダイクストラの最短経路アルゴリズムです。それを最長パスの計算に簡単に変えることができました。私の問題は、これらのアルゴリズムはすべて、頂点 a から b への最短または最長のパスを計算するためのものですが、a から a に戻る必要があることです。

私の心にいくつかのキックがありますか？

ご意見ありがとうございます！

マルコ

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

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

ダイクストラは通常、グラフ内の 2 つのノード間の最短距離を見つけるために使用されます。最小全域木を見つけるために使用できますか? もしそうなら、どのように？

編集: これは宿題ではありませんが、古い模擬試験の問題を理解しようとしています。

本当に巨大なa1単語 ( dog、fish、runなど)の配列 ( と呼びましょう) を取得しました。programming

単語のうちのa1どれでも他の単語と組み合わせることができ (たとえば、 and と組み合わせることができますdog) programming、dog-programming文字列が非常に大きくなるまで、何度も何度も組み合わせることができます。

a2また、文字列の配列 ( と呼びましょう) も取得しました ( de、s、x?、などumh、ほとんど何でもかまいません)。a2a1 のどの文字列にも見つからない文字列は存在しないことが保証されています。

私が探しているのは、 内のすべての文字列を含む最短の文字列 (文字列に含まれる文字数ではなく、その文字列を作成するのに必要な組み合わせの数に関して最も短い) ですa2。最小の長さを特徴とする文字列が複数ある場合は、任意の文字列を選択して、プログラムから抜け出すことができます。

配列が比較的小さい場合でも、単語を組み合わせるオプションは事実上無限にあるため、これをブルートフォースすることはできないと思いますが、間違っていることを証明したいと思います!

確実に最短の結果が得られる最短の文字列を取得する良い方法はありますか、それともヒューリスティックアルゴリズムを使用してかなり短い文字列を検索する必要がありますか?

a2 のほとんどの文字列をカバーする文字列を a1 から選択し、a2 からそれらの項目を削除して、最初からやり直そうとしましたが、うまくいきません! かなり良い結果が得られますが、最高ではありません。

私はこの問題のためにこの実装を行いました： http ：//www.spoj.pl/problems/SHOP/

私のコードがテストケースの正しい答えを生成しない理由がわかりません。誰かが私がコードを改善するのを手伝ってくれるなら、そうしてください：D