Col*_*nic 11 algorithm dynamic-programming
在Google Code Jam中听到以下问题.竞争已经结束,所以可以谈论它https://code.google.com/codejam/contest/2270488/dashboard#s=p3
按照旧地图,你偶然发现了恐惧海盗拉里的秘密宝库!
宝库由N个锁定的箱子组成,每个箱子只能通过特定类型的钥匙打开.此外,一旦使用钥匙打开胸部,它就永远不能再次使用.在每个胸部内,你当然会找到很多宝藏,你也可以找到一把或多把钥匙,可用来打开其他箱子.胸部可能包含多个相同类型的钥匙,您可以容纳任意数量的钥匙.
您已经拥有至少一个密钥,并且您的地图显示了在各个箱子中可以找到的其他密钥.有了这些信息,您能想出如何解锁所有的箱子吗？
如果有多种方法可以打开所有箱子,请选择"按字典计算最小"的方式.
对于比赛,有两个数据集,一个包含最多20个箱子的小数据集,以及一个大到200个箱子的大型数据集.
我的回溯分支定界算法只能快速地解决小数据集.什么是更快的算法？
我不习惯算法比赛.我对这个问题感到有些不安:要在分支和绑定通用算法中剪切分支,你需要知道你将拥有的一般输入.
基本上,我查看了小集中提供的一些输入.在这个集合中发生的是你最终进入你无法得到任何类型t的任何键的路径:这种类型的所有剩余键都在具有相同类型t的锁的箱子中.所以你不能再访问它们了.
所以你可以建立下面的剪切标准:如果有一个t类型的胸部被打开,如果所有类型为t的剩余钥匙都放在那些箱子里,如果你没有这种类型的钥匙,那么你就不会在这个分支中找到解决方案.
您可以概括切割标准.考虑一个图形,其中顶点是键类型,如果在t1中仍有一些具有类型为t2的键的闭合胸部,则在t1和t2之间存在边缘.如果你有一些类型为t1的钥匙,那么你可以打开这种类型的一个箱子,然后至少得到一个可以从外围边缘进入的箱子的钥匙.如果您沿路径行驶,那么您知道在此路径中至少可以打开每个锁类型的一个箱子.但是如果没有到顶点的路径,你知道你无法打开这个顶点所代表的胸部.
有切割算法.计算您在posession中有一个键的顶点集中的所有可到达顶点.如果存在仍然关闭胸部的无法到达的顶点,则切割分支.(这意味着你回溯)
这足以解决大集.但我必须添加你写的第一个条件:
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 秒内解决了大输入问题。
谷歌官方对该问题的分析给出了这种迭代贪婪算法的正确性证明。