蛮力算法

通过每个顶点一次的路径与以某种方式排序顶点相同。因此,为了计算通过每个顶点一次的最小成本,我们可以对从 1N 的数字的 N! 排列中的每一个进行暴力破解。

伪码

minimum = INF
for all permutations P

    current = 0                                

    for i from 0 to N-2
        current = current + cost[P[i]][P[i+1]]  <- Add the cost of going from 1 vertex to the next
    
    current = current + cost[P[N-1]][P[0]]      <- Add the cost of going from last vertex to the first

    if current < minimum                        <- Update minimum if necessary
        minimum = current
    
output minimum

时间复杂性

N! 排列通过,每个路径的成本在 O(N) 中计算,因此这个算法需要时间 6 来输出确切的答案。