0
我做了一個貪心算法,解決最小加權哈密頓迴路問題。算法總是選擇最便宜的邊緣,如果沒有辦法從當前邊緣集合中找到電路,那麼算法會下降最後的邊緣,並挑選下一個cheapest.I'm不能確定該算法的複雜性,可有人向我解釋 這裏是貪心算法的複雜性
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