欲張りアルゴリズムの複雑さ

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!)（完全に接続されたグラフの場合）です。可能なルートは1つだけあり、最後にチェックするルートです。

ほとんどの場合、このアルゴリズムは高速になります。この問題は、通常、旅行代理店の問題という別の名前で参照されます。 Wikipediaにはあなたよりも速いa list of good algorithms and heuristicsがあります。