潜在的なNPハードの最大エッジ加重マルチサイクルグラフへの入力が必要

Question

申し訳ありませんが、複雑な名前は申し分ありません。問題を提示しましょう。

コンテキスト：私はいくつかの分割をしたい場所ネットワークのタイプを持っています。問題の

定義：私は、Eは、エッジ、頂点Vのセットと{W、V、E}無向重み付きグラフG =を有し、エッジ重みWのエッジがVにすべての頂点の間に存在

今、サイクルC = {C1 ... CN}のサイズ| C1 | ... | CN | s.t. | C1 | ... | CN |の和。頂点の総数| V |に等しい。サイクルCiのスコアは、パスに含まれるすべてのエッジの重みの合計です。

最後に、目的は次のとおりです。私は、Gのすべてのサイクルを、Cのサイクルがお互いに交差しないという制約で最大の結合スコアになるようにフィットさせたいと思います。

こういうわけで、定義された長さのサイクルを持つグラフを記入したいと思います。グローバルな重みが最適です。

私はこの問題に取り組んでいます。この問題は、少なくともNP困難です。これは、パッキングの問題やハミルトニアンサイクルのようなものに減らすことができるためです。

最適解は、おそらく擬似多項式ではありません。私はいくつかの異なる方法（グラフ）で問題を定式化しようとしましたが、それは常に状態の爆発を招くので、扱いにくい2D動的プログラミング手法は不可能です（私が間違っていれば修正します）。

だから、おそらく近似アプローチを使用しなければならないようです。心に浮かぶ1つのことは、それ自体の近似アプローチを使用してグラフ全体のハミルトニアン経路を見つけることです。次に、次のステップは、局所最適ハミルトニアン経路を「切断」してサイクルを生成する位置を見つけることである。 | C |！* | V |があります。これらの "カットサイト"を整理する方法。階乗は、これらのサイクルの順序付けと| V |開始位置の総数から得られます。プルーニング（すなわち、同じサイズのサイクルがある）であっても、これは、| C |が大きければ扱いにくい。私はブルートフォースが小| C |の場合は大丈夫だと言っていて、大| C |がローカル最適配置の近似を得るためには山登りのアプローチが必要になるでしょう。

どういうわけか、あなたはどう思いますか？

Answer 1

David Speyerのコメントhereによると、私はあなたが（多項式で解ける|V|にある）linear assignment problemを見ていると思います。

私が正しく理解していれば、ノードを分割するサイクルのセットの間に関数を最適化しようとしています。私が理解しているように、サイクル数や単一の長さを固定しているわけではありません。唯一の制約は、それらが互いに素であり、すべてのノードを含むことです。

もしそうなら、そのような各サイクルのセットは、ノードの単一の順列で正確に識別することができる。したがって、ノード順列の空間を最適化するように見えます。

目的関数（現在の並べ替えでの辺の重みの合計）をfとしましょう。 fはノード順列の関数ですが、それらの順列がどのように表現されるかは自由に選択できます。 |V|ベクトルに分割されたmatrixを選択した場合、fは|V|ドット積の合計であるため、割り当て問題の基準に合うように線形です。

EDITは

おそらくハミルトニアンサイクルを検索することについての質問は、ノードのすべての対が接続するエッジを有することを想起することで解決することができます。完全なグラフはその問題の縮退したケースです。すべてのノードの順序付けはハミルトニアンサイクルです。

Cが重み行列であり、Pが置換行列である場合、コスト関数はf(P) = sum(sum(C .* P))というようにmatlab/octave構文で記述できます。ここで.*はペアワイズプロダクト演算子であり、その結果行列が両方の次元で合計され、スカラーが得られます。 .*は古典的な線形代数の名前（私が知っている）を持っていないので、ドット積の和として書くことができます。各内積はCの行とPの行の上になります（ない列。）

Hungarian algorithmが割り当て問題のWikipediaのページにリンクされているpolytimeアルゴリズムの一つです。