我需要在带圈的加权图中找到两个节点之间最便宜和最短的路径。我正在Prolog中实现这一点。
由于我必须找到最便宜的(最便宜的)和最短的(最短的)路径,所以我认为应该使用深度搜索来计算现有的所有可能的路径--首先使用回溯搜索,因为它的内存消耗较低,而且速度相对较快(我使用一个辅助列表来跟踪访问的节点以处理循环问题),然后从收集到的路径列表中选择最便宜和最短的路径。
我排除了使用启发式算法(例如A*)的可能性,因为这些算法虽然速度更快,但依赖于估计函数,而且在某些具体情况下,估计可能是错误的,它们可能给出错误的答案。我不想要一个好的解决方案,我想要最好的解决方案。
因此,我的问题是:我给出的解决这个问题的方法是否更有意义,更确切地说,是为了确保我在有循环的两个节点之间的图问题中得到了最多或最便宜的路径,是否有意义计算所有现有的解决方案,然后通过将其与其他方案进行比较来选择正确的方案,还是我处理这个问题的方法是错误的?
发布于 2016-12-03 21:45:47
这里没有必要使用自定义算法。您可以使用一个标准的最短路径查找算法(Dijkstra的,如果所有的权重是非负的,福特-Bellman或弗洛伊德的,否则)。边的权重应该分别是第一个问题和第二个问题的代价和距离。
https://stackoverflow.com/questions/40952628
复制相似问题