algorithm - 寻找最优解的动态算法

Question

考虑一个厌倦了白色和红色方 block 的游戏，顺序如下:

(开始 w w w w w w r r w w w w r w r w r w 结束)

w = 白色。 r = 红色。

有 3 个按钮。 绿色按钮:移动 5 步。 黄色按钮:移动 3 步。 蓝色按钮:移动 3 步。

游戏规则: - 如果玩家落在红色方 block 上则输。 - 第一个玩家完成游戏获胜。 - 允许降落在白色方 block 上。

贪心算法:

x = 0 
steps = 0
stop = false
while (....)
if a[x+5] is white then
 push the green buttton and x= x+5, steps++
if a[x+3] is white then
 push the yellow buttton and x= x+3, steps++
if a[x+2] is white then
 push the blue buttton and x= x+2, steps++
else stop = true

必需:赢得比赛的最少步数。

按照上面的贪心算法，解决方案将是 552225，而最佳解决方案是 33555。

我的问题是如何应用动态算法找到最优解？

Answer 1

您要做的是生成一个包含最小成本和最佳前一步的数组。你从头到尾把它填满，然后你从头到尾读到最优解。所以像这样:

min_cost = [infinite for all steps]
arriving_move = [none for all steps]
For each i in 0 to steps-1:
    if square[i] = 'r':
        pass
    else:
       for j in 2, 3, 5:
           if i <= j:
               if min_cost[i-j] + 1 < min_cost[i]:
                   min_cost[i] = min_cost[i-j] + 1
                   arriving_move[i] = j
reversed_answer = []
i = steps-1
while arriving_move[i] is not none:
    reversed_answer.append(arriving_move[i])
    i = i - arriving_move[i]
answer = reversed(reversed_answer)

请注意，这将找到一个您直接到达终点的最佳游戏。因此，在您的示例中，步数为 33553。

如果您同意“超出标记”，则必须在末尾添加一个具有自己特殊规则的特殊结束节点。