在遍历边上约束的最短路径

在处理一个项目时，我偶然发现了一个I 未能解决的图算法问题。问题如下：在遍历边上约束的最短路径

你有一个导向，加权图，并希望找到一个开始节点和在访问指定的节点终端节点（很像 Find the shortest path in a graph which visits certain nodes）之间的最短路径。然而，随着节点和边缘，这个图表还有“项目”的概念，驻留在节点上，当你进入该节点时你“拾起”。现在还有一个额外的限制条件，如果您已经获得必要的项目，则该边缘只能穿过，对于该特定边缘，边缘只能获得I。认为它是一扇门的钥匙;您需要先获得钥匙才能通过。

我只能想到以指数方式爆炸的蛮力方法。任何人都可以想到更好的东西，或者将我指向解决这个问题的地方？或者也许说服我，这是“硬”（从计算上讲）？谢谢你的帮助！

来源

2013-10-04 maxnelso

有多少种不同的物品？ – templatetypedef

只是一种取决于游戏（你可能已经猜到这是通过视频游戏遍历），但我会说30-40的顺序。 – maxnelso

是否有某种好的订购项目？也就是说，这些项目是否大致遵循线性进展？ – templatetypedef

这个问题是NP-HARD最佳解决方案。哈密尔顿路径问题有一个简单的减少：

将独特的项目放在原始图形的每个顶点上。构建仅连接到目标顶点的sink顶点。让这两个顶点之间的边缘需要所有的项目。

来源

2013-10-04 20:24:27 tskuzzy

这是如何工作的？你能发布一个代码示例吗？ – Bytemain

tskuzzy正在构建一个图表，您可以*访问每个顶点从开始到结束。假设每条边都具有相同的重量。如果一个图有一个哈密尔顿循环，那么这个循环就是最优解。如果最优解不是哈密顿周期，那么该图没有一个。因此，如果你给我你的算法，我可以用它来解决任何图的HC。 – DanielV

嗯，结果有点令人失望，但谢谢！ – maxnelso

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

来源

2013-10-04 20:02:39 Bytemain

在遍历边上约束的最短路径

回答

相关问题