匹配算法

Question

奇怪的問題在這裏不是真正的代碼，但邏輯，希望它確定發佈它在這裏，這裏是

我有一個可以被認爲是一個圖形的數​​據結構。 每個節點可以支持多個鏈接，但僅限於每個節點的值。 所有鏈接都是雙向的。每個環節都有成本。成本取決於節點之間的歐氏差異，每個節點中兩個參數的最小值。和一個全局修飾符。

我希望找到圖形的最大成本。

想知道是否有一個聰明的方法來找到這樣的匹配，而不是通過蠻力進行......這是醜陋的......我不知道我怎麼會這樣做，沒有花費700萬多年運行它。

澄清：

Global variable = T 
many nodes N each have E,X,Y,L 
L is the max number of links each node can have. 
cost of link A,B = Sqrt( min([a].e | [b].e) ) x 
    (1 + Sqrt(sqrt(sqr([a].x-[b].x)+sqr([a].y-[b].y)))/75 + Sqrt(t)/10) 


total cost =sum all links.....and we wish to maximize this. 

用於在節點的平均值爲40-50的範圍可以到（20..600） 平均節點連接因子爲3的範圍是0-10。

Answer 1

如果我正確理解問題，則可能沒有多項式解。因此，我將實現如下算法：

1. 查找崩貪婪一些解決方案。要做到這一點，您需要按成本對所有邊進行排序，然後從最高處開始，在可能的情況下爲圖添加邊，並在節點無法接受更多邊時跳過。
2. 看看你的邊緣，並試圖通過使用啓發式來更改它們以存檔更高的成本。第一個出現在我腦海中的是：你循環遍歷節點（A，B，C，D）的所有4元組，如果你當前的圖有邊AB，CD但是AC，BD會更好，然後你做出改變。
3. 可選用6元組或其他遺傳算法（它們被稱爲這種方式，因爲它們通過突變工作）。

Answer 2

是否有可能通過從任何給定起點貪婪地選擇下一個最昂貴的選項（省略跳至訪問節點）並停止所有節點訪問？如果你死路回到前一個地方，你並沒有死路一條，貪婪地選擇。這需要一些工作，可能像堆棧一樣，以保持您的路徑。我認爲這將非常有效地工作，只要成本有序且非負面。

Answer 3

使用遺傳算法。它們旨在解決您快速降低時間複雜性的問題。用您選擇的語言檢查AI庫。

Answer 4

爲了完整爲別人着想，着眼於本文中，我會建議重新審視你的圖論算法：

• 的Dijkstra
• 愛仕達
• 貪婪
• 深度/廣度優先
• 即使動態編程（在某些情況下）
• 等。等。

在那裏有一個地方是你的問題的正確解決方案。我會建議先看看Dijkstra。

我希望這可以幫助別人。

Answer 5

這相當於旅行商問題（因此是NP-Complete），因爲如果你能夠有效地解決這個問題，你可以簡單地通過用它的倒數代替每個成本來解決TSP。

這意味着你不能準確解決。另一方面，這意味着你可以像我說的那樣完全按照它的倒數來代替每個成本，然後在這個問題上使用任何已知的TSP近似方法。

Answer 6

對我來說好像是一個max flow problem。