Volver atrás

Backtracking es una técnica para encontrar soluciones a problemas donde las restricciones deben ser satisfechas. Esta técnica enumera todas las soluciones posibles y descarta aquellas que no cumplen con las restricciones. Una técnica clásica es explorar estructuras de árboles y realizar un seguimiento de todos los nodos y ramas visitados anteriormente, para que pueda volver al nodo más cercano que contenía una ruta aún inexplorada en caso de que la búsqueda en la rama actual no tenga éxito. Los nodos de igual profundidad representan los valores posibles de una variable. Una aplicación de backtracking está en los programas para jugar ajedrez, que generan todos los movimientos posibles para una profundidad de N movimientos a partir de la actual y luego examinan con backtracking las diversas alternativas, seleccionando al final la mejor. El retroceso tiene una complejidad exponencial, por lo que es ineficiente para lidiar con problemas que no son NP-completos. En general, sin embargo, el algoritmo integra heurística que permite disminuir su complejidad. Esta técnica es la base del lenguaje de programación Prolog.

Los posibles tipos de retroceso son muchos, con diferentes operaciones, diferentes características y diferentes ventajas. Los más conocidos son: los primeros cuatro algoritmos son algoritmos fundamentales definidos, ya que representan diferentes "filosofías" de la base, y diferentes métodos para implementar el backtracking; mientras que el último es, en cambio, un ejemplo bien conocido de un algoritmo híbrido, es decir, un algoritmo que puede considerarse una variación de los algoritmos básicos, pero que es precisamente la diferencia de los Algoritmos de los que se deriva puede traer muchos beneficios.

Un problema que se puede resolver con este método es el de la satisfabilidad de una proposición en lógica de primer orden (K - SAT). El algoritmo procede estableciendo el valor de cada variable, hasta que la fórmula está satisfecha (supongamos que es satisfacible). Por simplicidad tomamos la fórmula x ∧ y {\displaystyle x \ land y} , la técnica procede de la siguiente manera: el ejemplo en forma de código Python (el código no se detiene cuando encuentra el resultado): produce como resultado .

Sin fuentes de programación

Inteligencia artificial

Algoritmos de búsqueda

Sistema inmune Artificial

El método del sistema inmune artificial (AIS) es un tipo de algoritmo de optimización inspirado en los principios y procesos del sistema inmune de los seres viv...

Abstracción (Ciencias de la computación)

L ' Abstracción-en Ciencias de la computación, es la aplicación del método lógico de abstracción en la estructuración de la descripción de sistemas informáticos...

Algoritmos de optimización

Conceptos de programación

Gestión de datos

Esta página se basa en el artículo de Wikipedia: Fuente, Autores, Licencia Creative Commons Reconocimiento-CompartirIgual.
This page is based on the Wikipedia article: Source, Authors, Creative Commons Attribution-ShareAlike License.
contactos
Política de privacidad , Descargos de responsabilidad