优先图中的最短路径

我正在寻找一种算法，以考虑连接图来确定优先图的最短路径。我看了一下Dijkstra和Bellman Ford，但我认为他们对于优先图并不可行，因为他们只在每个顶点的一个边上向外。但是在优先图中，还有一些情况需要通过两条或更多条边到达下一个顶点。例如，要拆卸，必须首先删除零件A和B，然后才能到达零件C.优先图中的最短路径

我试图解决的问题：我有一个简单的优先图表示如何拆卸产品。每个顶点都有一个成本（时间单位）。在这张图中，我有一个开始和目的地。结果应该是拆卸所需的最短时间。

另外需要考虑的是，您可以根据连接图将整个反模块拆卸到一个特定的部分。该图显示了各部分是如何实际相互连接的。像A一样，B和C必须被移除以达到D.A必须首先被移除。然后，您可以将B和C作为一个整体删除（删除C，而B仍然附着在它上面）。

来源

2016-05-30 kinglite

不幸的是，问题是NP完全[参考]（http://www.tandfonline.com/doi/abs/10.1080/00207540701476281）。有近似解的贪婪方法和启发式，但主要不是图遍历，而是组合问题。 – BeyelerStudios

正如我担心的那样。感谢您的回复。你有一个解决方案的简单方法来源？ – kinglite

您是否尝试联系上述论文的[作者]（http://www1.coe.neu.edu/~smgupta/）（s）？ – BeyelerStudios

我现在使用Deep-first搜索算法进行了一些修改，以适合我的第一部分的目的。第二部分，模块应该被认为是拆卸而不是每一个单一的和平，但仍然缺失。也许对算法进行一些更改也是可能的。

来源

2016-06-10 05:44:24 kinglite

优先图中的最短路径

回答

相关问题