在六角形圖中尋找最佳節點對的算法

我正在尋找一種算法來尋找使成本函數最小化的六邊形（蜂窩）圖上的相鄰節點對。在六角形圖中尋找最佳節點對的算法

每個節點被連接到三個相鄰節點
每個節點「i」的應用正好一個鄰居節點「J」配對。
每對節點的定義的成本函數

C = pairCost（I，J）
的總成本被計算爲

TOTALCOST = 1/2 {sum_ I = 1 ：對}成對（i，對（i）））

其中對（i）返回與「i」配對的節點的索引。（總和除以2，因爲總和計數每個節點兩次）。我的問題是，如何找到最小化totalCost的節點對？

鏈接的圖片應該可以很清楚的一個解決方案是什麼樣子（粗紅線表示一種配對）：

enter image description here

一些進一步的說明：

我不真的關心最外層的節點
我的成本函數是像|| （i）v（j）|| （與節點相關的向量之間的距離）
我猜這個問題可能是NP難題，但我並不真的需要真正的最佳解決方案，一個好的解決方案就足夠了。
樸素算術傾向於獲得「鎖定」的節點，即所有鄰居都被佔用。

注：我不熟悉這個領域的通常術語（是圖論？）。如果你能幫上忙，那麼也許可以讓我在文獻中尋找解決方案。

來源

2011-06-23 svantana

這是一般圖中maximum weight matching problem的實例 - 當然，您必須否定權重才能使其成爲最小權重匹配問題。埃德蒙茲的paths, trees and flowers algorithm（Wikipedia link）爲你解決這個問題（也有一個公共Python implementation）。幼稚實施爲Ñ頂點爲O（n 4 ），但它可以使用Micali的算法和下推到爲O（n ^1/2米）爲Ñ頂點和米邊緣Vazirani（對不起，找不到PDF）。

來源

2011-06-23 09:44:46

謝謝，Edmonds的Blossom算法解決了這個問題。不幸的是，它的複雜性比節點的數量要多（對我來說）。由於我正在考慮非常大的圖表，我需要找到更快的算法。有可能利用我圖的統一結構 - 如果不是的話，似乎有很多啓發式的快速近似解法。 – svantana

嘗試找到Micali和Vazirani算法的實現;由於你的圖是六邊形的，所以* m *漸近地等於* 3n *，這使得它的複雜性變爲O（n ^3/2）。 –

這似乎與minimum edge cover problem有關，還有一個限制條件是每個節點只能有一條邊，並且您試圖最小化成本而不是邊數。也許你可以通過搜索這個短語找到一些答案。

如果做不到這一點，你的問題可以被表述爲integer linear programming problem，這是NP完全問題，這意味着你可能會得到甚至中型的問題，可怕的性能。（但這並不一定意味着問題本身就是NP完全的。）

來源

2011-06-23 09:19:56

在六角形圖中尋找最佳節點對的算法

回答

相關問題