Correct me if I'm wrong but can't the nearest neighbor algorithm be used to find a Hamiltonian Circuit in an arbitrary graph and hence proved P = NP?
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
0
|
|
|
|
|
2
|
The nearest neighbor algorithm as I understand it (repeatedly select a neighboring vertex that hasn't been visited yet and travel to that vertex) does not guarantee that you will find a circuit even if one exists. For example consider the graph with vertices A,B,C,D with edges AB, AC, AD, BC and CD (a complete graph on 4 vertices with edge BD removed). Starting at A, you travel to C. You can then travel to either B or D, at which point your only choice is to go back to A. So if you go from A to C, you can't complete the loop and construct a Hamiltonian circuit even though one exists. |
||
|
|
