Let's say I want to find a Hamiltonian circuit. If my algorithm has no edges to visit, should it return false or go back to the place where it can do something?
Asked
Active
Viewed 54 times
1 Answers
2
Hamilton circuit finding is an NP-hard problem, so by consequence there is no greedy algorithm to always successfully find one when it is possible. This means indeed that an algorithm that initially takes a greedy approach, and is unsuccessful, will need to backtrack and choose another route to try again.
trincot
- 317,000
- 35
- 244
- 286
-
There is something about the way this answer was formulated which is very appealing. – Maurycyt Oct 07 '20 at 19:20