这个"狼人问题"有更好的算法吗？

Question

我有一个问题,我感兴趣(编程竞赛),我不知道是否有一个比我的更有效的解决方案.

问题是这样的:

鲍勃是一个狼人.在他的"狼形态"中,鲍勃能够比正常的人类形式跑得更快.然而,作为一个人(由于他的双手),他能够更快地打开门.他还需要一些时间来来回变换.

如果鲍勃正在追逐某人,他需要沿着走廊走廊,他想知道最快的方法是什么.

作为一只狼,他可以每秒跑10米,而他每天只能跑4米.鲍勃需要8秒才能以狼的形式打开一扇门,通常只需1秒钟.他需要5秒钟来改变狼的形态.

任务是编写一个程序,考虑到鲍勃需要行走的走廊的距离,以及走廊中所有门的位置,他可以覆盖距离的最短时间,以及他将进行多少次转换.

鲍勃总是以人的形式开始.

我解决它的方法是基本上遍历可能的解决方案的整个空间,并找到成本最低的解决方案.

我觉得可能有一个更简单的贪婪算法来解决这个问题,但是我还没有找到它.有任何想法吗？

Answer 1

我的第一个想法是将其视为图搜索问题,您可以使用Dijkstra算法.考虑这个图:

                          door            door
   HUMAN START-o---------o----o----------o----o-----------------o
               |         |    |          |    |                  } END
WEREWOLF       o---------o----o----------o----o-----------------o

基本上,在任何给定节点,您都有状态感(距离,isWolf),并且在任何两个节点之间您都有一定的成本(时间).使用Dijkstra算法,您可以找到任何给定节点的最短时间,具有两个可能的结束节点.

正如评论中所指出的那样,您可能会发现图表是针对的:您可能只会向右移动,只有在门和门之后变为人类才有意义.

因为这个问题很好地分解为迭代子问题,你可能会从动态编程的角度来考虑它,其中子问题是"远离door[n]人类或狼的最远的时间是什么,从远处得到两个时间一边door[n-1]？"

(我不会把这些算法中的任何一个称为贪婪,因为你在任何特定时刻都有两种不同的选择,而不是仅仅基于单一的最佳解决方案进行开发.对于任何给定的点,总是有最快的方法,但取决于在走廊的形状上,鲍勃可能有一个尚不为人知的优势,就是在其余的跑步中以一种形式或另一种形式存在.)