匈牙利環難題

我很難找到匈牙利環難題的可接受啓發式。我正在計劃使用IDA *算法來解決並正在使用Visual Basic編寫程序。我所缺乏的是如何實現解謎的實際解決方案。我已經將左右環實現爲它們自己的陣列，並具有順時針和逆時針旋轉每個環的功能。我不是要求代碼，只是在某處開始。匈牙利環難題

這裏是2個環陣列：

Dim leftRing(19) As Integer 
' leftRing(16) is bottom intersection and leftRing(19) is top intersection 
Dim rightRing(19) As Integer 
' rightRing(4) is top intersection and rightRing(19) is bottom intersection

在陣列中，我存儲以下作爲用於每種顏色的值：紅色值= 1黃色= 2藍色= 3和黑色= 4

來源

2012-09-17 James Brown

向我們展示一些工作。你說你想使用這種算法 - 你有沒有想出一些僞代碼？ –

顯示「我已經將左右環實現到他們自己的數組中」的代碼，這使得回答更容易。你確定VB6嗎？ VS201x Express是免費下載的。 –

主要的問題是不知道從哪裏開始爲程序做啓發式。如果我能得到一個出發點，我可以從那裏出發。我所擁有的僅僅是如何根本不使用啓發式解決謎題的基本想法。基本上將10個紅球分成左環，然後將10個黑球分成右環，並混合和匹配黃和藍，直到它們按正確順序排列。 –

我建議分別計算每個環中的「錯誤」 - 需要更換多少個球才能使環解決（1個9色，1個10色，9個單獨一個球）。最多可以使用旋轉來固定兩個球，然後需要另一個旋轉來固定另外兩個球。分別計算每個環的距離= 2n-1，其中n是不良位置數量的一半，並取其中較大的一個。當您尋找錯誤數量最少的一個時，您可以遍歷所有二十個位置，但我想有一個更好的方法來計算這個度量（除了簡單的修剪）。

更新：與加雷裏德的討論指向以下啓發式：

對於單獨的各環，計數：

的顏色變化的數量。目標量是每個環三個顏色變化，並且一次最多可以消除四個顏色變化。對於這個指標，積分轉到Gareth。
不同顏色的計數，忽略它們的位置。應該有：一個10色10個球，一個9色9個球和另一個9色一個球。一次最多可以更改2種顏色。

第二啓發式可以分成三個部分：

應該有10 10球和10 9-球。十多球需要更換。
應該只有一種顏色的10球。較小顏色的球需要更換。
應該只有一個9色的球。其他顏色的球需要更換。如果所有顏色都是相同的，並且9色不缺，則需要更換另外一個球。

取兩個估計值中的較大者。請注意，您需要交替使用戒指，因此實際需要2n-1次移動才能進行n次替換。如果兩個估算值相等，或者最新的估算值相同，則增加一個。其中一環將不會通過第一步改進。

修剪將同一個環旋轉兩次的所有移動（假設允許大旋轉的移動度量）。這些已經被探索。

這應該避免所有大的局部最小值。

來源

2012-09-17 21:21:54

匈牙利環難題

回答

相關問題