在做一个项目时，我偶然发现了一个图算法问题 I一直无法解决。问题如下：
您有一个有向加权图，并希望找到访问指定节点时启动节点和结束节点(非常像在访问某些节点的图形中找到最短路径(。但是，除了节点和边之外，此图还具有"项目"的概念，它驻留在节点上，当您进入该节点时，您会"拾取"。现在有一个额外的约束，即边缘只能是如果您获得了该特定边缘的必要物品，则遍历。把它想象成一扇门的钥匙;您需要先获取密钥，然后才能进门。
我只能想到成倍爆炸的蛮力方法。谁能想到更好的方法或指出我解决这个问题的地方？或者也许让我相信这是"困难的"(计算上(？感谢您的任何帮助！
这个问题很难以最佳方式解决。哈密顿路径问题有一个简单的简化：
将唯一项目放在原始图形的每个顶点上。构造仅连接到目标顶点的汇折点。让这两个顶点之间的边需要所有项目。
您可以尝试保存算法的修改版本。解决车辆路线问题是一种启发式方法。也许您可以反转它并为想要的键创建一个拾取功能。它用于交付和最短路径问题。