3

複雑な名前で申し訳ありませんが、当然のことです。問題を提示させてください。

コンテキスト: パーティショニングを行いたいタイプのロケーション ネットワークがあります。

問題の定義: 頂点 V、辺 E、および辺の重み W のセットを持つ無向重み付きグラフ G = {V,E,w} があります。辺は V のすべての頂点の間に存在します。

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

最後に、目的は次のとおりです。C のサイクルが互いに交差しないという制約の下で、C のすべてのサイクルを組み合わせたスコアが最大になるように、C のすべてのサイクルを G に適合させたいと考えています。

したがって、素人の言葉で言えば、定義された長さのサイクルでグラフを埋めたいと思います。グローバルな重みは最適です。

この問題に対する私の見解: この問題は、パッキング問題やハミルトン サイクルのようなものに還元できるため、少なくとも NP 困難です。

最適解は疑似多項式でさえない可能性があります。問題をいくつかの異なる方法 (グラフ) で定式化しようとしましたが、常に状態爆発が発生するため、扱いやすい 2D 動的プログラミング アプローチはおそらく不可能です (間違っている場合は訂正してください)。

したがって、おそらく近似アプローチを使用する必要があるようです。頭に浮かぶことの 1 つは、独自の近似アプローチを使用して、グラフ全体のハミルトニアン パスを見つけようとすることです。次に、次のステップは、局所最適ハミルトニアン パスを「カット」してサイクルを生成する場所を見つけることです。|C|!*|V| があります。これらの「カットサイト」を配置する方法。階乗は、これらのサイクルと |V| の順序の順列から得られます。開始位置の総数から得られます。剪定を行っても (つまり、同じサイズのサイクルが存在する場合)、これは大きな |C| に対しては依然として扱いにくいものです。小さい |C| の場合は力ずくで問題ないと思いますが、大きい |C| の場合は局所最適配置の近似値を得るために山登り法が必要になります。

ところで、皆さんどう思いますか？

4

1 に答える 1

0

ここでの David Speyer のコメントによると、(多項式で解ける|V|)線形代入問題を見ていると思います。

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

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

目的関数 (現在の順列のエッジの重みの合計) を呼び出しましょうf。 fはノード順列の関数ですが、それらの順列をどのように表現するかは自由に選択できます。ベクトルに分割された行列を選択すると、 は内積の合計となり、割り当て問題の基準に適合する線形になります。|V|f|V|

編集

ハミルトニアン サイクルを見つけなければならない可能性についての質問は、ノードのすべてのペアに接続エッジがあることを思い出すことで解決できます。完全なグラフは、その問題の退化したケースです。すべてのノードの順序はハミルトン サイクルです。

Cが重み行列で、が順列行列の場合P、コスト関数は matlab/octave 構文で として記述できますf(P) = sum(sum(C .* P))。.*これは、スカラーを得るために両方の次元で合計された行列になります。.*は (私が知っている) 古典的な線形代数には名前がないので、代わりに内積の和として書くことができます。各内積は、 の行Cと の行P(列ではありません) になります。

ハンガリー語アルゴリズムは、割り当て問題のウィキペディア ページにリンクされているポリタイム アルゴリズムの 1 つです。

于 2012-05-12T23:27:27.543 に答える