模擬退火和Yahtzee！

Question

我挑選Programming Challenges，找到了Yahtzee！問題，我將簡化：

• 有13個計分類別
• 有13個軋輥通過播放器（包括播放）
• 每個輥必須適合在一個不同的類別
• 的目標是找出戲劇的最高分數（類別中的最佳放映位置）;分數（玩）返回一個遊戲的分數

蠻力尋找最大的比賽得分需要13！ （= 6,227,020,800）分數（）調用。

我選擇模擬退火來找到接近最高分的東西，速度更快。雖然不確定，但它足夠好。我有5個芯片的13卷的列表，如：

((1,2,3,4,5) #1 
(1,2,6,3,4),#2 
    ... 
(1,4,3,2,2) #13 
) 

和遊樂(1,5,6,7,2,3,4,8,9,10,13,12,11)傳入得分（）返回該劇中的排列得分。

如何選擇一個好的「鄰國」？對於隨機重啓，我可以簡單地選擇nos的隨機排列。 1-13，把它們放在一個矢量中，並對它們進行評分。在旅行商問題，這裏有一個good neighboring state的例子：「在一些特定的 置換的鄰居是 是例如由生產交換 一對相鄰 城市的排列」

我有簡單地交換兩個隨機向量位置，像這樣一種不好的預感：

(1,5,6,7, 2 , 3,4,8,9,10, 13, 12,11) # switch 2 and 13 
(1,5,6,7, 13, 3,4,8,9,10, 2 , 12,11) # now score this one 

但我沒有證據，不知道如何去選擇一個好的鄰居狀態。任何人有關於如何挑選好鄰國的想法？

Answer 1

雙交換策略對我來說聽起來不錯。它無疑在理論上訪問所有排列。我認爲要點是要看看你的「鄰居」在你的情況下是否真的「相似」，也就是說，如果在配對交換中只有兩個不同的配對在分數上相當相似。我無法決定這一點，因爲你的「遊戲」規則對我來說並不清楚。

Answer 2

訣竅是有多種類型的動作。因此，提供SA既小，統一的舉措和大，多樣化的舉措。 但有更高的機會提供第一個。 小動作很容易：更換1或開關2.

看看我在drools planner的護士列表示例。它在java中是開源的。