在一个项目中，我偶然发现了一个图算法问题
还没能解决。问题如下：
您有一个有向的加权图，并且希望在
访问指定节点时的开始节点和结束节点（非常类似
Find the shortest path in a graph which visits certain nodes）。
然而，除了节点和边之外，这个图还有“项”的概念，
它们位于节点上，当您进入该节点时，您将“拾取”。现在有一个额外的约束，边只能是
如果你已经获得了必要的物品，我，为那个特殊的边缘。
把它当作门的钥匙；你需要先拿到钥匙才能
穿过门。
我只能想到暴力的方法，爆炸指数。有谁能想出更好的办法，或者把我引向一个解决这个问题的地方吗或者让我相信这很难（从计算上讲）？谢谢你的帮助！
最佳答案
这个问题是np-难最优解的。哈密顿路径问题有一个简单的简化：
在原始图形的每个顶点上放置唯一的项。构造仅连接到目标顶点的汇顶点。让这两个顶点之间的边需要所有项。