[Skydiver]

blackcompe, on 26 August 2012 - 01:35 AM, said:

2. This paper (pg. 14) gives an algorithm for finding the optimal Hamiltonian path, although it's a little tough to decipher.

What little of if I can decipher indicates that you have to pick a node 'p' as the final node, and then apply the algorithm. But what if I picked a bad 'p'? So that then means that I need to do the algorithm V-1 times to make sure that I picked the best 'p' or find a better 'p'.

So given lines 3-4 already show this:

for s = 1 to N-2
    for i,j = 1 to N 

This looks like O(n³) to me. Doing another loop to try out all the possible p's would bring this algorithm up to O(n⁴). Am I missing something?

Still beats O(n!), though.

This post has been edited by Skydiver: 27 August 2012 - 11:30 AM