模拟退火和 Yahtzee！
我选择了编程挑战并找到了 Yahtzee！我将简化的问题：
- 有 13 个得分类别
- 一名玩家有 13 次掷骰（包括一场比赛）
- 每个掷骰必须适合一个不同的类别
- 目标是找到一次比赛的最高得分（掷骰在类别中的最佳位置）； Score(play) 返回游戏的分数
暴力破解找到最大游戏分数需要 13！ (= 6,227,020,800) Score() 调用。
我选择模拟退火来更快地找到接近最高分的东西。虽然不是确定性的，但已经足够了。我有一个 13 卷 5 个骰子的列表，例如：
((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)传递给 Score() 返回该比赛排列的分数。
如何选择一个好的“邻国”？对于随机重启，我可以简单地选择 no 的随机排列。 1-13，将它们放入向量中，并对它们进行评分。在旅行推销员问题中，以下是一个良好邻国的示例：
“某些特定的邻居 排列是排列 例如由 交换一对相邻的 城市。”
对简单地交换两个随机向量位置有一种不好的感觉，就像这样：
(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
但我没有证据，也不知道如何选择一个好的邻国。有人对如何选择好的邻国有任何想法吗？
I've picked up Programming Challenges and found a Yahtzee! problem which I will simplify:
- There are 13 scoring categories
- There are 13 rolls by a player (comprising a play)
- Each roll must fit in a distinct category
- The goal is to find the maximum score for a play (the optimal placement of rolls in categories); score(play) returns the score for a play
Brute-forcing to find the maximum play score requires 13! (= 6,227,020,800) score() calls.
I choose simulated annealing to find something close to the highest score, faster. Though not deterministic, it's good enough. I have a list of 13 rolls of 5 die, like:
((1,2,3,4,5) #1
(1,2,6,3,4),#2
...
(1,4,3,2,2) #13
)
And a play (1,5,6,7,2,3,4,8,9,10,13,12,11) passed into score() returns a score for that play's permutation.
How do I choose a good "neighboring state"? For random-restart, I can simply choose a random permutation of nos. 1-13, put them in a vector, and score them. In the traveling salesman problem, here's an example of a good neighboring state:
"The neighbours of some particular
permutation are the permutations that
are produced for example by
interchanging a pair of adjacent
cities."
I have a bad feeling about simply swapping two random vector positions, like so:
(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
But I have no evidence and don't know how to select a good neighboring state. Anyone have any ideas on how to pick good neighboring states?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
对我来说，配对交换策略听起来不错。从理论上讲，它肯定会访问所有排列。我认为，要点是看看“邻居”在您的情况下是否真的“相似”，即仅在一对交换中不同的两个位置在分数上是否相当相似。我无法决定这一点，因为我不清楚你的“游戏”规则。
The pair-swap strategy does not sound bad to me. It certainly visits -in theory- all permutations. The main point, I think, is to see if the "neighbors" are really "similar" in your case, i.e. if two placements that differ only in a pair swapping are rather similar in score. I cannot decide this, because the rules of your "game" are not clear to me.
诀窍是要有多种类型的动作。
因此，为 SA 提供小型、统一的动作和大型、多样化的动作。
但提供第一个的机会更高。
小动作很简单：更改 1 或切换 2。
请查看 drools planner 中的护士排班示例。它是用java开源的。
The trick is to have multiple types of moves.
So offer SA both small, unifying moves and big, diversifying moves.
But have a higher chance of offering the first.
The small moves are easy: change 1 or switch 2.
Take a look at my nurse rostering example in drools planner. Its open source in java.