algorithm - Google Foobar，资源限制下的最大独立访问，图中的负权重

Question

我无法弄清楚这是什么类型的问题。我还是一名学生，还没有上过图论/线性优化类(class)。

我唯一确定的是检查负循环，因为这意味着您可以将资源限制提高到无穷大，这样您就可以捡起每只兔子。我不知道选择下一条路径的“原因”。我也不知道何时终止，因为您可以继续使用所有边缘并使资源限制永远低于 0，但永远不会逃脱。

我并不是真的在寻找代码(因为这是一个编码挑战)，只是寻找问题的类型(例如:最大流、最长路径、最短路径等)如果您的算法已经适合这个那会特别棒。谢谢。

The time it takes to move from your starting point to all of the bunnies and to the bulkhead will be given to you in a square matrix of integers. Each row will tell you the time it takes to get to the start, first bunny, second bunny, ..., last bunny, and the bulkhead in that order. The order of the rows follows the same pattern (start, each bunny, bulkhead). The bunnies can jump into your arms, so picking them up is instantaneous, and arriving at the bulkhead at the same time as it seals still allows for a successful, if dramatic, escape. (Don't worry, any bunnies you don't pick up will be able to escape with you since they no longer have to carry the ones you did pick up.) You can revisit different spots if you wish, and moving to the bulkhead doesn't mean you have to immediately leave - you can move to and from the bulkhead to pick up additional bunnies if time permits.

In addition to spending time traveling between bunnies, some paths interact with the space station's security checkpoints and add time back to the clock. Adding time to the clock will delay the closing of the bulkhead doors, and if the time goes back up to 0 or a positive number after the doors have already closed, it triggers the bulkhead to reopen. Therefore, it might be possible to walk in a circle and keep gaining time: that is, each time a path is traversed, the same amount of time is used or added.

Write a function of the form answer(times, time_limit) to calculate the most bunnies you can pick up and which bunnies they are, while still escaping through the bulkhead before the doors close for good. If there are multiple sets of bunnies of the same size, return the set of bunnies with the lowest prisoner IDs (as indexes) in sorted order. The bunnies are represented as a sorted list by prisoner ID, with the first bunny being 0. There are at most 5 bunnies, and time_limit is a non-negative integer that is at most 999.

Answer 1

这是一个planning problem ， 基本上。规划的一般方法是确定世界的可能状态、初始状态、状态之间的转换和最终状态。然后搜索该数据所暗示的图形，最简单的方法是使用广度优先搜索。

对于这个问题，相关的状态是(1)还剩多少时间(2)我们捡到了哪些兔子(3)我们现在在哪里。这意味着 1,000 个时钟设置(我将在一分钟内讨论增加的时间)乘以 2^5 = 兔子的 32 个子集乘以 7 个位置 = 224,000 种可能的状态，这对人来说很多，但对计算机来说不是。

我们可以通过从 Johnson's algorithm 滑动一个技巧来处理增加的时间.正如 Tymur 在评论中建议的那样，运行 Bellman--Ford 并找到一个负循环(在这种情况下，所有兔子都可以通过首先绕负循环运行足够多次来保存)或者在应用时使所有时间都为非负的潜力。不要忘记根据起始位置和隔板之间的电位差来调整起始时间。