問題タブ [graph-algorithm]

コスト関数を最小化する六角形（ハニカム）グラフ上で隣接するノードのペアを見つけるアルゴリズムを探しています。

• 各ノードは3つの隣接ノードに接続されています
• 各ノード「i」は、1つの隣接ノード「j」とペアにする必要があります。

• ノードの各ペアはコスト関数を定義します

  c = pairCost（i、j）

• 次に、総コストは次のように計算されます。

  totalCost = 1/2 sum_ {i = 1：N}（pairCost（i、pair（i）））

ここで、pair（i）は、「i」がペアになっているノードのインデックスを返します。（合計は各ノードを2回カウントするため、合計は2で除算されます）。私の質問は、totalCostを最小化するノードペアを見つけるにはどうすればよいですか？

リンクされた画像は、ソリューションがどのように見えるかを明確にする必要があります（太い赤い線はペアリングを示します）：

いくつかのさらなるメモ：

• 一番外側のノードはあまり気にしません
• 私のコスト関数は||のようなものです v（i）-v（j）|| （ノードに関連付けられたベクトル間の距離）
• 問題はNP困難かもしれないと思いますが、本当に最適なソリューションは必要ありません。良いソリューションで十分です。
• ナイーブなアルゴは、「ロックイン」されたノードを取得する傾向があります。つまり、すべての隣接ノードが取得されます。

注：私はこの分野の通常の命名法に精通していません（それはグラフ理論ですか？）。あなたがそれを手伝うことができれば、多分それは私が文献で解決策を探すことを可能にするかもしれません。

相互に接続されたデータベースの大規模なグラフ、事実上 1 つの巨大な分散データベースがあるとします。グラフ上の任意のノードは、そのネイバーに再帰的にクエリを実行することでデータベース全体をクエリできます。これにより、ネイバーから取得した結果が取得され、結合された結果がクエリ パスに渡されます。

また、ノード自体のデータベースに「十分に良い」結果が含まれている場合に再帰を停止する機能があると想定してください。これにより、適切な結果がすでに近くにある場合にネットワーク全体を照会する必要がなくなります。これは、私が言おうとしていることに関連性があります。

クエリが作成されるたびに、返されたデータをクエリを開始したノードに一歩近づけて転送するのは理にかなっていませんか? つまり、クエリされたノードは、そのネイバーにクエリを実行して X を取得し、自身にクエリを実行して Y を取得し、クエリを実行したノードに X+Y を渡し、X をデータベースに格納し、データベースから Y を削除します。これは最終的に、平均してクエリ中に参照されるノードの量に関して、分散データベースがそのノード間でデータのほぼ最適な分散を行うことになるのではないでしょうか?

この技に名前はありますか？

有向非巡回グラフ (DAG) で定式化できるこの技術的な問題があります。ノードはイベント (タイミングは不明) を表し、有向エッジは関係シップをエンコードします: 「私はあなたより若い/私はあなたの前に起こった」.

Weighted DAG (WDAG) が DAG の距離関数を意味するように、エッジの重み (つまり、「動的な重み」) を推定する必要があります。言い換えると、ノード A と B の間のパスの重みの合計は、すべてのパスで等しくなければなりません。

重みが整数であっても、これは未定の問題です（トポロジカルソートが一意ではないという根本的な理由と同じだと思います）。一般論として、ノード/イベント間の時間間隔を表すエッジの重みは実数です。したがって、ここでは指定されていない、重み付き DAG に事前設定された目的関数 C=J(WDAG) を導入します。

私の質問は次のとおりです。1) 重みが DAG の距離関数を形成し、2) 目的関数のコスト C を最小化するという制約に従って、WDAG に正定値の重みを分散するアルゴリズムはありますか?

これは、従来 WDAG に関連付けられていた最短パスまたは最小スパニング ツリーの問題とは無関係のようです。上記の問題に対する正式な解決策またはヒューリスティックな解決策はありますか?

よろしく、

ステファン

mygraph から頂点のベクトルがあり、頂点をトポロジカルに並べ替えます。

頂点を「順番に」位相的にソートします。v1 と v2 を比較して、元の頂点のベクトル (v1) が「順序どおり」または「順序どおり」であるかどうかをテストする最良の方法は何ですか。

編集: 例: ベクトル v1 に頂点 {A, B, C} があり、エッジ (A,B) (C,A) がある場合

したがって、トポロジカルソートの後、v2 になります

{タクシー}

一意のトポロジー順序が得られない場合があります。たとえば、(A,C) が唯一のエッジである場合、v2 は {A , B , C} または {B , A , C} になる可能性があります。

ここで、v1 と v2 を調べて、v1 と v2 の両方が同じ順序を表しているかどうかを確認する必要があります。

2番目の編集：私はアプローチを試みましたが、今のところうまくいきます。これが良いアプローチかどうか教えてください。

開始点に戻る方法を考慮したTSPw/ oの問題名と、これを解決するためのアルゴリズムを知りたいです。

最短経路問題を調べましたが、それは私が探しているものではありません。問題は、割り当てられた2つのポイントから最短経路を見つけるだけです。しかし、私が探しているのは、nポイントを与え、1つの開始点のみを入力するという問題です。次に、すべてのポイントを1回だけ移動する最短経路を見つけます。（終点は任意の点にすることができます。）

ハミルトン閉路問題も調べましたが、定義された問題を解決するのではなく、ハミルトン閉路があるかどうかを調べました。

ダイクストラのアルゴリズムが負の重みで機能しない理由を理解しようとしています。最短経路の例を読んで、私は次のシナリオを理解しようとしています。

ウェブサイトから：

エッジがすべて左から右に向けられていると仮定すると、Aから始める場合、ダイクストラのアルゴリズムは、d（A、A）+ length（edge）、つまり（A、B）を最小化するエッジ（A、x）を選択します。次に、d（A、B）= 2を設定し、d（A、y）+ d（y、C）を最小化する別のエッジ（y、C）を選択します。唯一の選択肢は（A、C）で、d（A、C）=3に設定されます。ただし、全長1で、Cを経由してAからBへの最短経路を見つけることはありません。

次のダイクストラの実装を使用すると、d [B]がに更新されない理由がわかりません1（アルゴリズムが頂点Cに到達すると、Bでリラックスが実行され、d [B]がに等しいことを確認して、2更新します）その値を1）に。

ありがとう、

メイア

画像上のポイントを選択して保存するためのコードは誰でも知っています。私は、ロンドンの地下鉄の画像上にホットスポットを作成するために Dreamweaver CS5 を使用しています [Tube Map]。しかし、2点を選択する方法は何ですか。

クリック可能なインターフェイスであるジャーニープランナーに取り組んでいるので、「チューブマップ」で任意の 2 つのポイントを選択し、選択した 2 つのポイント間の最短経路を取得する必要があります。このようなものに似ています http://www.mtr.com.hk/jplanner/flash_chi/index.php

Tube Map の情報を入手し、MySQL または PhpMyAdmin ですべて作成しました。Wikipedia http://commons.wikimedia.org/wiki/London_Underground_geographic_maps/SQLから入手し ました。私はWampserver2を使用しています

これはほとんど言語にとらわれない質問であり、宿題ではありません。理想的には、解決策として C# や SQL サーバーを使用します。

関数 があるとしますGetExchangeRate(buyCurrency, sellCurrency)。したがって、1 GBP が 1.6 USD の価値がある場合、GetExchangeRate('GBP', 'USD') = 1.6とGetExchangeRate('USD', 'GBP') = 0.625.

システム内の注文は、次のトリプレットとして表されます: (buyCurrency, SellCurrency, buyCurrencyAmount). したがって、('GBP', 'USD', 125.00) は、125 GBP を購入することを意味します。

私の目標は、取引コストを節約し、推移性を含めて注文をキャンセルすることです。同じ通貨ペア間の買いと売りをネッティングするのは簡単で、簡単に正当化できます。USD で GBP を購入し、GBP で EUR を購入するなどの注文を簡素化するビジネス上の理由があるとしましょう。

この一連の注文を推移的に単純化したい。データは SQL テーブルに格納されますが、グラフ データ構造 (ノードは通貨、エッジは buyCurrencyAmounts) を構築し、これに適切なアルゴリズムを適用することを考えていました。最初に単純なネッティングを行い、次に DAG でトポロジカル ソートを行い、次にトップから開始し、トポロジカルな順序で歩き、順序を「絞る」、たとえば単純化することを考えました。

問題は、必ずしも DAG があるとは限らないことです。しかし、アルゴリズムを実行するにつれて、グラフ構造を単純化する可能性が高くなります。

これに使用する必要がある正しいデータ構造/アルゴリズムは何ですか? 結果の精度について心配する必要がありますか? 私が行くときにセントを失わないための良いアプローチはありますか? これを処理できる優れた C# ライブラリをお勧めできますか? SQL Server 2008 のみを使用してこれを試みるのは、クレイジー/非効率的/多すぎる作業でしょうか?

編集:取引に支払われる手数料はすべて価格 (為替レート) に組み込まれています。固定の定額料金などはありません。

2 つの有向パスを持つ有向グラフがあります。

2 つのパスの類似性を判断するアルゴリズムが必要です。

この投稿では、レーベンシュタイン距離を使用しておおよその類似性を判断することについて言及しています。また、ハミング距離も同様のメトリックを使用していることに気付きました。

私の質問は：

2 つのパスが互いに平行に走っている場合、どのように処理しますか。つまり、2 つのパスに類似したノードがない場合でも、それらのパスは互いに非常に近くを同じ方向に移動するため、「類似」と見なされます。

ありがとう

バックエッジhttp://cs.wellesley.edu/~cs231/fall01/dfs.pdfを検出することにより、DFS アルゴリズムでサイクルを検出できることは理解しています。上記の方法に従っている間、サイクル内のノードを効率的かつ「クリーン」な方法で出力する方法を理解できません。

いくつかの助けに感謝します

ありがとう