Vuelta atrás

Vuelta atrás (Backtracking) es una estrategia para encontrar soluciones a problemas que satisfacen restricciones. El término "backtrack" fue acuñado por primera vez por el matemático estadounidense D. H. Lehmer en la década de 1950.

Ejemplo de árbol de búsqueda. Nótese que el árbol no tiene por qué ser binario.

Enfoques

Los problemas que deben satisfacer un determinado tipo de restricciones son problemas completos, donde el orden de los elementos de la solución no importa. Estos problemas consisten en un conjunto (o lista) de variables a la que a cada una se le debe asignar un valor sujeto a las restricciones del problema. La técnica va creando todas las posibles combinaciones de elementos para obtener una solución. Su principal virtud es que en la mayoría de las implementaciones se puede evitar combinaciones, estableciendo funciones de acotación (o poda) reduciendo el tiempo de ejecución.

Vuelta atrás está muy relacionado con la búsqueda combinatoria.

Other Languages
български: Бектрекинг
čeština: Backtracking
Deutsch: Backtracking
English: Backtracking
français: Retour sur trace
italiano: Backtracking
한국어: 퇴각검색
Nederlands: Backtracking
português: Backtracking
română: Backtracking
српски / srpski: Бектрекинг
українська: Пошук з вертанням
中文: 回溯法