問題タブ [dijkstra]

本当に巨大な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

私は古いアルゴリズムのメモを確認していて、この証拠に出くわしました。それは私が持っていた課題からのものであり、私はそれを正しく理解しましたが、確かに証拠が不足していると感じています。

問題はprove that the distance values taken from the priority queue in Dijkstra's algorithm is a non-decreasing sequence.

私の証明は次のようになります：

矛盾による証明。まず、d値'i'でQから頂点をプルするとします。次回は、d値が「j」の頂点をプルします。iを引いたとき、d値を確定し、開始頂点sからiまでの最短経路を計算しました。正のエッジウェイトがあるため、パスに頂点を追加するときにd値を縮小することはできません。Qからiを引いた後、より小さなd値でjを引く場合、jを介してiに到達できる可能性があるため、iへの最短経路がない可能性があります。ただし、iへの最短経路はすでに計算されています。可能なパスは確認しませんでした。保証されたパスはもうありません。矛盾。

この証明をどのように改善できますか？またはさらに良いことに、別のアプローチがありますか？かなり弱いようです:)

編集：申し訳ありませんが、この場合、私の優先キューは最小ヒープで実装されています

このプロジェクトの締め切りはすぐに迫っており、残っているものに対処する時間があまりありません。したがって、最良の（そしておそらくより複雑で時間のかかる）アルゴリズムを探す代わりに、グラフ構造にいくつかの操作を実装するための最も簡単なアルゴリズムを探しています。

私がする必要がある操作は次の通りです：

• 距離Xを指定して、グラフネットワーク内のすべてのユーザーを一覧表示します
• 距離Xと関係のタイプを指定して、グラフネットワーク内のすべてのユーザーを一覧表示します
• 関係のタイプを指定して、グラフネットワーク上の2人のユーザー間の最短経路を計算します
• グラフネットワーク上の2人のユーザー間の最大距離を計算します
• グラフネットワーク上で最も離れた接続ユーザーを計算します

私のグラフの実装に関するいくつかのメモ：

• エッジノードには2つのプロパティがあり、1つはタイプcharで、もう1つはですint。これらは、それぞれ関係のタイプと重みを表します。
• グラフは、頂点とエッジの両方について、リンクリストを使用して実装されます。つまり、各頂点は次の頂点を指し、各頂点は別のリンクリストのヘッド、つまりその特定の頂点のエッジも指します。

私がしなければならないことについて私が知っていること：

• 上で述べたように、これが最も簡単かどうかはわかりませんが、2人のユーザー間の最短経路については、ダイクストラアルゴリズムが人々によく推奨されているように思われるので、それを使用すると思います。
  • 私は検索と検索を行ってきましたが、このアルゴリズムを実装するのは難しいと感じています。このアルゴリズムを自分で実装できるように、チュートリアルやわかりやすいものを知っている人はいますか？可能であれば、Cソースコードの例を使用すると、非常に役立ちます。数学表記の例をたくさん見ますが、それは私をさらに混乱させます。
  • リンクの重みと関係タイプを表すためにグラフを隣接行列に「変換」すると役立つと思いますか？リンクリストの代わりに、そのアルゴリズムを実行する方が簡単でしょうか？必要に応じて、その変換を行う関数を簡単に実装できます。数ページ読んだ方が楽だと感じたので言っていますが、間違っているかもしれません。
• 他の4つの操作、提案についてのアイデアはありませんか？

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

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

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

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

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

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

頂点とエッジの両方について、リンクリストを使用してグラフを実装しましたが、これがダイクストラアルゴリズムの問​​題になりつつあります。前の質問で述べたように、隣接行列を使用するこのコードを変換して、グラフの実装を操作しています。

問題は、最小値を見つけると配列インデックスを取得することです。グラフの頂点が代わりに配列に格納されている場合、このインデックスは頂点インデックスと一致します。そして、頂点へのアクセスは一定になります。

グラフの実装を変更する時間はありませんが、一意の番号（ただし、0で始まらないもの、100090000のようなもの）でインデックス付けされたハッシュテーブルがあります。これが問題です。必要なときはいつでも、モジュロ演算子を使用して、0から頂点の総数までの数値を取得します。

これは、数値からの配列インデックスが必要な場合には問題なく機能しますが、配列インデックスからの数値が必要な場合（一定時間で計算された最小距離頂点にアクセスするため）、それほど多くはありません。

100090000 mod 18000=10000や10000invmod18000 = 100090000のように、モジュロ演算を逆にする方法を検索しようとしましたが、その方法が見つかりませんでした。

次の方法は、上記の例でarr [10000] = 100090000のような参照配列を作成することです。これで問題は解決しますが、グラフ全体をもう一度ループする必要があります。

現在のグラフの実装で、より良い/より簡単なソリューションはありますか？

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

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

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

私は、ダイクストラとプリムのアルゴリズムが、複数の頂点から移動先を選択しているときに何が起こるのか疑問に思っていました。同じ重みを持つ複数の頂点があります。

例えば

サンプル画像 http://img688.imageshack.us/img688/7613/exampleu.jpg

これらのそれぞれが使用されている実際の例は何ですか?

私はダイクストラのアルゴリズムに取り組んでおり、1 つだけでなく、考えられる最短経路をすべて見つける必要があります。隣接行列を使用しており、ダイクストラのアルゴリズムを適用したところ、最短経路を見つけることができました。しかし、最小コストですべてのパスを見つける必要があります。つまり、可能なすべてのソリューションが存在する場合です。

これは、単一のソリューションに対して、私のアルゴリズムがどのように機能するかです。