Сложность жадного алгоритма

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, которые быстрее вашего.