6

これが実際に割り当て/線形プログラミングの問題であるのと同じくらい「色付け」の問題であるかどうかはわかりません。私はどちらの専門知識も持っていません。しかし、この問題は以前にほぼ確実に解決/調査されたにちがいないと感じています。私は正しい方向へのいくつかの指針を得ることを望んでいました。

「問題文」は事実上次のように要約されます。

  1. グラフには、ルーターとコアの 2 種類の頂点があります。

  2. コアはルーターのみに接続されます。各コアは、SINGLE ルーターにのみ接続されます。そして、それぞれにユーザーが入力/定義した「色」があります。（私の特定の問題では、色は4/5の可能な色の1つに制限されています）。それらの色は変更できません。これは入力パラメーターです。(コアは下の画像の四角です)

  3. ルーターは、他のルーターと同様にコアに接続されます。それらには「色」が割り当てられていません。色を割り当てることは、プログラム/アルゴリズムの目的の一部です。(ルーターは、下の画像の円形の頂点です。)

  4. プログラムの目的は、異なる色の頂点間の「交差点」/エッジの数が最小限になるように、グラフ内の各ルーターに色を割り当てることです。

(別の見方: 基本的に、いくつかの頂点が色付けされ、他の頂点は色付けされていないグラフが与えられます。目的は、異なる色の頂点間のエッジの数が最小になるように、色付けされていない頂点に色を付けることです。)

これを整数線形プログラムとして定式化することができました（かなり不十分だと思います）、LP-Solveを使用してソリューション/アプローチをセットアップしました。私も独自のヒューリスティックを持っています。これを解決するための「適切な」/既知の/他のアプローチを知りたいですか?!

どうもありがとう！

デモンストレーションのための簡単な例。

4

2 に答える 2

3

まず、2色のケースに注目してみましょう。これをst min cutのインスタンスに変えることができます。アイデアは、グラフでsノードとtノードを指定し、残りのノードをsグループまたはtグループのいずれかに分割して、2 つのグループ間のエッジの重みの合計が最小化。お使いのバージョンでは、マスター イエロー ノードsとマスター レッド ノードtがあります。、元のグラフのすべてのエッジの数を超える重み付けされたエッジを、各コアと対応するマスター カラー ノードの間に配置します。高コストのエッジにより、すべてのルーターを移動する方が安価になるため、違法にコアの色を変更することはありません。この問題は、最大フロー - 最小カット定理を介して、標準の最大フロー アルゴリズムを使用して多項式時間で解くことができます。最適な選択は、エッジと頂点の数によって異なります。

複数の色の場合、「多端子カット」の問題を解決しようとしています。これは最小kカット問題に関連していますが、この問題の標準的な参考文献はThe Complexity of Multiterminal Cuts ( kカットの記事が間接的にリンクしている) です。3 色以上の場合、明らかにグラフが平面であれば、問題は多項式時間で解決できます。それ以外の場合はNP 困難であるため、これは別の NP 困難問題であるため、整数計画法ソルバーを使用することもできます。

于 2012-05-25T08:10:36.723 に答える
0

色の数が 5 以下で、ルーターの数が 10 以下の場合は、ブルート フォースを使用できます。

特にデフォルトですべてのルーターを最も一般的な色に色付けし、必要に応じてバックトラックしてそれらのいくつかの色を変更する場合は特に、5^10 よりもはるかに少ないオプションがあります。

編集: また、ルーターが 15 未満の場合は、必要に応じて適応できる素敵なハミルトニアン パス アルゴリズムもあります。グラフでハミルトニアン サイクルを見つけるための動的計画法のアルゴリズムは何ですか?

于 2012-05-25T05:19:02.740 に答える