I'm currently taking an Algorithms course, and we are covering Backtracking, CSP, and heuristics. However, I'm getting confused on exactly the differences between these terms and their applications.
When using Backtracking on a problem, I understand we are calculating the set of all allowable solutions to satisfy some property. This uses the idea of some form of constraint to make sure we can reduce the problem and not have to calculate every possible permutation.
So is the Backtracking algorithm just an application of a CSP? But when I saw an example of solving a sudoku puzzle with the Backtracking algorithm, it took many more steps than a CSP description of it.
Also, how would the idea of using heuristics to solve a problem relate in with this?
There is a good chance I'm getting confused with some of the terminology so any advice would be greatly appreciated.
Asked By : Brant Kapple
Answered By : Realz Slaw
CSP is a problem.
Backtracking is an algorithm that searches for a solution, basically, by trying every possibility, and backtracking as soon as it knows it is wrong. Thus it can be applied to many problems, by searching the solution space.
A heuristic algorithm is an algorithm that finds a solution using some trick to speed it up. Some heuristic algorithms might work well for particular types of problems, while remaining slow in the worst-case. Other heuristic algorithms might terminate quicker, but in the worst-case might not find a solution, or it can find an approximate solution.
From wikipedia:
This is achieved by trading optimality, completeness, accuracy, or precision for speed.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/16723
0 comments:
Post a Comment
Let us know your responses and feedback