algorithm - 这个 "Werewolf Prob"有更好的算法吗？

Question

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

问题是这样的:

Bob is a Werewolf. In his "wolf form", Bob is able to run faster than he can in is normal, human form. However, he is able to open doors much faster as a human (due to his hands). He also takes some amount of time to transform back and forth.

If Bob is chasing someone down, and he needs to travel along a hallway with doors, he wants to know what the fastest way to do it would be.

As a wolf, he can run 10 meters per second, while he can only run 4 meters per second normally. It takes Bob 8 seconds to open a door in wolf form, and only 1 second normally. It takes him 5 seconds to transform to and from wolf form.

The task is to write a program that, given the distance of the hallway Bob needs to travel, and the locations of all of the doors in the hallway, the shortest time he could cover the distance, along with how many transformations he would make.

Bob always begins in human form.

我解决它的方法基本上是遍历所有可能的解决方案空间，并找到成本最低的解决方案。

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

Answer 1

我的第一个想法是将其视为图形搜索问题，对此您可以使用 Dijkstra's algorithm .考虑这张图:

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

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

如评论中所述，您可能会观察到图形是有向的:您只能向右遍历，并且只有在门前变为人和门后变为狼才有意义。

因为问题很好地分解为迭代子问题，所以您可能会从 dynamic programming 来考虑它观点，其中子问题是“从door[n]的远端最快到达door[n]的时间是多少，无论是人还是狼，都从door[n-的远端给出” 1]?"

(我不会将这些算法中的任何一个称为贪心算法，因为在任何给定的时间你都有两种不同的选择，而不是仅仅基于单一的最佳解决方案来开发。总是有一种最快的方法到达任何给定点，但根据走廊的形状，Bob 在剩余的运行中处于一种或另一种形式可能具有未知的优势。)