algorithm - 对遍历边有约束的最短路径

Question

在从事一个项目时，我偶然发现了一个我无法解决的图形算法问题。问题如下：

您有一个有向加权图，并希望在访问指定节点时找到起始节点和结束节点之间的最短路径（非常类似于 Find the shortest path in a graph which visit certain nodes）。但是，除了节点和边之外，该图还具有“项目”的概念，它们驻留在节点上，当您进入该节点时您会“拾取”。现在有一个额外的约束，即只有在您获得了该特定边的必要项I时才能遍历边。把它想象成一扇门的钥匙；您需要先获得钥匙才能通过门。

我只能想到以指数方式爆发的蛮力方法。谁能想到更好的方法或将我指向解决此问题的地方？或者也许让我相信这很“难”（从计​​算上讲）？谢谢你的帮助！

Answer 1

这个问题是 NP-HARD 最优解。哈密​​顿路径问题有一个简单的简化：

在原始图的每个顶点上放置唯一的项目。构造一个只连接到目标顶点的接收器顶点。让这两个顶点之间的边需要所有的项目。

Answer 2

您可以尝试保存算法的修改版本。解决车辆路径问题是一种启发式方法。也许您可以反转它并为想要的键创建一个拾取功能。它用于交付和最短路径问题。