0

我做了一个贪心算法来解决最小加权哈密顿电路问题。该算法总是选择最便宜的边缘，如果无法从当前边缘集合中找到电路，那么算法会丢弃最后一个边缘并选择下一个最便宜的边缘.我不确定这个算法的复杂性，谁能给我解释一下这是伪代码

    HC(currentVertex,expandedVertices,path,sum,N)
    if size(expandedVertices)==N then
        print(path)
        return sum
    end if
    expandedVertices.add(currentVertex)
    vertices=getAdjacentNodes(expandedVertices)
    sort(vertices)
    for i=1 to size(vertices) do
        path.append(vertices[i])
        cost=HC(vertices[i],expandedVertices,path,sum+getEdgeCost(currentVertex,
           vertices[i]),N)
        if(cost>0) then
            break
        end if
        path.remove(vertices[i])
    expandedVertices.remove(currentVertex)
    return cost
4

1 回答 1

1

您的算法使用蛮力来寻找路径，因此最大运行时间是O(n!)（对于完全连接的图）。可能只有一种可能的路线，即您检查的最后一条路线。

在大多数实际情况下，此算法会更快。这个问题通常用它的另一个名字来引用：旅行商问题。Wikipedia列出了比您更快的优秀算法和启发式算法。

于 2016-12-19T10:48:08.993 回答