贪心算法的复杂性
贪心算法的复杂性
提问于 2016-12-19 18:20:35
我做了一个求解最小加权哈密顿电路的贪心算法problem.The算法总是选择最便宜的边，如果没有办法从当前边集中找到电路，那么该算法丢弃最后一个边，然后选择下一个最便宜的边。我不确定这个算法的复杂性，有人能给我解释一下吗?这里是伪代码
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回答
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/41220374
复制相关文章
相似问题
腾讯云开发者
