욕심 많은 알고리즘의 복잡성

Question

최소 가중치 - 해밀턴 회로 문제를 해결하는 욕심 많은 알고리즘을 만들었습니다. 알고리즘은 항상 가장 싼 에지를 선택합니다. 현재 에지에서 회로를 찾지 못하면 알고리즘이 떨어집니다 마지막 가장자리와 여기

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

귀하의 알고리즘은 경로를 찾기 위해 무력을 사용하는 의사가 그렇게이며, 누군가가 나 로 설명 할 수 있습니다,이 알고리즘의 복잡성에 대한 다음 cheapest.I'm 확실하지 않은 선택합니다 최대 실행 시간은 O(n!) (완전히 연결된 그래프의 경우)입니다. 마지막으로 확인한 경로는 하나 일 수 있습니다.

대부분의 실제 사례에서이 알고리즘은 더 빠릅니다. 문제는 일반적으로 다른 이름 인 여행 판매원 문제로 참조됩니다. 위키 피 디아는 너보다 빠른 a list of good algorithms and heuristics입니다.