在做一个项目的时候,我偶然发现了一个我无法解决的图形算法问题。问题如下:
您有一个有向加权图,并希望在访问指定节点(非常类似于)时,在开始节点和结束节点之间找到最短路径。但是,除了节点和边之外,这个图还有"items“的概念,它驻留在节点上,当您进入该节点时,您就会”拾取“。现在有一个额外的约束,即只有在获得了必要的项( I )的情况下,才能遍历边缘。把它看作是门的钥匙,你需要在能够通过门之前获得一把钥匙。
我只能想到强力的方法能成倍地爆炸。有人能想到更好的办法吗?或者带我去一个解决这个问题的地方?或者让我相信这“很难”(从计算上讲)?谢谢你的帮助!
众所周知,计算具有最小可能叶数的生成树是NP完全的。但是我不能把这个问题转化为哈密顿路径问题的多项式时间缩减。
我的指数递减:
if(hamiltonian path exists for whole graph)
min leaves = 1;
return;
else
for each vertex of the graph
if(hamiltonian path exists for this graph after removing the vertex and its incident edges)
min leave