La vuelta hacia atrás es un tipo de algoritmo que sea un refinamiento de la búsqueda de la fuerza bruta. En la vuelta hacia atrás, las soluciones múltiples pueden ser eliminadas sin explícitamente el examen, usando las características específicas del problema. Puede ser una estrategia para encontrar soluciones a los problemas de satisfacción del constreñimiento el " del término; backtrack" fue acuñado por el ADO americano del matemático. Lehmer en los años 50.
Explicación
Los problemas de satisfacción del constreñimiento son problemas con una solución completa, donde no importa la pedido de elementos. Los problemas consisten en un sistema de las variables que se deben asignar un valor, conforme a los apremios particulares del problema. El retroceso intenta intentar todas las combinaciones para obtener una solución. Su fuerza que muchas puestas en práctica evitan intentar muchas combinaciones parciales, así está acelerando el funcionar-tiempo .
La vuelta hacia atrás es estrechamente vinculada a la búsqueda combinatoria .
Puesta en práctica
Los algoritmos de la vuelta hacia atrás intentan cada posibilidad hasta ellos encuentran el derecho. Es una Profundidad-primera búsqueda del sistema de soluciones posibles. Durante la búsqueda, si una alternativa no trabaja, la búsqueda retrocede al punto bien escogido, el lugar que presentó diversas alternativas, e intenta la alternativa siguiente. Cuando se agotan las alternativas, la búsqueda vuelve al punto bien escogido anterior e intenta la alternativa siguiente allí. Si no hay puntos bien escogidos, la búsqueda falla.Esto se alcanza generalmente en una función recurrente donde cada caso toma uno más variable y le asigna alternativo todos los valores disponibles, guardando el que es constante con llamadas recurrentes subsecuentes. La vuelta hacia atrás es similar a una profundidad-primera búsqueda pero a las aplicaciones incluso menos espacio, guardando apenas un estado actual de la solución y poniéndolo al día.
Para acelerar la búsqueda, cuando un valor se selecciona, antes de hacer la llamada recurrente, el algoritmo cualquiera las cancelaciones que valoran de los dominios no asignados que están en conflicto (comprobación delantera) o de los cheques todos los apremios para considerar lo que valora otra este valor nuevo-asignado excluye (propagación de constreñimiento). Ésta es la técnica más eficiente para ciertos problemas como 0/1 problema de la mochila y de la n-reina. Da a mejores resultados que la programación dinámica para estos problemas.
Heurística
Vario la heurística es común acelerar el proceso. Porque las variables se pueden procesar en cualquier orden, es generalmente eficiente intentar obligados primero (es decir las que está con pocas opciones del valor) pues esto poda el árbol de la búsqueda temprano (maximiza el impacto de la opción temprana del actual ).Al elegir qué valor a asignar, utilizan muchas puestas en práctica adelante la comprobación para considerar qué valor restringe el menos número de valores, en la anticipación que tal opción es a) más probable preservar una solución posible y b) una solución se ha encontrado cuando el número de apremios excepcionales se ha reducido a cero.
Las puestas en práctica sofisticadas de la vuelta hacia atrás utilizan a menudo una función de limitación, que comprueba si es posible obtener una solución, para la solución parcial actual. Así, una prueba de limitación que detecta las soluciones parciales que el fall puede mejorar eficacia de la búsqueda. Porque se funciona a menudo, posiblemente en cada paso, el coste de cómputo de limitación necesita ser mínimo, si no la eficacia total del algoritmo no se mejora. Las funciones de limitación eficaces son creadas en una manera similar a otras funciones heurísticas - relajando las reglas del problema levemente.
Cuando la vuelta hacia atrás se utiliza en una lengua de la programación de constreñimiento, los gastos indirectos agregados ocurren desde la información sobre los apremios, usados por el disolvente del constreñimiento sí mismo, necesitan ser puestos al día también. En estas idiomas, una Profundidad-primera búsqueda simple es una técnica adecuada de la puesta en práctica, según lo utilizado en el planificador y el prólogo .
Además de conservar los valores mínimos de la recuperación usados en el respaldo, retrocediendo las puestas en práctica guardan comúnmente un rastro variable, para registrar historia del cambio del valor. Una puesta en práctica eficiente evitará crear una entrada variable del rastro entre dos cambios sucesivos cuando no hay punto bien escogido, pues la vuelta hacia atrás borrará todos los cambios como sola operación.
Una alternativa al rastro variable es guardar un grupo fecha/hora de cuando el cambio pasado fue realizado a la variable. El grupo fecha/hora se compara al grupo fecha/hora de un punto bien escogido. Si el punto bien escogido tiene un rato asociado más adelante que el de la variable, es innecesario invertir la variable cuando se retrocede el punto bien escogido, pues fue cambiado antes de que ocurriera el punto bien escogido.
Usos
El uso más extenso de la vuelta hacia atrás está en la ejecución de las expresiones regulares por ejemplo, el " simple del patrón;a*a" no podrá emparejar el " de la secuencia; aa" sin la vuelta hacia atrás (porque, en el primer paso, el primer " a" es comido por el " *" no dejando nada detrás para el " restante; a" al fósforo.) Otro de uso común de la vuelta hacia atrás es en los algoritmos el encontrar de trayectoria donde la función remonta sobre un gráfico de nodos y retrocede hasta que encuentre la menos trayectoria del coste.
La vuelta hacia atrás se utiliza en la puesta en práctica de los lenguajes de programación (tal como icono, planificador y prólogo ) y de otras áreas tales como del texto que analiza .
| Random links: | Tableta de gráficos | Puerto del roble, Ohio | James Bulwer | Crécy-en-Ponthieu |