貪心算法的複雜性

Question

我做了一個貪心算法，解決最小加權哈密頓迴路問題。算法總是選擇最便宜的邊緣，如果沒有辦法從當前邊緣集合中找到電路，那麼算法會下降最後的邊緣，並挑選下一個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 

Answer 1

你的算法使用蠻力找到一個路徑的僞代碼，所以最大運行時間爲O(n!)（對於完全連接的圖）。可能只有一條可能的路線，您檢查的最後一條路線。

在大多數現實世界的情況下，這個算法會更快。問題通常以其他名稱引用：旅行商問題。維基百科有a list of good algorithms and heuristics比你的更快。