最先進的圖着色metaheuristics

我有一個圖着色問題，涉及成千上萬的頂點，每個頂點有10到50個邊。我一直在研究許多圖形着色啓發式算法（GA，禁忌搜索...），但是我發現它們很難比較，並且決定哪個最適合我。有沒有人有任何關於大規模圖形着色的經驗來推薦一種技術，或者告訴我關於該領域當前的最新算法？最先進的圖着色metaheuristics

謝謝。

來源

2012-12-08 user1544745

簡單的啓發式不會做？ –

你也可以嘗試一個更理論[近似方法]（http://www.sciencedirect.com/science/article/pii/0020019093902466） – amit

在像Drools Planner這樣的優化引擎中實現它，並運行它以運行benchmarker以找出哪些metaheuristics最適合。

特別是如果你沒有純正圖着色問題（所以你有額外的約束），這是不可能事先告訴哪個元啓發式將最好的工作。

來源

2012-12-10 09:40:42

我知道的一個很好的解決方案是使用Kempe鏈模擬退火。基本上，您使用標準模擬退火，當您想要隨機更改解決方案時，請選擇兩個相鄰節點，然後根據Kempe鏈規則對它們的顏色進行填充。

來源

2014-04-25 07:41:47 twistedlogic

你能否請添加更多關於Kempe鏈的詳細信息？ – arunmoezhi

好吧，我瞭解了這個來自教授的技術Pascal van Hentenryck關於Coursera的離散優化課程。 – twistedlogic

該課程的新課程是可用的，我會推薦它。 Kempe Chains的想法如下：您想將其中一個節點的顏色更改爲任意顏色，但您也希望保持解決方案的可行性。例如，您想要將節點n1的顏色從藍色更改爲紅色。但是你有兩個相鄰的節點到節點n1，讓我們說n2和n3已經是紅色的。想法是在n1上從藍色→紅色改變顏色，n2和n3改變紅色→藍色，形容詞。紅色節點爲n2，n3爲紅色 - >藍色，等等。這樣解決方案的可行性得以維持。 – twistedlogic

最先進的圖着色metaheuristics

回答

相關問題