2016-12-19 96 views
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 

回答

1

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

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