將節點分配給圖的算法設計

我有一個圖論（這也與組合問題有關）問題，下面舉例說明，並想知道設計算法解決問題的最佳方法是什麼。將節點分配給圖的算法設計

鑑於4個不同6個節點的曲線圖（由不同的，我的意思是不同的結構，例如星形，線形，COMPLETE，等等），和24個獨特的目的，設計一個算法，這些對象分配給這4個圖表4次，因此4個賦值中圖上的重複鄰居數爲最小化爲。例如，如果對象A和B在一個賦值中的4個圖中的1個上是鄰居，則在最佳情況下爲，A和B將爲而不是在其他3個賦值中再次爲鄰居。

顯然，這種最小化的程度取決於給定的具體圖結構。但是我對這裏的一個通用解決方案更感興趣，所以給定任何4個圖結構，這種最小化作爲算法的結果得到了保證。

歡迎任何解決此問題的建議/想法，並且一些僞代碼可能足以說明設計。謝謝。

來源

2011-06-06 skyork

我可能會遺漏一些東西，但... 24個對象意味着您可以爲每個圖中的每個節點分配一個不同的對象，從而導致任何給定鄰居不超過一次。 – Chowlett 2011-06-06 14:57:32

@Chowlett，是的，但這只是一項任務（即將24個對象總共分配給4 x 6個節點）。我在這裏感興趣的是超過4個作業，重複鄰居的數量被最小化。 – skyork 2011-06-06 15:02:17

啊，我遵循。我很困惑，因爲有4個圖表和4個分配，但是這些數字實際上是無關的。 – Chowlett 2011-06-06 15:22:24

表示：

你有24個元素，我將其命名爲從A這個元素X（24個字母）。這四個元素中的每一個都會在4個圖中的一箇中放置。我將爲從1到24的4個圖表中的24個節點分配一個數字。

我將通過24-uple =（xA1，xA2 ...，xA24）確定A的位置，如果我想要把A賦給8號節點爲例，我會寫（xa1，Xa2..xa24）=（0,0,0,0,0,0,0,1,0,0 ... 0），其中圖1是在第8位置

我們可以說，A =（A1，... xa24）

E1 ... E24是單位矢量（1,0 ...，0）到（0， 0 ...1）

注意到有關操作 ''：

A.e1 = XA1
...
X.e24 = Xx24

上有一些限制A，... X與這些符號：

Xii在{0,1} 和

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

Sum（Xa1， 1

由於一個元素只能分配給一個節點。

我將通過定義每個節點的鄰居關係限定的曲線圖，可以說，節點8具有鄰居節點7和節點10

檢查A和B是在節點8的鄰居爲例我NEDD：

A.e8 = 1和B.e7或B.e10 = 1，則我只需要A.e8 *（B.e7 + B.e10）== 1

在函數isNeighborInGraphs（A，B ）我測試每個節點，我得到一個或零取決於鄰里。

符號：

6個節點的4個曲線圖中，每個元素的位置是由1-3的整數定義爲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是在neigbors一個圖表爲爲例系統

國：

L（A）= [B，B，C，E，G ...] //的A的 neigbors列表（可以重複）

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

目標函數

N（A）= LEN（L（A））+薩姆（IsneigborInGraph （A，i）中，i的L（A））

...

N（X）= ...該算法

開始的

說明與初始位置 A = E1 ... X = E24

具體化L（A），L（B）... ...你（X）

解決這個（用solveur，ampl爲爲例將工作我想，因爲它是一個非線性優化問題）：

目標函數

分鐘（薩姆（N（Z）中，Z = A至X）

限制條件：

薩姆（賽）= 1 ... Sum（Xxi）= 1

Sum（Xa1，xb1，... Xx1）= 1 ... 總和（Xa24，XB24，... Xx24）= 1

你得到最佳的解決方案

4.重複步驟2和3，3次以上。

來源

2011-06-13 14:04:46

感謝您的建議。但是，你能詳細解釋一下，你的意思是e1，e2等，你是指N個元素A，B，...，X及其表示（xa1，xa2 ... xa24）是什麼意思？ – skyork 2011-06-16 22:02:44

@Skyork，我更新了這篇文章，我添加了段**表示法** – 2011-06-17 06:36:20

假設您不想循環所有組合並每次計算總和並選擇最小值，則可以實現最小問題（根據您的約束使用線性規劃求解器即symplex算法引擎或非線性規劃求解器非線性求解器，在時間方面談得多），並根據路徑的形狀對變量（24）進行約束。你也可以使用像LINGO/LINDO這樣的免費軟件來快速創建一個決策理論模型並測試它的正確性（你需要決策理論的概念）

來源

2011-06-06 19:01:55

如果這與真實世界有任何關係，那麼絕對不太可能必須有一個真正的最低限度的解決方案。接近最小值應該足夠好吧？如果是這樣，您可以反覆隨機進行4項任務，並檢查結果，直到您耗盡時間或具有足夠好的解決方案，或似乎已停止改進最佳解決方案。

來源

2011-06-10 21:07:52 Fantius

如果所有四個圖都是K_6，那麼你可以做的最好的選擇是將24個對象的4個分區分成4個基數爲6的每個集合，這樣任意兩個集合的成對交集至多有2個基數。通過選擇集合分區的Hasse圖中最大相距的集合分區來完成此操作，並通過細化給出部分順序。一般情況下要困難得多，但也許你仍然可以從解決方案的粗略近似開始，然後巧妙地將哪個頂點分配給四個賦值中的哪個對象。

來源

2011-06-10 23:43:44 PengOne

我懷疑爲什麼這還不是被接受的答案的唯一正當理由，更可能是在'我的頭腦'部門比實際答案。如果你能想出一個（部分）這個想法的演示，我認爲你會（a）教會我很多（b）在這裏得到你更多的讚賞。 – sehe 2011-06-18 19:36:14

將節點分配給圖的算法設計

回答

相關問題