在Google Code Jam中听到以下问题。比赛现在已经结束，所以可以谈论它 https://code.google.com/codejam/contest/2270488/dashboard#s=p3
在旧地图之后，你偶然发现了恐惧海盗拉里的秘密宝藏！
宝库由N个锁定的箱子组成，每个箱子只能通过特定类型的钥匙打开。此外，一旦使用钥匙打开胸部，它就永远不能再使用了。在每个胸部内，你当然会找到很多宝贝，你也可以找到一把或多把钥匙，可用来打开其他箱子。胸部可能包含多个相同类型的钥匙，您可以容纳任意数量的钥匙。
您已经拥有至少一个键，并且您的地图显示了在各个箱子中可以找到的其他键。有了这些信息，您能想出如何解锁所有的箱子吗？
如果有多种方法可以打开所有箱子，请选择“按字典计算最小”的方式。
对于比赛，有两个数据集，一个最多20个箱子的小数据集，以及一个大到200个箱子的大型数据集。
我的回溯分支定界算法 只有足够快才能解决小数据集。什么是更快的算法？
令人惊讶的是，这个问题可以通过贪婪算法解决。我也将它实现为记忆深度优先搜索。之后我才注意到搜索从未回溯，并且没有命中记忆缓存。只需要对问题状态和部分解决方案进行两次检查，以了解是否应该进一步追求特定的解决方案分支。用一对例子很容易说明它们。
首先，考虑这个测试用例：
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分钟。此外，我注意到缓存命中数下降到零，此外，搜索从未回溯。我删除了memoization并将程序从递归转换为迭代形式。该 Python解决方案 然后能够在大约1.5秒内解决“大”测试输入。几乎相同 C ++解决方案 使用优化编译，可在0.25秒内解决大量输入。
这个迭代的贪婪算法的正确性证明在 官方谷歌分析 这个问题。
我不习惯算法比赛。我对这个问题感到有些不安：要在分支和绑定通用算法中剪切分支，你需要知道你将拥有的一般输入。
基本上，我查看了小集中提供的一些输入。在这个集合中发生的是你最终进入你无法得到任何类型t的任何键的路径：这种类型的所有剩余的键都在具有相同类型t的锁的箱子中。所以你不能再访问它们了。
所以你可以建立下面的切割标准：如果有一些t型胸部被打开，如果所有类型为t的剩余钥匙都放在那些箱子里，如果你没有这种类型的钥匙，那么你就不会在这个分支中找到解决方案。
您可以概括切割标准。考虑一个图形，其中顶点是键类型，如果在t1中仍有一些具有类型为t2的键的闭合胸部，则在t1和t2之间存在边缘。如果你有一些类型为t1的钥匙，那么你可以打开这种类型的一个箱子，然后至少得到一个可以从外围边缘进入的箱子的钥匙。如果您沿路径行驶，那么您知道在此路径中至少可以打开每个锁类型的一个箱子。但是如果没有到顶点的路径，你知道你无法打开这个顶点所代表的胸部。
有切割算法。计算您在posession中有一个键的顶点集中的所有可到达顶点。如果存在仍然关闭胸部的无法到达的顶点，则切割分支。 （这意味着你回溯）
这足以解决大集。但我必须添加你写的第一个条件：
if any(required > keys_across_universe):
return False
否则，它将无法正常工作。这意味着当钥匙的数量非常接近箱子的数量时，我的解决方案很弱。
这种切割条件并不便宜。它实际上可以花费O（N²）。但它削减了如此多的分支，以确定它是值得的......只要数据集很好。 （公平吗？）
我也无法解决这个问题。我的算法起初太慢了，然后我添加了一些增强功能，但我想我在其他方面失败了：
正如瓦伦丁所说，我计算了可用的密钥以快速丢弃棘手的案件
试图在第一次击中时忽略没有钥匙的箱子，跳到下一个
从较高的箱子开始跳过解决方案
检查“钥匙圈”，如果可用钥匙不足以打开胸部（胸部内有钥匙）
性能很好（25个小案例<2秒），我手动检查了案例并且工作正常，但无论如何都得到了错误的答案：P