Complexity of the greedy algorithm

956 views Asked by At

I made a greedy algorithm that solves minimum-weighted-Hamiltonian-circuit problem.The algorithm always picks the cheapest edge,if there is no way to find the circuit from the current edges set then the algorithm drops the last edge and picks the next cheapest.I'm not sure about the complexity of this algorithm,can someone explain it to me Here is the pseudocode

    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

There are 1 answers

0
Filip Haglund On

Your algorithm uses brute force to find a path, so the maximum running time is O(n!) (for a fully connected graph). There might only be one possible route, the last one you check.

In most real-world cases, this algorithm will be faster. The problem is usually referenced to by its other name: the traveling salesman problem. Wikipedia has a list of good algorithms and heuristics that are faster than yours.