12

以下に示すグラフ理論（組み合わせ論にも関連しています）の問題があり、それを解決するためのアルゴリズムを設計するための最良のアプローチは何でしょうか。

6つのノードの4つの異なるグラフ（異なる、つまり、STAR、LINE、COMPLETEなどの異なる構造を意味します）と24の一意のオブジェクトが与えられた場合、これらのオブジェクトをこれらの4つのグラフに4回割り当てるアルゴリズムを設計します。 4つの割り当てにわたってグラフ上で隣接するものを繰り返すことは最小限に抑えられます。たとえば、オブジェクトAとBが1つの割り当ての4つのグラフの1つで隣接している場合、最良の場合、AとBは他の3つの割り当てで再び隣接することはありません。

明らかに、そのような最小化が進むことができる程度は、与えられた特定のグラフ構造に依存します。しかし、私はここで一般的な解決策にもっと興味があります。そのため、4つのグラフ構造が与えられた場合、そのような最小化はアルゴリズムの結果として保証されます。

この問題を解決するための提案/アイデアは歓迎されます。設計を説明するには、いくつかの擬似コードで十分な場合があります。ありがとうございました。

4

4 に答える 4

5

表現：

24個の要素があります。この要素にAからX（最初の24文字）の名前を付けます。これらの各要素は、4つのグラフのいずれかに配置されます。1から24までの4つのグラフの24ノードに番号を割り当てます。

Aの位置を24-uple=（xA1、xA2 ...、xA24）で識別し、たとえばノード番号8にAを割り当てたい場合は、（xa1、Xa2..xa24）と記述します。 =（0,0,0,0,0,0,0,1,0,0 ... 0）、ここで1は位置8にあります。

A =（xa1、... xa24）と言えます

e1 ... e24は、（1,0 ... 0）から（0,0 ... 1）までの単位ベクトルです。

演算子'。'についての注意：

  • A.e1 = xa1
  • ..。
  • X.e24 = Xx24

A、... Xには、次の表記法でいくつかの制約があります。

Xiiは{0,1}にあり、

Sum（Xai）= 1 ... Sum（Xxi）= 1

Sum（Xa1、xb1、... Xx1）= 1 ... Sum（Xa24、Xb24、... Xx24）= 1

1つの要素を1つのノードにのみ割り当てることができるため。

各ノードの隣接関係を定義することによってグラフを定義します。たとえば、ノード8に隣接ノード7とノード10があるとします。

たとえば、AとBがノード8のネイバーであることを確認するには、次のようにします。

A.e8=1およびB.e7またはB.e10=1の場合、A.e8 *（B.e7 + B.e10）==1が必要です。

関数isNeighborInGraphs（A、B）で、すべてのノードについてテストし、近傍に応じて1または0を取得します。

表記：

  • 6ノードの4つのグラフ、各要素の位置は1〜24の整数で定義されます（最初のグラフの場合は1〜6など）。
  • e1 ... e24は、（1,0,0 ... 0）から（0,0 ... 1）までの単位ベクトルです。
  • A、B...XをN個の要素とします。

A =（0,0 ...、1、...、0）=（xa1、xa2 ... xa24）

B=..。

..。

X =（0,0 ...、1、...、0）

  • グラフの説明：

IsNeigborInGraphs（A、B）= A.e1 * B.e2 + ... //例として、1と2が1つのグラフの隣人である場合

  • システムの状態：

L（A）= [B、B、C、E、G ...] // Aのネイバーのリスト（繰り返すことができます）

actualise(L(A)):
for element in [B,X]
if IsNeigbotInGraphs(A,Element)
L(A).append(Element)
endIf
endfor
  • 目的関数

N（A）= len（L（A））+ Sum（IsneigborInGraph（A、i）、i in L（A））

..。

N（X）=..。

アルゴリズムの説明

  1. 初期位置から開始A=e1 ... X = e24
  2. L（A）、L（B）を実現... L（X）
  3. これを解きます（ソルバーを使用すると、非線形最適化の問題であるため、例のアンプが機能すると思います）：

目的関数

min（Sum（N（Z）、Z = AからX）

制約：

Sum（Xai）= 1 ... Sum（Xxi）= 1

Sum（Xa1、xb1、... Xx1）= 1 ... Sum（Xa24、Xb24、... Xx24）= 1

あなたは最高の解決策を手に入れます

4.手順2と3をさらに3回繰り返します。

于 2011-06-13T14:04:46.397 に答える
3

4 つのグラフがすべてK_6である場合、最善の方法は、24 個のオブジェクトの 4 つのセット パーティションをそれぞれカーディナリティ 6 の 4 つのセットに選択して、任意の 2 つのセットのペアごとの共通部分のカーディナリティが最大 2 になるようにすることです。これを行うには、セットを選択します。セット分割のハッセ図で最大に離れている分割で、部分的な順序が洗練によって与えられます。一般的なケースははるかに難しいですが、おそらく、この大雑把な解の近似から始めて、4 つの割り当てでどの頂点がどのオブジェクトに割り当てられるかを賢くすることができます。

于 2011-06-10T23:43:44.773 に答える
0

これが現実の世界と関係がある場合、真の最小のソリューションが絶対に必要になる可能性はほとんどありません。最小値に近ければ十分ですよね？その場合、時間がなくなるか、十分な解決策が得られるか、最善の解決策の改善が止まったように見えるまで、繰り返しランダムに 4 つの課題を作成し、結果を確認することができます。

于 2011-06-10T21:07:52.227 に答える
0

すべての組み合わせを循環させて毎回合計を計算し、最小のものを選択したくないと仮定すると、最小の問題を実装できます (線形計画法ソルバー、つまりシンプレックス アルゴリズム エンジンまたは非線形ソルバーのいずれかを使用して、制約に応じて解決されます。パスの形状に応じて、変数 (24) に制約を加えます。また、LINGO/LINDO などのフリー ソフトウェアを使用して、意思決定理論モデルを迅速に作成し、その正確性をテストすることもできます (ただし、意思決定理論の概念が必要です)。

于 2011-06-06T19:01:55.807 に答える