backjumping
Sign in to saveIn constraint programming and SAT solving, backjumping (also known as non-chronological backtracking or intelligent backtracking) is an enhancement for backtracking algorithms which reduces the search space. While backtracking always goes up one level in the search tree when all values for a variable have been tested, backjumping may go up more levels. In this article, a fixed order of evaluation of variables x_1,\ldots,x_n is used, but the same considerations apply to a dynamic order of evaluation.
Wikidata facts
- Subclass of
- backtracking
- Image
- Backtracking-with-backjumping.svg
Sources (1)
via Wikidata · CC0
Article · Español
En algoritmos de backtracking, el backjumping es una técnica que reduce espacio de búsqueda, y por tanto, aumenta la eficacia de esta. Mientras que el backtracking siempre remonta un nivel en el diagrama de árbol cuando todos los valores para una variable han sido probados,el backjumping puede remontar más niveles. En este artículo, se utiliza un orden fijo de evaluación de variables, pero las mismas consideraciones se aplican para un orden dinámico de evaluación. * Un diagrama de árbol utilizando el backtracking. * Un salto hacia atrás: el nodo gris no ha sido visitado.
Abstract from DBpedia / Wikipedia · CC BY-SA