Google Foobar，资源限制下的最大独特访问次数，图中负面权重 [英] Google Foobar, maximum unique visits under a resource limit, negative weights in graph

问题描述

我很难找出问题的类型。我还是个学生，还没有参加过图论/线性优化课程。

我唯一知道的就是检查阴性周期，因为这意味着您可以将资源限制提高到无穷大，让您可以拿起每只兔子。我不知道选择下一条道路的理由。我也不知道何时终止，因为你可以继续使用所有的边缘，并使资源限制永远降到0以下，但永远不会逃跑。

I' m没有真正寻找代码（因为这是一个编码挑战），只有这种问题类型（例如：最大流量，最长路径，最短路径等）如果你已经有一个适合这个的算法，这将是额外的真棒。感谢。

从您的起点移动到所有兔子和隔壁所需的时间将会在整数矩阵。每排会告诉你开始时间，第一个兔子，第二个兔子，...，最后一个兔子，以及该顺序的舱壁。行的顺序遵循相同的模式（开始，每个兔子，舱壁）。兔子可以跳进你的手臂，所以它们可以瞬间抓起来，并在密封的同时到达舱壁，这样即使有戏剧性的逃生，也能获得成功。 （不用担心，任何你没有拿起的兔子都可以随身携带，因为它们不必携带你拿起的兔子。）如果你愿意，你可以重新访问不同的地方，然后移动到舱壁上并不意味着你必须立即离开 - 如果时间允许的话，你可以在舱壁之间移动以拾取额外的兔子。

除了在兔子之间花时间旅行，一些路径与空间站的安全检查点相互作用，并增加时间。给时钟增加时间会延迟关闭舱壁门，如果时间回到0或门关闭后的正数，它会触发舱壁重新打开。因此，有可能走一圈并保持时间的增加：也就是说，每次遍历一条路径时，都会使用或添加相同的时间。

编写一个形式回答函数（times，time_limit）来计算你可以拿起的最多的兔子以及它们是哪个兔子，同时在门关好之前仍然通过舱壁逃脱。如果有多套相同尺寸的兔子，请按排序顺序返回最低囚犯编号（作为索引）的兔子组。兔子被囚犯ID表示为一个有序列表，第一个兔子为0.最多有5个兔子，而time_limit是一个非负的整数，最多999个。
blockquote>

解决方案

这是计划问题，基本上。规划的通用方法是确定世界的可能状态，初始状态，状态之间的转换以及最终状态。然后搜索这个数据所暗示的图表，最简单地使用广度优先搜索。

对于这个问题，相关的状态是（1）剩下多少时间（2 ）我们选择了哪些兔子（3）我们现在在哪里。这意味着1,000个时钟设置（我将在一分钟内讨论增加的时间）时间2 ^ 5 = 32个兔子子集时间7个位置= 224,000个可能状态，这对于人而不是计算机很重要。

我们可以通过从刷屏来处理额外的时间约翰逊的算法。正如Tymur在评论中所建议的那样，运行Bellman - Ford并找到一个负循环（在这种情况下，所有的兔子都可以通过在负循环周围跑第一次来节省），或者在应用时使所有时间都是非负的潜力。不要忘记根据起始位置和舱壁之间的电位差来调整起始时间。

I'm having trouble figuring out the type of problem this is. I'm still a student and haven't taken a graph theory/linear optimization class yet.

The only thing I know for sure is to check for negative cycles, as this means you can rack the resource limit up to infinity, allowing for you to pick up each rabbit. I don't know the "reason" to pick the next path. I also don't know when to terminate, as you could keep using all of the edges and make the resource limit drop below 0 forever, but never escape.

I'm not really looking for code (as this is a coding challenge), only the type of problem this is (Ex: Max Flow, Longest Path, Shortest Path, etc.) If you an algorithm that fits this already that would be extra awesome. Thanks.

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.

解决方案

It's a planning problem, basically. The generic approach to planning is to identify the possible states of the world, the initial state, transitions between states, and the final states. Then search the graph that this data imply, most simply using breadth-first search.

For this problem, the relevant state is (1) how much time is left (2) which rabbits we've picked up (3) where we are right now. This means 1,000 clock settings (I'll talk about added time in a minute) times 2^5 = 32 subsets of bunnies times 7 positions = 224,000 possible states, which is a lot for a human but not a computer.

We can deal with added time by swiping a trick from Johnson's algorithm. As Tymur suggests in a comment, run Bellman--Ford and either find a negative cycle (in which case all rabbits can be saved by running around the negative cycle enough times first) or potentials that, when applied, make all times nonnegative. Don't forget to adjust the starting time by the difference in potential between the starting position and the bulkhead.

这篇关于Google Foobar，资源限制下的最大独特访问次数，图中负面权重的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！