2

我参加了Programming Challenges并找到了 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()的剧本返回该剧本排列的分数。

如何选择一个好的“邻国”？对于随机重启，我可以简单地选择 nos 的随机排列。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

但我没有证据，也不知道如何选择一个好的邻国。有人对如何选择好的邻国有任何想法吗？

4

2 回答 2

1

对交换策略对我来说听起来不错。它肯定会访问——理论上——所有的排列。我认为，主要的一点是看看“邻居”在你的情况下是否真的“相似”，即两个仅在一对交换中不同的位置是否在分数上相当相似。我无法决定这一点，因为我不清楚你的“游戏”规则。

于 2011-01-11T01:11:51.430 回答
1

诀窍是有多种类型的动作。因此，为 SA 提供统一的小动作和多样化的大动作。但是有更高的机会提供第一个。小动作很简单：更改 1 或切换 2。

看看我在drools planner中的护士排班示例。它在java中的开源。

于 2011-01-11T09:18:09.110 回答