Search code examples
backtrackingheuristics

Is backtracking considered an heuristic?


More specifically, I am trying to figure out if the following statement is correct:

Every BackTracking is an Heuristic but not every Heuristic is a BackTracking.

Am I right? Cause I feel I am missing something and messing things up.


Solution

  • I think the only question here is: "Is every backtracking a heuristic?"

    Backtracking is a general algorithm for finding all (or some) solutions to SOME computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions and abandons each partial candidate as soon as it determines that it cannot possibly be completed to a valid solution.

    Backtracking should be relatively fast, therefor it is used to determine whether or not a candidate is a valid solution (a rough selection is done). As backtracking obviosly not work with precise solutions, it is definitely a general heuristic method.

    Of course, backtracking is not the only metaheuristic principle, so the second part of the sentence does not make sense.