1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Backtracking algorithm is a way to solve the CSP. While backtracking the algorithm may have to chose from several nodes, which will be the next one to expand. This is the point, where heuristic can be used.

Lets use the representation of the CSP as set of variables, each with its own domain of values. Here are two popular heuristics:

Minimal Remaining Values - Chose the variable that has minimal remaining values it can take.

Least Constraining Values - Chose a value of some variable that will be least constraining for all other variables

Using those generally(in "complex enough" CSP) will find a solution faster, because it chooses in optimal way the next node in the search tree to be expanded.

Here is a very helpful link ,that gives full description with examples.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.