Backtracking constructs a tree of partial solutions until algorithm finds out that this solution is wrong or right. Technique, when algorithm stops searching down the tree if any children nodes are evidently wrong is called search pruning.
Applications:
- traveling salesman
- schedule optimization
- robotics
- AI
- mind games like chess and even go
- puzzles like crosswords, sudoku
is any approach to problem solving, learning, or discovery that employs a practical method not guaranteed to be optimal or perfect, but sufficient for the immediate goals
Search space is set of all possible solutions.
Simulated annealing is a technique for searching approximate global minimum/maximum. Often used when search space is discrete.
Three components:
– concise problem representation – search space and cost function – transitions – how to move from one state to another one – cooling schedule – which tells algorithm that it has to gamble less
Can be applied to solve combinatorial problems, but simulated annealing is more preferred.
Author don't recommend using them in practice because they're the less effective ones.
They can speed your algorithm up, but they also introduce you to many other types of problems.
slideshare.net – BackTracking Algorithm: Technique and Examples