有更好的算法来解决这个“狼人问题”吗？

Question

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

问题是这样的：

鲍勃是个狼人。在他的“狼形态”中，鲍勃能够跑得比他正常的、人类的身体更快。然而，作为一个人类，他能够更快地打开门(因为他的手)。他还需要一些时间来来回变换。 如果鲍勃在追人，他需要沿着带门的走廊走，他想知道最快的方法是什么。 作为一只狼，他可以跑10米每秒，而他只能跑4米每秒正常。以狼的形式打开门只需8秒，正常情况下只需1秒。他需要5秒的时间才能转换成狼形态。 任务是编写一个程序，考虑到走廊的距离，以及走廊上所有门的位置，他可以用最短的时间覆盖这段距离，以及他将进行多少次转换。 鲍勃总是以人的形式开始。

我解决这个问题的方法是基本上遍历整个可能的解决方案，并找到一个成本最低的解决方案。

我觉得可能有一个更简单的贪婪的算法来解决这个问题，但我还没有想到它。有什么想法吗？

Answer 1

我的第一个想法是把这看作是一个图搜索问题，您可以使用迪克斯特拉算法。考虑一下这张图：

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

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

正如评论中所指出的，你可能会注意到图是有向的:你只能向右走，只有在门前变回人，门后变狼才有意义。

因为这个问题分解得非常好，所以您可能会从动态规划的角度来考虑这个问题，其中的子问题是“作为人类或狼，到door[n]的远端的最快时间是什么？”

(我不认为任何这些算法都是贪婪的，因为你有两个不同的选择是在任何时刻开发出来的，而不是仅仅基于单一的最好看的解决方案。到达任何一个给定的点总是有最快的方法，但取决于走廊的形状，鲍勃可能有一种尚未为人所知的优势，那就是在剩下的时间里以这种或那种形式存在。)

Answer 2

我认为这可以归为最短路径。图中每个门有两个节点，一个是狼节点，一个是人节点。门之间的距离是边重。你可以从狼形态转变成成本(从狼图到人类图形的旅行)。包括变换在内的两个位置之间的最短路径对应于组合图中的最短路径。您从门或“人的图形”上的特殊开始节点开始初始化，在结束节点上以狼人的身份结束。

Answer 3

我不打算计算，所以你得弄清楚细节，但以下是我的想法：

您只能通过以下方式节省时间：

从狼转向人类打开一扇门

打开一扇门后，从人类转向狼，跑一段距离

基本上，你只需要在入口处前后做出决定。

如果你是人，当你撞到一扇门，穿过门(总是更快)

如果你是一只狼，当你撞到一扇门的时候，检查下一条走廊是否足够短，在穿过门之前你想变成人类。

如果你像人一样穿过一扇门，在走远之前，看看你是否应该变成一只狼。

如果你像狼一样穿过一扇门，你应该一直呆到隔壁。

祝好运!