1
$\begingroup$

Backtracking search is the basic uninformed algorithm for CSPs (constraint satisfaction problems). What are the directions along which backtracking efficiency can be improved ?

$\endgroup$
  • $\begingroup$ According to the question, you want to use Artificial Intelligence techniques to improve backtracking search in state space. This is needed, if the problem isn't a toy-problem and backtracking alone would take too long, right? $\endgroup$ – Manuel Rodriguez Nov 23 '18 at 16:52
  • $\begingroup$ Backtracking algorithms can be improved by adding heuristics methods. You could add filtering and ordering techniques. $\endgroup$ – Thuriya Thwin May 28 at 0:45
0
$\begingroup$

A variant of depth-first search called backtracking search uses still less memory.In backtracking, only one successor is generated at a time rather than all successors ; each paritally expanded node remembers which successor to generate next. In this wat,only O(m) memory is needed rather than O(bm). Backtracking search facilities yet another memory-saving (and time saving) trick: the idea of generating a successor by modifying the current state description directly rather than copying it first.This reduces the memory requirement to just one state description and O(m) actions.This is one from various ways through which efficiency of backtracking search algorithm can be improved. And also for this to work,we must be able to undo each modification when we go back to generate the next successor.For problems with large scale descriptions,such as robotic assembly, these techniques are critical to success.

$\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.