0

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

  • 各ノードは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困難かもしれないと思いますが、本当に最適なソリューションは必要ありません。良いソリューションで十分です。
  • ナイーブなアルゴは、「ロックイン」されたノードを取得する傾向があります。つまり、すべての隣接ノードが取得されます。

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

4

2 に答える 2

1

これは、一般的なグラフの最大の重みの一致の問題のインスタンスです。もちろん、最小の重みの一致の問題にするには、重みを無効にする必要があります。エドモンズのパス、樹木、花のアルゴリズム（ウィキペディアのリンク）がこれを解決します（公開されているPythonの実装もあります）。ナイーブな実装は、n個の頂点に対してO（n 4 ）ですが、MicaliとVaziraniのアルゴリズムを使用してn個の頂点とm個のエッジに対してO（n 1/2 m）にプッシュダウンできます（申し訳ありませんが、PDFが見つかりませんでした）そのために）。

于 2011-06-23T09:44:46.537 に答える
0

これは、最小エッジカバーの問題に関連しているようですが、ノードごとに1つのエッジしか存在できず、エッジの数ではなくコストを最小限に抑えようとしているという追加の制約があります。たぶん、あなたはそのフレーズを検索することによっていくつかの答えを見つけることができます。

それができない場合、問題は整数線形計画問題として表現できます。これはNP完全です。つまり、中規模の問題でも恐ろしいパフォーマンスが得られる可能性があります。（ただし、これは必ずしも問題自体がNP完全であることを意味するわけではありません。）

于 2011-06-23T09:19:56.920 に答える