图的遍历与任何来源的最短路径 [英] Graph traversal with shortest path with any source

问题描述

您只能给一个双向加权图。现在你已经遍历开始使路径总长度最小的任何源整个图。 强力方法将遍历所有的排列，并给予最低程度。

You're given a bidirectional weighted graph. Now you've to traverse the whole graph starting with any source making the total path length minimum. Brute force approach will be to traverse all the permutations and give the minimum.

我应该是解决这类问题的正确方法呢？

What should be the correct approach to solve this kind of problems?

推荐答案

有没有多项式时间算法对于这个问题，因为旅行商还原为它并没有多项式时间算法TSP.But你总是可以改进对暴力使用动态规划这一问题。您可以将DP作为TSP，以减少时间复杂度为 O（2 ^ N）

there no polynomial time algorithm for this problem because travelling salesman is reducible to it and there is no polynomial time algorithm for TSP.But you can always improve over brute force using Dynamic Programming in this problem. You can apply DP as in TSP to reduce time complexity to O(2^N)

持有卡普算法是算法，使用动态编程来获得O（2 ^ N）为TSP和可以用于通过在您porblem轻微的变化。

Held-Karp algorithm is algorithm which uses dynamic programming to get O(2^N) for TSP and can be used by slight variation on your porblem.

否则，使用启发式算法来找到很好的解决办法： -

Otherwise use heuristic algorithm to find good solutions : -

遗传算法

蚁群优化

这篇关于图的遍历与任何来源的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！