問題タブ [graph]

少し奇妙な質問があります。誰かが情報を見つける場所を教えてもらえますか、または山登り法を使用する最短経路アルゴリズムの使用について少し紹介してもらえますか？私は両方の基本を理解していますが、2つを組み合わせることができません。ウィキペディアには、山登り法で巡回セールスマンを解決することについて興味深い部分がありますが、それを正確に行う方法についてのより詳細な説明は提供されていません。

たとえば、山登り法は巡回セールスマン問題に適用できます。すべての都市を訪問する解決策を見つけるのは簡単ですが、最適な解決策と比較すると非常に貧弱です。アルゴリズムはそのようなソリューションから始まり、2つの都市が訪問される順序を切り替えるなど、小さな改善を行います。最終的には、はるかに優れたルートが得られます。

私が理解している限りでは、任意のパスを選択し、それを繰り返して、途中で最適化を行う必要があります。たとえば、戻って開始ノードから別のリンクを選択し、それによってパスが短くなるかどうかを確認します。

申し訳ありませんが、私は自分自身をあまり明確にしませんでした。このアイデアを巡回セールスマンに適用する方法を理解しています。最短距離アルゴリズムで使用したいと思います。

更新しました

さらに読んだ後、次の漸化式で解を与えることができます。

これは、パートCを除いて、今では意味をなし始めています。最小値kを決定するにはどうすればよいですか？これは、可能なすべてのk値を反復処理して、（l（k、i）+ dist（pk、pj）の最小結果を格納できることを意味すると思いますか？

はい、確かに私が学校で勉強していた問題です。巡回セールスマン問題のビトニックツアーを研究しています。

とにかく、私が5つの頂点{0,1,2,3,4}を持っているとしましょう。私の最初のステップは、x座標の昇順でこれらを並べ替えることです。そこから、動的計画法でこれがどのように行われるかについて少し混乱しています。

ソートされたノードのリストをスキャンし、両方の部分（初期パスと戻りパス）の最適なパスを維持する必要があることを読んでいます。これらの最適なパスをどのように計算するかについて、私は混乱しています。たとえば、特定のノードを両方に含めることはできないため、最初のパスとリターンパスのどちらに含める必要があるかをどのように知ることができますか（エンドポイントを除く）。動的計画法のフィボナッチを振り返ると、基本的には基本ケースから始めて、前進します。私が求めているのは、バイトニック巡回セールスマン問題をどのように始めればよいのかということだと思います。

フィボナッチ数のようなものの場合、アプローチされる動的計画法は非常に明確です。しかし、私がただ密集しているだけなのか、それとも何なのかはわかりませんが、この問題に頭を悩ませようとするとかなり混乱します。

見てくれてありがとう！

注：私は完全な解決策を探していませんが、少なくともいくつかの良いヒントを探しています。たとえば、これがフィボナッチ数の問題である場合、最初の数個の数値がどのように計算されるかを説明できます。質問を改善する方法も教えてください。

これは一種のより一般的な質問であり、言語固有ではありません。使用するアイデアとアルゴリズムの詳細。

システムは次のとおりです。

友人のグループ間の少額のローンを登録します。ビルのカードが機能していないので、アリスが食事代 10 ドルを支払いますAlice。 翌日、鉄道の駅で会ったチャレスは切符を買うお金がなかったので、5ドルで切符を買いました。その日遅く、友人から 5 ドルと 1ドルを借りて、友人にプレゼントを買いました。Bill
BillCharlesBillAliceCharlesBill

ここで、すべてのトランザクションがシステムに登録されていると仮定すると、次のようになります。

ですから、あとは$4Billを渡すだけでAlice(彼は彼女に $1 を渡し、Charlie 彼の $5 をAlicealredy に送金しました)、これで初期状態になりました。

複数のトランザクションを持つ多くの異なる人々にそれをスケーリングする場合、トランザクションをできるだけ少なくするための最良のアルゴリズムは何でしょうか?

C または C++ で二部一致アルゴリズム (おそらく max-flow アルゴリズムに基づく) を実装するにはどうすればよいですか?

具体的には、ファイルに次の入力があります: (1,3) (1,5) (2,5)

(M,F) --> ここで、M は MALE の ID を表し、F は FEMALE の ID を表します。

一致の最大数を見つけて、一致したカップルを表示する必要があります。Like: マッチ: 1&3 , 2&5

「ネットワーク内の最大フロー」アルゴリズムに基づいてこの問題を解決できる本をいくつか読んだことがありますが、「この問題は....アルゴリズムで解決できる」という文以外に特定の情報は見つかりませんでした。私はmax-flowについてほとんど知識がなく、それを実装する方法も知りません...

私の問題は、グラフ内の最小スパニング ツリーを見つけることです。しかし、各頂点の合計次数が一定の係数を超えてはならないというもう 1 つの制約が必要です。問題をモデル化するにはどうすればよいですか? MST は間違ったパスですか? 私に役立つアルゴリズムを知っていますか？

もう 1 つの問題: グラフのエッジの重みが重複しているため、一意の MST の数をカウントする方法はありますか? これを行うアルゴリズムはありますか?

ありがとうございました。

編集：度とは、頂点を接続するエッジの総数を意味します。重複するエッジの重みとは、2 つのエッジの重みが同じであることを意味します。

ソーシャル グラフを作成するタスクを受け取りました。ここでは、1 人のユーザーを中心に、そのユーザーのつながりを示しています。

しかし、そこに到達する前に、2 人のユーザー間の最短経路を決定する方法に焦点を当てます。

それを行うためのアルゴリズムをいくつか見つけましたが、時間がかかりそうです.ソーシャルリンクに関するものであるため、追いつくために定期的に実行する必要があるため、最速のものを探しています.友達の更新。

では、2 人のユーザー間の最短経路を決定する最速の方法はどれか知っていますか?

PS: PHP と MySQL の例を知っていれば、仮想のビール (またはコーラ) を差し上げます。:D

フラッシュでグラフを描画するためのクラス/コンポーネント/ライブラリはありますか? そして、私は棒グラフについて話しているのではなく、ニューラル グラフやロード グラフなどの実際のグラフについて話しているのです。また、誰かが経験を持っている場合、グラフが大きくなり、非常にハードにロードされるまで、どのくらいの大きさのグラフをプロットできますか (どのように多くのノード、ルート)。

どうもありがとう。

関数をflotの「plotselected」イベントにバインドする場合、選択した領域の開始点と終了点のメインシリーズインデックスを取得する方法はありますか？

「plothover」では「item」変数を使用できることを確認しましたが、それが選択に機能するかどうかは明確ではありません。さらに、関数が呼び出されるたびにシリーズ全体を繰り返す必要はありません。私の目標は次のようなものを手に入れることです。

それを取得できれば、次のようなものを（データとともに）出力することもできます。

このように単純なはずですが、flotは本当に私をループに投げ込んでいます。

ありがとう！

ZedGraphコントロールを使用して、Y 値が 13、34、および 55 のデータをプロットしているとします。

Y 軸を設定して、13、34、55 のテキスト ラベルのみが表示されるようにするにはどうすればよいですか (そして、グリッド線が同期されると思います)。

データの範囲 (0、25、50、75 など) に等間隔のラベルを配置したくありません。実際の値にラベルを付けるだけです。