在 Google Code Jam 中听到以下问题。现在比赛已经结束了，聊聊就好了https://code.google.com/codejam/contest/2270488/dashboard#s=p3
按照一张旧地图，您偶然发现了恐怖海盗拉里的秘密宝库！
宝库由 N 个上锁的箱子组成，每个箱子只能用特定类型的钥匙打开。而且，一旦钥匙被用来打开箱子，就再也不能使用了。在每个箱子里，你当然会发现很多宝藏，你可能还会发现一把或多把钥匙，可以用来打开其他箱子。一个箱子可能包含多个相同类型的钥匙，您可以持有任意数量的钥匙。
您已经拥有至少一把钥匙，并且您的地图显示在各个箱子内还可以找到哪些其他钥匙。有了所有这些信息，你能弄清楚如何解锁所有的箱子吗？
如果有多种打开所有箱子的方式，请选择“按字典顺序最小”的方式。
比赛有两个数据集，一个包含最多 20 个箱子的小数据集，一个包含最多 200 个箱子的大型数据集。
我的回溯分支定界算法只够快解决小数据集。什么是更快的算法？
我不习惯算法比赛。我对这个问题有点不安：要在分支和绑定通用算法中切割分支，您需要了解您将拥有的一般输入。
基本上，我查看了小集合中提供的一些输入。在这组中发生的事情是，您最终会进入无法获得某种类型 t 的任何钥匙的路径：这种类型 t 的所有剩余钥匙都在具有相同类型 t 锁的箱子中。因此，您将无法再访问它们。
所以你可以建立以下切割标准：如果有一些类型为 t 的箱子要打开，如果所有剩余的类型为 t 的钥匙都在这些箱子里，如果你没有这种类型的钥匙，那么你不会在这个分支中找到解决方案。
您可以概括切割标准。考虑一个图，其中顶点是键类型，如果 t1 中仍然有一些封闭的箱子具有 t2 类型的键，则在 t1 和 t2 之间存在一条边。如果你有一些 t1 类型的钥匙，那么你可以打开一个这种类型的箱子，然后至少得到一把钥匙，可以从外边进入其中一个箱子。如果您遵循一条路径，那么您知道您可以在这条路径中打开至少一个每种锁类型的箱子。但是，如果没有通往顶点的路径，您知道您将无法打开由该顶点表示的箱子。
有切割算法。从您拥有的密钥的顶点集中计算所有可到达的顶点。如果有无法到达的顶点仍然是封闭的胸部，那么你切断分支。（这意味着你回溯）
这足以解决大集合。但我必须添加你写的第一个条件：
if any(required > keys_across_universe):
return False
否则，它就行不通了。这意味着当钥匙的数量非常接近箱子的数量时，我的解决方案很弱。
这种切割条件并不便宜。它实际上可能花费 O(N²)。但它削减了如此多的分支，它绝对值得……只要数据集很好。（公平的 ？）
令人惊讶的是，这个问题可以通过贪心算法解决。我也将其实现为记忆深度优先搜索。直到后来我才注意到搜索从未回溯，并且没有命中记忆缓存。只需要对问题的状态和部分解决方案进行两次检查，就可以知道是否应该进一步追求特定的解决方案分支。它们很容易用一对例子来说明。
首先，考虑这个测试用例：
Chest Number | Key Type To Open Chest | Key Types Inside
--------------+--------------------------+------------------
1 | 2 | 1
2 | 1 | 1 1
3 | 1 | 1
4 | 2 | 1
5 | 2 | 2
Initial keys: 1 1 2
这里总共只有两把类型 2 的钥匙：一把在 5 号箱子里，一把在你最初拥有的地方。但是，三个箱子需要使用类型 2 的钥匙才能打开。我们需要比现有更多的这种类型的钥匙，所以显然不可能打开所有的箱子。我们立即知道这个问题是不可能的。我称这个键为“全局约束”。我们只需要检查一次。我看到这个检查已经在你的程序中了。
仅通过这个检查和记忆的深度优先搜索（就像你的一样！），我的程序能够解决这个小问题，尽管速度很慢：大约花了一分钟。知道程序无法在足够的时间内解决大输入，我从小集合中查看了测试用例。一些测试用例很快就解决了，而另一些则需要很长时间。这是程序花了很长时间才找到解决方案的测试用例之一：
Chest Number | Key Type To Open Chest | Key Types Inside
--------------+--------------------------+------------------
1 | 1 | 1
2 | 6 |
3 | 3 |
4 | 1 |
5 | 7 | 7
6 | 5 |
7 | 2 |
8 | 10 | 10
9 | 8 |
10 | 3 | 3
11 | 9 |
12 | 7 |
13 | 4 | 4
14 | 6 | 6
15 | 9 | 9
16 | 5 | 5
17 | 10 |
18 | 2 | 2
19 | 4 |
20 | 8 | 8
Initial keys: 1 2 3 4 5 6 7 8 9 10
经过简单的检查，这个测试用例的结构是显而易见的。我们有 20 个箱子和 10 把钥匙。十种钥匙类型中的每一种都将打开两个箱子。在使用给定钥匙类型可打开的两个箱子中，一个包含另一个相同类型的钥匙，另一个根本不包含任何钥匙。解决方案很明显：对于每种类型的钥匙，我们必须首先打开将给我们另一把钥匙的箱子，以便能够打开同样需要该类型钥匙的第二个箱子。
该解决方案对人类来说是显而易见的，但是该程序需要很长时间才能解决它，因为它还没有任何方法来检测是否有任何无法再获取的密钥类型。“全局约束”涉及每种密钥的数量，而不是获取它们的顺序。这第二个约束关注的是可以获取密钥的顺序，而不是它们的数量。问题很简单：对于我需要的每种密钥类型，有什么方法我仍然可以得到它吗？
这是我为检查第二个约束而编写的代码：
# Verify that all needed key types may still be reachable
def still_possible(chests, keys, key_req, keys_inside):
keys = set(keys) # set of keys currently in my possession
chests = chests.copy() # set of not-yet-opened chests
# key_req is a dictionary mapping chests to the required key type
# keys_inside is a dict of Counters giving the keys inside each chest
def openable(chest):
return key_req[chest] in keys
# As long as there are chests that can be opened, keep opening
# those chests and take the keys. Here the key is not consumed
# when a chest is opened.
openable_chests = filter(openable, chests)
while openable_chests:
for chest in openable_chests:
keys |= set(keys_inside[chest])
chests.remove(chest)
openable_chests = filter(openable, chests)
# If any chests remain unopened, then they are unreachable no
# matter what order chests are opened, and thus we've gotten into
# a situation where no solution exists.
return not chests # true iff chests is empty
如果此检查失败，我们可以立即中止搜索分支。执行此检查后，我的程序运行得非常快，需要 10 秒而不是 1 分钟。此外，我注意到缓存命中数下降到零，而且，搜索从未回溯。我删除了记忆并将程序从递归形式转换为迭代形式。然后，Python 解决方案能够在大约 1.5 秒内解决“大”测试输入。使用优化编译的几乎相同的C++ 解决方案可在 0.25 秒内解决大量输入。
在Google 官方对该问题的分析中给出了这种迭代、贪心算法正确性的证明。
我也无法解决这个问题。起初我的算法太慢了，然后我添加了一些增强功能，但我想我在其他方面失败了：
正如 Valentin 所说，我计算了可用的密钥以快速丢弃棘手的情况
第一次命中时试图忽略里面没有钥匙的箱子，跳到下一个
从更高的箱子开始跳过解决方案
检查“钥匙圈”，如果可用的钥匙不足以打开一个箱子（箱子里面有自己的钥匙）
性能很好（25 个小案例<2 秒），我手动检查了案例，它工作正常，但还是得到了不正确的答案：P