{{Referencia}} 

Estructuras secuenciales 

 

La estructura secuencial es aquella en la que una acción (instrucción) sigue a otra en secuencia. Las tareas se suceden de tal modo que la salida de una es la entrada de la siguiente y así sucesivamente hasta el fin del proceso.

 

== Componentes ==

===  Asignación ===

La asignación consiste, en el paso de valores o resultados a una zona de la memoria. Dicha zona será reconocida con el nombre de la variable que recibe el valor. La asignación se puede clasificar de la siguiente forma: • Simples: Consiste en pasar un valor constate a una variable (a=15) • Contador: Consiste en usarla como un verificador del número de veces que se realiza un proceso (a=a+1) • Acumulador: Consiste en usarla como un sumador en un proceso (a=a+b) • De trabajo: Donde puede recibir el resultado de una operación matemática que involucre muchas variables (a=c+b*2/4).

===  Lectura ===

La lectura consiste en recibir desde un dispositivo de entrada (p.ej. el teclado) un valor. Esta operación se representa en un pseudocodigo como sigue: Leer a, b Donde “a” y “b” son las variables que recibirán los valores

===  Escritura ===

Consiste en mandar por un dispositivo de salida (p.ej. monitor o impresora) un resultado o mensaje. Este proceso se representa en un pseudocodigo como sigue:

Escribe “El resultado es:”, R Donde “El resultado es:” es un mensaje que se desea aparezca y R es una variable que contiene un valor. 

 

== Ejemplos ==

Los algoritmos que necesitan de estructuras secuenciales para su solución son los mas difíciles de comprender y mas sencillos de identificar los procesos que realizará el programa que nos llevarán a la solución del mismo. En algunos algoritmos se omite la declaración de variables, en casos que el algoritmo no es complicado.

Ejercicio 1

Hacer el rastreo manual para: a = 2 a = a + 1 b = a * 2 b = b - 1 c = a + 2 * b Presentar "c".

RASTREO: Para el rastreo hay que asignarle a cada línea un número, de la siguiente manera, de antemano ya nos habremos fijado que el valor de salida es el de la variable c, el problema sería saber el valor de esta variable c que se mostrará finalmente. 1) a = 2 2) a = a + 1 3) b = a * 2 4) b = b - 1 5) c = a + 2 * b 6) Presentar "c".

Línea 1: a=2 Línea 2: a=2+1=3 Línea 3: b=3*2=6 Línea 4: b=6-1=5 Línea 5: c=3+2*5=13 Línea 6: Se presenta 13 El valor de la variable c será 13.

Ejercicio 2

Hacer el algoritmo para escribir un programa que evalúe la expresión Solución: observe que los valores de ingreso serán para las variables x, w.

Algoritmo Inicio Declare Resultado, x, w Leer x,w Resultado (x+w)/(2*w) Mostrar Resultado Fin

Variables resultado: valor de la expresión luego de ser evaluada. x : guarda un valor numérico ingresado. w : guarda un valor numérico ingresado.

Programa #include<stdio.h> main(void) {float resultado,x,w; //se escriben dos valores separados por la barra espaciadora printf("ingrese el valor de x , también de w \n"); //se leen o capturan dos valores escritos en las variables x y w. scanf("%f %f",&x,&w); //Se evalúa la expresión y el resultado es asignado a la variable resultado. resultado=(x+w)/(2*w); //se imprime el valor de la variable resultado. printf("%f",resultado); } 

== Referencia ==

*Urbaez, Wilder.'' Explicamos las estructuras secuenciales, cómo se representan en pseudocódigo y algunos ejemplos prácticos de las mismas. '' 

 

 

[[Category:Algoritmos]]

Algoritmo

2010-04-30T17:57:44Z

Asanto uci:

Algoritmo de búsqueda

2010-04-30T17:51:59Z

Asanto uci:

{{Referencia}} 

Algoritmo de búsqueda 

Un algoritmo de búsqueda es aquel que está diseñado para localizar un elemento concreto dentro de una estructura de datos. Consiste en solucionar un problema de existencia o no de un elemento determinado en un conjunto finito de elementos, es decir, si el elemento en cuestión pertenece o no a dicho conjunto, además de su localización dentro de éste. Este problema puede reducirse a devolver la existencia de un número en un vector.

== Búsqueda secuencial ==

Se utiliza cuando el contenido del vector no se encuentra o no puede ser ordenado. Consiste en buscar el elemento comparándolo secuencialmente (de ahí su nombre) con cada elemento del array hasta que éste se encuentre, o hasta que se llegue al final del array. La existencia se puede asegurar desde el momento que el elemento es localizado, pero no podemos asegurar la no existencia hasta no haber analizado todos los elementos del array. A continuación se muestra el pseudocódigo del algoritmo: Datos de Entrada: vec: vector en el que se desea buscar el elemento tam: tamaño del vector dato: elemento que se quiere buscar.

Variables pos: posición actual en el array

pos = 0 Mientras pos < tam: Si vec[pos]== dato devolver verdadero y/o pos, de lo contrario: pos = pos + 1

Fin (Mientras) Devolver falso

== Búsqueda binaria (dicotómica) ==

Se utiliza cuando el vector en el que queremos determinar la existencia o no de un elemento está ordenado, o puede estarlo, este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente con el número de iteraciones. Para implementar este algoritmo se compara el elemento a buscar con un elemento cualquiera del array (normalmente el elemento central), si el valor de éste es mayor que el del elemento buscado se repite el procedimiento en la parte del array que va desde el inicio de éste hasta el elemento tomado, en caso contrario se toma la parte del array que va desde el elemento tomado hasta el final. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible, con el elemento buscado como elemento central. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en el arreglo. A continuación se presenta el pseudocódigo del algoritmo, tomando como elemento inicial el elemento central del array. Datos de Entrada: vec: vector en el que se desea buscar el elemento tam: tamaño del vector dato: elemento que se quiere buscar.

Variables centro: elemento central del intervalo inf: límite inferior del intervalo sup: límite superior del intervalo

inf = 0 sup = tam–1

Mientras inf <= sup: centro = ((sup + inf) / 2) /* división entera: se trunca la parte decimal */ Si vec[centro] == dato devolver verdadero y/o pos, de lo contrario: Si dato < vec[centro] entonces: sup=centro–1 En caso contrario: inf=centro+1

Fin (Mientras) Devolver Falso

== Referencias ==

1.  http://img291.imageshack.us/img291/9047/busqueda.jpg

 

[[Category:Algoritmos]]

2010-04-29T19:36:18Z

Asanto uci:

Vuelta atrás (backtracking)

2010-04-29T19:14:28Z

Asanto uci:

{{Referencia}}

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 los años 1950s.

== Concepto ==

En su forma básica, la idea de backtracking se asemeja a un recorrido en profundidad dentro de un grafo dirigido. El grafo en cuestión suele ser un árbol, o por lo menos no contiene ciclos. Sea cual sea su estructura, existe sólo implícitamente. El objetivo del recorrido es encontrar soluciones para algún problema. Esto se consigue construyendo soluciones parciales a medida que progresa el recorrido; estas soluciones parciales limitan las regiones en las que se puede encontrar una solución completa. El recorrido tiene éxito si, procediendo de esta forma, se puede definir por completo una solución. En este caso el algoritmo puede bien detenerse (si lo único que se necesita es una solución del problema) o bien seguir buscando soluciones alternativas (si deseamos examinarlas todas). Por otra parte, el recorrido no tiene éxito si en alguna etapa la solución parcial construida hasta el momento no se puede completar. En tal caso, el recorrido vuelve atrás exactamente igual que en un recorrido en profundidad, eliminando sobre la marcha los elementos que se hubieran añadido en cada fase. Cuando vuelve a un nodo que tiene uno o más vecinos sin explorar, prosigue el recorrido de una solución.

 

Algoritmo de Backtracking

proc Backtracking (↕X[1 . . . i ]: TSolución, ↑ok: B)
variables L: ListaComponentes
inicio
si EsSolución (X) entonces ok CIERTO
en otro caso
ok FALSO
L=Candidatos (X)
mientras ¬ok ^ ¬Vacía (L) hacer
X[i + 1] Cabeza (L); L Resto (L)
Backtracking (X, ok)
finmientras
finsi
fin

Podemos visualizar el funcionamiento de una técnica de backtracking como la exploración en profundidad de un grafo.

Cada vértice del grafo es un posible estado de la solución del problema. Cada arco del grafo representa la transición entre dos estados de la solución (i.e., la toma de una decisión).

Típicamente el tamaño de este grafo será inmenso, por lo que no existirá de manera explícita. En cada momento sólo tenemos en una estructura los nodos que van desde el estado inicial al estado actual. Si cada secuencia de decisiones distinta da lugar a un estado diferente, el grafo es un árbol (el árbol de estados).

== Enfoque ==

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 [[Eficiencia de los algoritmos|tiempo]] de ejecución.

Vuelta atrás está muy relacionado con la [[Búsqueda combinatoria]].

== Diseño e implementación ==

Esencialmente, la idea es encontrar la mejor combinación posible en un momento determinado, por eso, se dice que este tipo de algoritmo es una [[Búsqueda en profundidad]]. Durante la búsqueda, si se encuentra una alternativa incorrecta, la búsqueda retrocede hasta el paso anterior y toma la siguiente alternativa. Cuando se han terminado las posibilidades, se vuelve a la elección anterior y se toma la siguiente opción (hijo [si nos referimos a un árbol]). Si no hay más alternativas la búsqueda falla. De esta manera, se crea un árbol implícito, en el que cada nodo es un estado de la solución (solución parcial en el caso de nodos interiores o solución total en el caso de los nodos hoja).

Normalmente, se suele implementar este tipo de algoritmos como un procedimiento [[Recursividad|recursivo]]. Así, en cada llamada al procedimiento se toma una variable y se le asignan todos los valores posibles, llamando a su vez al procedimiento para cada uno de los nuevos estados. La diferencia con la [[Búsqueda en profundidad]] es que se suelen diseñar funciones de cota, de forma que no se generen algunos estados si no van a conducir a ninguna solución, o a una solución peor de la que ya se tiene. De esta forma se ahorra espacio en memoria y tiempo de ejecución.

== Heurísticas ==

Algunas heurísticas son comúnmente usadas para acelerar el proceso. Como las variables se pueden procesar en cualquier orden, generalmente es más eficiente intentar ser lo más restrictivo posible con las primeras (esto es, las primeras con menores valores posibles). Este proceso poda el [[Árbol (estructura de datos)|árbol de búsqueda]] antes de que se tome la decisión y se llame a la subrutina recursiva.

Cuando se elige qué valor se va a asignar, muchas implementaciones hacen un examen hacia delante (FC, Forward Checking), para ver qué valor restringirá el menor número posible de valores, de forma que se anticipa en a) preservar una posible solución y b) hace que la solución encontrada no tenga restricciones destacadas.

Algunas implementaciones muy sofisticadas usan una función de cotas, que examina si es posible encontrar una solución a partir de una solución parcial. Además, se comprueba si la solución parcial que falla puede incrementar significativamente la eficiencia del algoritmo. Por el uso de estas funciones de cota, se debe ser muy minucioso en su implementación de forma que sean poco costosas computacionalmente hablando, ya que lo más normal es que se ejecuten en para cada nodo o paso del algoritmo. Cabe destacar, que las cotas eficaces se crean de forma parecida a las funciones [[Heurística]]s, esto es, relajando las restricciones para conseguir mayor eficiencia.

Con el objetivo de mantener la solución actual con coste mínimo, los algoritmos vuelta atrás mantienen el coste de la mejor solución en una variable que va variando con cada nueva mejor solución encontrada. Así, si una solución es peor que la que se acaba de encontrar, el algoritmo no actualizará la solución. De esta forma, devolverá siempre la mejor solución que haya encontrado.

== Ejemplos de aplicación de backtracking ==

SATISFABILITY

Inicialmente A contiene la expresión booleana que constituye el problema.

Elegir subproblema de A, p.ejemplo : (x+y+z)(x'+y)(y'+z)(z'+x)(x'+y'+z').

Elegir una cláusula con mínimo número de literales.

Elegir una variable x, y, z,... dentro de la cláusula y crear 2 subproblemas reemplazando x=V y x=F.

En el caso x=V

Omitir las cláusulas donde aparece x.

Omitir x' en las cláusulas que aparece x'.

En el caso x=F

Omitir las cláusulas donde aparece x'.

Omitir x en las cláusulas que aparece x.

Test

Si no quedan cláusulas. STOP. (solución encontrada).

Si hay una cláusula vacía. DROP.

En otro caso añadir a A

Nota: Observemos que si encontramos a A vacío entonces la expresión booleana no puede ser satisfecha.

 '''HAMILTON CYCLE (VIAJANTE DE COMERCIO)'''

En este caso los subproblemas S son caminos que parten de a y llegan a b a través de un sucesión de nodos T. (b es el mismo a lo largo de todo el algoritmo).

Inicialmente A contiene solamente el camino (a, vacío, b).

Elegimos un subproblema S cualquiera de A (y lo borramos de A) y añadimos ramas (c, a) del grafo (las c's son las adyacentes de a) . Estos caminos extendidos son los hijos. Ahora cada c juega el rol de a.

Examinamos c/ hijo:

Test:

1)Si G-T forma un camino hamiltoniano STOP (solución hallada)

2)Si G-T tiene un nodo de grado uno (excepto a y b) o si G-T-{a, b} es disconexo entonces DROP este subproblema .

3) Si 1) y 2) fallan add subproblema en A.

 '''EXACT COVER'''

Dado un conjunto finito U y una familia se subconjuntos {Tj} de U definimos una matriz A donde cada fila se corresponde con un elemento ui de U y cada columna de A con un subconjunto Tj . Ponemos aij=1 si uiU pertenece a Tj y aij=0 en caso contrario. Interpretamos que xj=1 significa que elegimos Tj y 0 en caso contrario.

Se trata de averiguar si es factible Ax=1 donde A y x son binarias y las componentes de 1 son unos.

S0= un vector de ceros (raíz del árbol)

Cada nodo S del árbol es una sucesión x cuyas primeras k componentes le han sido asignados un 1 o un 0 y el resto de componentes son ceros. Reemplazamos S por 2 subproblemas Si (i=1,2) poniendo xk+1 =1 y xk+1=0 respectivamente.

Test

if Ax=1 STOP

if Ax>1 DROP Si

if Ax<1 add Si to A

== Ejemplos de problemas comunes resueltos usando Vuelta Atrás ==

'''Problema de las N Reinas'''

Disponemos de un tablero de ajedrez de tamaño NxN, y se trata de colocar en él N reinas de manera que no se amenacen según las normas del ajedrez.

proc NReinas (↕[1 . . . i ]: TSolución, ↓N: N, ↑ok: B)
variables j : N
inicio
si i=N entonces ok=CIERTO
en otro caso
ok=FALSO
j=1
mientras ¬ok ^ (j≤N) hacer
si EsFactible (R, j) entonces
R[i + 1]= j
NReinas (R, N, ok)
finsi
j=j+1
finmientras
finsi
fin

func EsFactible (↓R[1 . . . i ]: TSolución, ↓j : N): B
variables factible: B
inicio
factible=CIERTO
k=1
mientras factible ^ (k≤i) hacer
si (j=R[k])\/(i+1−k= |j−R[k]|) entonces
factible=FALSO
finsi
k=k+1
finmientras
devolver factible
fin

                          

'''Problema de la mochila 0,1'''

Dados n elementos e1,e2,...,en con pesos p1,p2,...,pn y beneficios b1,b2,...,bn, y dada una mochila capaz de albergar hasta un máximo de peso M (capacidad de la mochila), queremos encontrar cuáles de los n elementos hemos de introducir en la mochila de forma que la suma de los beneficios de los elementos escogidos sea máxima, sujeto a la restricción de que tales elementos no pueden superar la capacidad de la mochila. 

 

'''Problema del laberinto'''

Se tiene una matriz bidimensional de nxn casillas para representar un laberinto cuadrado. Cada casilla está marcada como visitada o no visitada. Se debe ir desde la casilla (1,1) a la (n, n) haciendo movimientos horizontales y verticales.

*[[Problema de las parejas]]
*[[Formación de una palabra con n cubos]]
*[[Sudoku backtracking|Sudoku]]
*[[Problema del laberinto]]
*[[Problema del laberinto con límite]]
*[[Problema del dominó]]
*[[Problema de los movimientos de un caballo]]
*[[Problema del reparto del botín]]
*[[Problema de la mochila utilizando Vuelta Atrás]]
*[[Minimización de cableado en placa]]
*[[Coloreado de grafos]]
*[[Problema del viajante sobre grafos dirigidos]]
*[[Las ocho reinas]]

== Backtracking para la enumeración ==

El problema de la enumeración consiste en encontrar todas las soluciones del problema, es por ello que tendremos que recorrer el árbol de estados al completo.

Algoritmo de Backtracking para la enumeración:

proc Bactracking Enum(↕X[1 . . . i ]: TSolución, ↑num: N)
variables L: ListaComponentes
inicio
si EsSolución (X) entonces num num+1
EscribeSolución (X)
en otro caso
L Candidatos (X)
mientras ¬Vacía (L) hacer
X[i + 1] Cabeza (L); L Resto (L)
BacktrackingEnum (X, num)
finmientras
finsi
fin

== Aplicaciones ==

Vuelta atrás se usa en la implementación de los [[Lenguajes de programación]] tales como [[Planner|Lenguaje de programación Planner]] y [[Prolog]]. Además, se usa en los análisis sintácticos de los compiladores. Su uso en [[Inteligencia artificial]] ha sido muy importante, dando lugar a nuevos tipos de búsquedas como el [[A*|A estrella]].

== Branch & Bound ( Ramificación y poda ) ==

Este método busca una solución como en el método de backtracking, pero cada solución tiene asociado un costo y la solución que se busca es una de mínimo costo llamada óptima. Además de ramificar una solución padre (branch) en hijos se trata de eliminar de consideración aquellos hijos cuyos descendientes tienen un costo que supera al óptimo buscado acotando el costo de los descendientes del hijo (bound). La forma de acotar es un arte que depende de cada problema. La acotacion reduce el tiempo de búsqueda de la solución óptima al "podar" (pruning) los subarboles de descendientes costosos.

[[Category:Algoritmos]]

Vuelta atrás (backtracking)

2010-04-29T19:12:13Z

Asanto uci:

{{Referencia}}

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 los años 1950s.

== Concepto ==

En su forma básica, la idea de backtracking se asemeja a un recorrido en profundidad dentro de un grafo dirigido. El grafo en cuestión suele ser un árbol, o por lo menos no contiene ciclos. Sea cual sea su estructura, existe sólo implícitamente. El objetivo del recorrido es encontrar soluciones para algún problema. Esto se consigue construyendo soluciones parciales a medida que progresa el recorrido; estas soluciones parciales limitan las regiones en las que se puede encontrar una solución completa. El recorrido tiene éxito si, procediendo de esta forma, se puede definir por completo una solución. En este caso el algoritmo puede bien detenerse (si lo único que se necesita es una solución del problema) o bien seguir buscando soluciones alternativas (si deseamos examinarlas todas). Por otra parte, el recorrido no tiene éxito si en alguna etapa la solución parcial construida hasta el momento no se puede completar. En tal caso, el recorrido vuelve atrás exactamente igual que en un recorrido en profundidad, eliminando sobre la marcha los elementos que se hubieran añadido en cada fase. Cuando vuelve a un nodo que tiene uno o más vecinos sin explorar, prosigue el recorrido de una solución.

 

Algoritmo de Backtracking

proc Backtracking (↕X[1 . . . i ]: TSolución, ↑ok: B)
variables L: ListaComponentes
inicio
si EsSolución (X) entonces ok CIERTO
en otro caso
ok FALSO
L=Candidatos (X)
mientras ¬ok ^ ¬Vacía (L) hacer
X[i + 1] Cabeza (L); L Resto (L)
Backtracking (X, ok)
finmientras
finsi
fin

Podemos visualizar el funcionamiento de una técnica de backtracking como la exploración en profundidad de un grafo.

Cada vértice del grafo es un posible estado de la solución del problema. Cada arco del grafo representa la transición entre dos estados de la solución (i.e., la toma de una decisión).

Típicamente el tamaño de este grafo será inmenso, por lo que no existirá de manera explícita. En cada momento sólo tenemos en una estructura los nodos que van desde el estado inicial al estado actual. Si cada secuencia de decisiones distinta da lugar a un estado diferente, el grafo es un árbol (el árbol de estados).

== Enfoque ==

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 [[Eficiencia de los algoritmos|tiempo]] de ejecución.

Vuelta atrás está muy relacionado con la [[Búsqueda combinatoria]].

== Diseño e implementación ==

Esencialmente, la idea es encontrar la mejor combinación posible en un momento determinado, por eso, se dice que este tipo de algoritmo es una [[Búsqueda en profundidad]]. Durante la búsqueda, si se encuentra una alternativa incorrecta, la búsqueda retrocede hasta el paso anterior y toma la siguiente alternativa. Cuando se han terminado las posibilidades, se vuelve a la elección anterior y se toma la siguiente opción (hijo [si nos referimos a un árbol]). Si no hay más alternativas la búsqueda falla. De esta manera, se crea un árbol implícito, en el que cada nodo es un estado de la solución (solución parcial en el caso de nodos interiores o solución total en el caso de los nodos hoja).

Normalmente, se suele implementar este tipo de algoritmos como un procedimiento [[Recursividad|recursivo]]. Así, en cada llamada al procedimiento se toma una variable y se le asignan todos los valores posibles, llamando a su vez al procedimiento para cada uno de los nuevos estados. La diferencia con la [[Búsqueda en profundidad]] es que se suelen diseñar funciones de cota, de forma que no se generen algunos estados si no van a conducir a ninguna solución, o a una solución peor de la que ya se tiene. De esta forma se ahorra espacio en memoria y tiempo de ejecución.

== Heurísticas ==

Algunas heurísticas son comúnmente usadas para acelerar el proceso. Como las variables se pueden procesar en cualquier orden, generalmente es más eficiente intentar ser lo más restrictivo posible con las primeras (esto es, las primeras con menores valores posibles). Este proceso poda el [[Árbol (estructura de datos)|árbol de búsqueda]] antes de que se tome la decisión y se llame a la subrutina recursiva.

Cuando se elige qué valor se va a asignar, muchas implementaciones hacen un examen hacia delante (FC, Forward Checking), para ver qué valor restringirá el menor número posible de valores, de forma que se anticipa en a) preservar una posible solución y b) hace que la solución encontrada no tenga restricciones destacadas.

Algunas implementaciones muy sofisticadas usan una función de cotas, que examina si es posible encontrar una solución a partir de una solución parcial. Además, se comprueba si la solución parcial que falla puede incrementar significativamente la eficiencia del algoritmo. Por el uso de estas funciones de cota, se debe ser muy minucioso en su implementación de forma que sean poco costosas computacionalmente hablando, ya que lo más normal es que se ejecuten en para cada nodo o paso del algoritmo. Cabe destacar, que las cotas eficaces se crean de forma parecida a las funciones [[Heurística]]s, esto es, relajando las restricciones para conseguir mayor eficiencia.

Con el objetivo de mantener la solución actual con coste mínimo, los algoritmos vuelta atrás mantienen el coste de la mejor solución en una variable que va variando con cada nueva mejor solución encontrada. Así, si una solución es peor que la que se acaba de encontrar, el algoritmo no actualizará la solución. De esta forma, devolverá siempre la mejor solución que haya encontrado.

== Ejemplos de aplicación de backtracking ==

SATISFABILITY

----

Inicialmente A contiene la expresión booleana que constituye el problema.

Elegir subproblema de A, p.ejemplo : (x+y+z)(x'+y)(y'+z)(z'+x)(x'+y'+z').

Elegir una cláusula con mínimo número de literales.

Elegir una variable x, y, z,... dentro de la cláusula y crear 2 subproblemas reemplazando x=V y x=F.

En el caso x=V

Omitir las cláusulas donde aparece x.

Omitir x' en las cláusulas que aparece x'.

En el caso x=F

Omitir las cláusulas donde aparece x'.

Omitir x en las cláusulas que aparece x.

Test

Si no quedan cláusulas. STOP. (solución encontrada).

Si hay una cláusula vacía. DROP.

En otro caso añadir a A

Nota: Observemos que si encontramos a A vacío entonces la expresión booleana no puede ser satisfecha.

 '''HAMILTON CYCLE (VIAJANTE DE COMERCIO)'''

----

En este caso los subproblemas S son caminos que parten de a y llegan a b a través de un sucesión de nodos T. (b es el mismo a lo largo de todo el algoritmo).

Inicialmente A contiene solamente el camino (a, vacío, b).

Elegimos un subproblema S cualquiera de A (y lo borramos de A) y añadimos ramas (c, a) del grafo (las c's son las adyacentes de a) . Estos caminos extendidos son los hijos. Ahora cada c juega el rol de a.

Examinamos c/ hijo:

Test:

1)Si G-T forma un camino hamiltoniano STOP (solución hallada)

2)Si G-T tiene un nodo de grado uno (excepto a y b) o si G-T-{a, b} es disconexo entonces DROP este subproblema .

3) Si 1) y 2) fallan add subproblema en A.

 '''EXACT COVER'''

----

Dado un conjunto finito U y una familia se subconjuntos {Tj} de U definimos una matriz A donde cada fila se corresponde con un elemento ui de U y cada columna de A con un subconjunto Tj . Ponemos aij=1 si uiU pertenece a Tj y aij=0 en caso contrario. Interpretamos que xj=1 significa que elegimos Tj y 0 en caso contrario.

Se trata de averiguar si es factible Ax=1 donde A y x son binarias y las componentes de 1 son unos.

S0= un vector de ceros (raíz del árbol)

Cada nodo S del árbol es una sucesión x cuyas primeras k componentes le han sido asignados un 1 o un 0 y el resto de componentes son ceros. Reemplazamos S por 2 subproblemas Si (i=1,2) poniendo xk+1 =1 y xk+1=0 respectivamente.

Test

if Ax=1 STOP

if Ax>1 DROP Si

if Ax<1 add Si to A

== Ejemplos de problemas comunes resueltos usando Vuelta Atrás ==

'''Problema de las N Reinas'''

----

Disponemos de un tablero de ajedrez de tamaño NxN, y se trata de colocar en él N reinas de manera que no se amenacen según las normas del ajedrez.

proc NReinas (↕[1 . . . i ]: TSolución, ↓N: N, ↑ok: B)
variables j : N
inicio
si i=N entonces ok=CIERTO
en otro caso
ok=FALSO
j=1
mientras ¬ok ^ (j≤N) hacer
si EsFactible (R, j) entonces
R[i + 1]= j
NReinas (R, N, ok)
finsi
j=j+1
finmientras
finsi
fin

func EsFactible (↓R[1 . . . i ]: TSolución, ↓j : N): B
variables factible: B
inicio
factible=CIERTO
k=1
mientras factible ^ (k≤i) hacer
si (j=R[k])\/(i+1−k= |j−R[k]|) entonces
factible=FALSO
finsi
k=k+1
finmientras
devolver factible
fin

                          

'''Problema de la mochila 0,1'''

----

Dados n elementos e1,e2,...,en con pesos p1,p2,...,pn y beneficios b1,b2,...,bn, y dada una mochila capaz de albergar hasta un máximo de peso M (capacidad de la mochila), queremos encontrar cuáles de los n elementos hemos de introducir en la mochila de forma que la suma de los beneficios de los elementos escogidos sea máxima, sujeto a la restricción de que tales elementos no pueden superar la capacidad de la mochila. 

 

'''Problema del laberinto'''

----

Se tiene una matriz bidimensional de nxn casillas para representar un laberinto cuadrado. Cada casilla está marcada como visitada o no visitada. Se debe ir desde la casilla (1,1) a la (n, n) haciendo movimientos horizontales y verticales.

*[[Problema de las parejas]]
*[[Formación de una palabra con n cubos]]
*[[Sudoku backtracking|Sudoku]]
*[[Problema del laberinto]]
*[[Problema del laberinto con límite]]
*[[Problema del dominó]]
*[[Problema de los movimientos de un caballo]]
*[[Problema del reparto del botín]]
*[[Problema de la mochila utilizando Vuelta Atrás]]
*[[Minimización de cableado en placa]]
*[[Coloreado de grafos]]
*[[Problema del viajante sobre grafos dirigidos]]
*[[Las ocho reinas]]

== Backtracking para la enumeración ==

----

El problema de la enumeración consiste en encontrar todas las soluciones del problema, es por ello que tendremos que recorrer el árbol de estados al completo.

Algoritmo de Backtracking para la enumeración:

proc Bactracking Enum(↕X[1 . . . i ]: TSolución, ↑num: N)
variables L: ListaComponentes
inicio
si EsSolución (X) entonces num num+1
EscribeSolución (X)
en otro caso
L Candidatos (X)
mientras ¬Vacía (L) hacer
X[i + 1] Cabeza (L); L Resto (L)
BacktrackingEnum (X, num)
finmientras
finsi
fin

== Aplicaciones ==

Vuelta atrás se usa en la implementación de los [[Lenguajes de programación]] tales como [[Planner|Lenguaje de programación Planner]] y [[Prolog]]. Además, se usa en los análisis sintácticos de los compiladores. Su uso en [[Inteligencia artificial]] ha sido muy importante, dando lugar a nuevos tipos de búsquedas como el [[A*|A estrella]].

== Branch & Bound ( Ramificación y poda ) ==

----

Este método busca una solución como en el método de backtracking, pero cada solución tiene asociado un costo y la solución que se busca es una de mínimo costo llamada óptima. Además de ramificar una solución padre (branch) en hijos se trata de eliminar de consideración aquellos hijos cuyos descendientes tienen un costo que supera al óptimo buscado acotando el costo de los descendientes del hijo (bound). La forma de acotar es un arte que depende de cada problema. La acotacion reduce el tiempo de búsqueda de la solución óptima al "podar" (pruning) los subarboles de descendientes costosos.

[[Category:Algoritmos]]

Vuelta atrás (backtracking)

2010-04-29T19:11:06Z

Asanto uci:

{{Referencia}}

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 los años 1950s.

== Concepto ==

En su forma básica, la idea de backtracking se asemeja a un recorrido en profundidad dentro de un grafo dirigido. El grafo en cuestión suele ser un árbol, o por lo menos no contiene ciclos. Sea cual sea su estructura, existe sólo implícitamente. El objetivo del recorrido es encontrar soluciones para algún problema. Esto se consigue construyendo soluciones parciales a medida que progresa el recorrido; estas soluciones parciales limitan las regiones en las que se puede encontrar una solución completa. El recorrido tiene éxito si, procediendo de esta forma, se puede definir por completo una solución. En este caso el algoritmo puede bien detenerse (si lo único que se necesita es una solución del problema) o bien seguir buscando soluciones alternativas (si deseamos examinarlas todas). Por otra parte, el recorrido no tiene éxito si en alguna etapa la solución parcial construida hasta el momento no se puede completar. En tal caso, el recorrido vuelve atrás exactamente igual que en un recorrido en profundidad, eliminando sobre la marcha los elementos que se hubieran añadido en cada fase. Cuando vuelve a un nodo que tiene uno o más vecinos sin explorar, prosigue el recorrido de una solución.

 

Algoritmo de Backtracking

proc Backtracking (↕X[1 . . . i ]: TSolución, ↑ok: B)
variables L: ListaComponentes
inicio
si EsSolución (X) entonces ok CIERTO
en otro caso
ok FALSO
L=Candidatos (X)
mientras ¬ok ^ ¬Vacía (L) hacer
X[i + 1] Cabeza (L); L Resto (L)
Backtracking (X, ok)
finmientras
finsi
fin

Podemos visualizar el funcionamiento de una técnica de backtracking como la exploración en profundidad de un grafo.

Cada vértice del grafo es un posible estado de la solución del problema. Cada arco del grafo representa la transición entre dos estados de la solución (i.e., la toma de una decisión).

Típicamente el tamaño de este grafo será inmenso, por lo que no existirá de manera explícita. En cada momento sólo tenemos en una estructura los nodos que van desde el estado inicial al estado actual. Si cada secuencia de decisiones distinta da lugar a un estado diferente, el grafo es un árbol (el árbol de estados).

== Enfoque ==

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 [[Eficiencia de los algoritmos|tiempo]] de ejecución.

Vuelta atrás está muy relacionado con la [[Búsqueda combinatoria]].

== Diseño e implementación ==

Esencialmente, la idea es encontrar la mejor combinación posible en un momento determinado, por eso, se dice que este tipo de algoritmo es una [[Búsqueda en profundidad]]. Durante la búsqueda, si se encuentra una alternativa incorrecta, la búsqueda retrocede hasta el paso anterior y toma la siguiente alternativa. Cuando se han terminado las posibilidades, se vuelve a la elección anterior y se toma la siguiente opción (hijo [si nos referimos a un árbol]). Si no hay más alternativas la búsqueda falla. De esta manera, se crea un árbol implícito, en el que cada nodo es un estado de la solución (solución parcial en el caso de nodos interiores o solución total en el caso de los nodos hoja).

Normalmente, se suele implementar este tipo de algoritmos como un procedimiento [[Recursividad|recursivo]]. Así, en cada llamada al procedimiento se toma una variable y se le asignan todos los valores posibles, llamando a su vez al procedimiento para cada uno de los nuevos estados. La diferencia con la [[Búsqueda en profundidad]] es que se suelen diseñar funciones de cota, de forma que no se generen algunos estados si no van a conducir a ninguna solución, o a una solución peor de la que ya se tiene. De esta forma se ahorra espacio en memoria y tiempo de ejecución.

== Heurísticas ==

Algunas heurísticas son comúnmente usadas para acelerar el proceso. Como las variables se pueden procesar en cualquier orden, generalmente es más eficiente intentar ser lo más restrictivo posible con las primeras (esto es, las primeras con menores valores posibles). Este proceso poda el [[Árbol (estructura de datos)|árbol de búsqueda]] antes de que se tome la decisión y se llame a la subrutina recursiva.

Cuando se elige qué valor se va a asignar, muchas implementaciones hacen un examen hacia delante (FC, Forward Checking), para ver qué valor restringirá el menor número posible de valores, de forma que se anticipa en a) preservar una posible solución y b) hace que la solución encontrada no tenga restricciones destacadas.

Algunas implementaciones muy sofisticadas usan una función de cotas, que examina si es posible encontrar una solución a partir de una solución parcial. Además, se comprueba si la solución parcial que falla puede incrementar significativamente la eficiencia del algoritmo. Por el uso de estas funciones de cota, se debe ser muy minucioso en su implementación de forma que sean poco costosas computacionalmente hablando, ya que lo más normal es que se ejecuten en para cada nodo o paso del algoritmo. Cabe destacar, que las cotas eficaces se crean de forma parecida a las funciones [[Heurística]]s, esto es, relajando las restricciones para conseguir mayor eficiencia.

Con el objetivo de mantener la solución actual con coste mínimo, los algoritmos vuelta atrás mantienen el coste de la mejor solución en una variable que va variando con cada nueva mejor solución encontrada. Así, si una solución es peor que la que se acaba de encontrar, el algoritmo no actualizará la solución. De esta forma, devolverá siempre la mejor solución que haya encontrado.

== Ejemplos de aplicación de backtracking ==

SATISFABILITY

----

Inicialmente A contiene la expresión booleana que constituye el problema.

Elegir subproblema de A, p.ejemplo : (x+y+z)(x'+y)(y'+z)(z'+x)(x'+y'+z').

Elegir una cláusula con mínimo número de literales.

Elegir una variable x, y, z,... dentro de la cláusula y crear 2 subproblemas reemplazando x=V y x=F.

En el caso x=V

Omitir las cláusulas donde aparece x.

Omitir x' en las cláusulas que aparece x'.

En el caso x=F

Omitir las cláusulas donde aparece x'.

Omitir x en las cláusulas que aparece x.

Test

Si no quedan cláusulas. STOP. (solución encontrada).

Si hay una cláusula vacía. DROP.

En otro caso añadir a A

Nota: Observemos que si encontramos a A vacío entonces la expresión booleana no puede ser satisfecha.

 '''HAMILTON CYCLE (VIAJANTE DE COMERCIO)'''

----

En este caso los subproblemas S son caminos que parten de a y llegan a b a través de un sucesión de nodos T. (b es el mismo a lo largo de todo el algoritmo).

Inicialmente A contiene solamente el camino (a, vacío, b).

Elegimos un subproblema S cualquiera de A (y lo borramos de A) y añadimos ramas (c, a) del grafo (las c's son las adyacentes de a) . Estos caminos extendidos son los hijos. Ahora cada c juega el rol de a.

Examinamos c/ hijo:

Test:

1)Si G-T forma un camino hamiltoniano STOP (solución hallada)

2)Si G-T tiene un nodo de grado uno (excepto a y b) o si G-T-{a, b} es disconexo entonces DROP este subproblema .

3) Si 1) y 2) fallan add subproblema en A.

 '''EXACT COVER'''

----

Dado un conjunto finito U y una familia se subconjuntos {Tj} de U definimos una matriz A donde cada fila se corresponde con un elemento ui de U y cada columna de A con un subconjunto Tj . Ponemos aij=1 si uiU pertenece a Tj y aij=0 en caso contrario. Interpretamos que xj=1 significa que elegimos Tj y 0 en caso contrario.

Se trata de averiguar si es factible Ax=1 donde A y x son binarias y las componentes de 1 son unos.

S0= un vector de ceros (raíz del árbol)

Cada nodo S del árbol es una sucesión x cuyas primeras k componentes le han sido asignados un 1 o un 0 y el resto de componentes son ceros. Reemplazamos S por 2 subproblemas Si (i=1,2) poniendo xk+1 =1 y xk+1=0 respectivamente.

Test

if Ax=1 STOP

if Ax>1 DROP Si

if Ax<1 add Si to A

== Ejemplos de problemas comunes resueltos usando Vuelta Atrás ==

'''Problema de las N Reinas'''

----

Disponemos de un tablero de ajedrez de tamaño NxN, y se trata de colocar en él N reinas de manera que no se amenacen según las normas del ajedrez.

proc NReinas (↕[1 . . . i ]: TSolución, ↓N: N, ↑ok: B)
variables j : N
inicio
si i=N entonces ok=CIERTO
en otro caso
ok=FALSO
j=1
mientras ¬ok ^ (j≤N) hacer
si EsFactible (R, j) entonces
R[i + 1]= j
NReinas (R, N, ok)
finsi
j=j+1
finmientras
finsi
fin

func EsFactible (↓R[1 . . . i ]: TSolución, ↓j : N): B
variables factible: B
inicio
factible=CIERTO
k=1
mientras factible ^ (k≤i) hacer
si (j=R[k])\/(i+1−k= |j−R[k]|) entonces
factible=FALSO
finsi
k=k+1
finmientras
devolver factible
fin

                          

'''Problema de la mochila 0,1'''

----

Dados n elementos e1,e2,...,en con pesos p1,p2,...,pn y beneficios b1,b2,...,bn, y dada una mochila capaz de albergar hasta un máximo de peso M (capacidad de la mochila), queremos encontrar cuáles de los n elementos hemos de introducir en la mochila de forma que la suma de los beneficios de los elementos escogidos sea máxima, sujeto a la restricción de que tales elementos no pueden superar la capacidad de la mochila. 

 

'''Problema del laberinto'''

----

Se tiene una matriz bidimensional de nxn casillas para representar un laberinto cuadrado. Cada casilla está marcada como visitada o no visitada. Se debe ir desde la casilla (1,1) a la (n, n) haciendo movimientos horizontales y verticales.

[[Image:Alg5.jpg]]

*[[Problema de las parejas]]
*[[Formación de una palabra con n cubos]]
*[[Sudoku backtracking|Sudoku]]
*[[Problema del laberinto]]
*[[Problema del laberinto con límite]]
*[[Problema del dominó]]
*[[Problema de los movimientos de un caballo]]
*[[Problema del reparto del botín]]
*[[Problema de la mochila utilizando Vuelta Atrás]]
*[[Minimización de cableado en placa]]
*[[Coloreado de grafos]]
*[[Problema del viajante sobre grafos dirigidos]]
*[[Las ocho reinas]]

== Backtracking para la enumeración ==

----

El problema de la enumeración consiste en encontrar todas las soluciones del problema, es por ello que tendremos que recorrer el árbol de estados al completo.

Algoritmo de Backtracking para la enumeración:

proc Bactracking Enum(↕X[1 . . . i ]: TSolución, ↑num: N)
variables L: ListaComponentes
inicio
si EsSolución (X) entonces num num+1
EscribeSolución (X)
en otro caso
L Candidatos (X)
mientras ¬Vacía (L) hacer
X[i + 1] Cabeza (L); L Resto (L)
BacktrackingEnum (X, num)
finmientras
finsi
fin

== Aplicaciones ==

Vuelta atrás se usa en la implementación de los [[Lenguajes de programación]] tales como [[Planner|Lenguaje de programación Planner]] y [[Prolog]]. Además, se usa en los análisis sintácticos de los compiladores. Su uso en [[Inteligencia artificial]] ha sido muy importante, dando lugar a nuevos tipos de búsquedas como el [[A*|A estrella]].

== Branch & Bound ( Ramificación y poda ) ==

----

Este método busca una solución como en el método de backtracking, pero cada solución tiene asociado un costo y la solución que se busca es una de mínimo costo llamada óptima. Además de ramificar una solución padre (branch) en hijos se trata de eliminar de consideración aquellos hijos cuyos descendientes tienen un costo que supera al óptimo buscado acotando el costo de los descendientes del hijo (bound). La forma de acotar es un arte que depende de cada problema. La acotacion reduce el tiempo de búsqueda de la solución óptima al "podar" (pruning) los subarboles de descendientes costosos.

[[Category:Algoritmos]]

Vuelta atrás (backtracking)

2010-04-29T19:09:50Z

Asanto uci:

{{Referencia}}

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 los años 1950s.

== Concepto ==

En su forma básica, la idea de backtracking se asemeja a un recorrido en profundidad dentro de un grafo dirigido. El grafo en cuestión suele ser un árbol, o por lo menos no contiene ciclos. Sea cual sea su estructura, existe sólo implícitamente. El objetivo del recorrido es encontrar soluciones para algún problema. Esto se consigue construyendo soluciones parciales a medida que progresa el recorrido; estas soluciones parciales limitan las regiones en las que se puede encontrar una solución completa. El recorrido tiene éxito si, procediendo de esta forma, se puede definir por completo una solución. En este caso el algoritmo puede bien detenerse (si lo único que se necesita es una solución del problema) o bien seguir buscando soluciones alternativas (si deseamos examinarlas todas). Por otra parte, el recorrido no tiene éxito si en alguna etapa la solución parcial construida hasta el momento no se puede completar. En tal caso, el recorrido vuelve atrás exactamente igual que en un recorrido en profundidad, eliminando sobre la marcha los elementos que se hubieran añadido en cada fase. Cuando vuelve a un nodo que tiene uno o más vecinos sin explorar, prosigue el recorrido de una solución.

 

Algoritmo de Backtracking

proc Backtracking (↕X[1 . . . i ]: TSolución, ↑ok: B)
variables L: ListaComponentes
inicio
si EsSolución (X) entonces ok CIERTO
en otro caso
ok FALSO
L=Candidatos (X)
mientras ¬ok ^ ¬Vacía (L) hacer
X[i + 1] Cabeza (L); L Resto (L)
Backtracking (X, ok)
finmientras
finsi
fin

Podemos visualizar el funcionamiento de una técnica de backtracking como la exploración en profundidad de un grafo.

Cada vértice del grafo es un posible estado de la solución del problema. Cada arco del grafo representa la transición entre dos estados de la solución (i.e., la toma de una decisión).

Típicamente el tamaño de este grafo será inmenso, por lo que no existirá de manera explícita. En cada momento sólo tenemos en una estructura los nodos que van desde el estado inicial al estado actual. Si cada secuencia de decisiones distinta da lugar a un estado diferente, el grafo es un árbol (el árbol de estados).

== Enfoque ==

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 [[Eficiencia de los algoritmos|tiempo]] de ejecución.

Vuelta atrás está muy relacionado con la [[Búsqueda combinatoria]].

== Diseño e implementación ==

Esencialmente, la idea es encontrar la mejor combinación posible en un momento determinado, por eso, se dice que este tipo de algoritmo es una [[Búsqueda en profundidad]]. Durante la búsqueda, si se encuentra una alternativa incorrecta, la búsqueda retrocede hasta el paso anterior y toma la siguiente alternativa. Cuando se han terminado las posibilidades, se vuelve a la elección anterior y se toma la siguiente opción (hijo [si nos referimos a un árbol]). Si no hay más alternativas la búsqueda falla. De esta manera, se crea un árbol implícito, en el que cada nodo es un estado de la solución (solución parcial en el caso de nodos interiores o solución total en el caso de los nodos hoja).

Normalmente, se suele implementar este tipo de algoritmos como un procedimiento [[Recursividad|recursivo]]. Así, en cada llamada al procedimiento se toma una variable y se le asignan todos los valores posibles, llamando a su vez al procedimiento para cada uno de los nuevos estados. La diferencia con la [[Búsqueda en profundidad]] es que se suelen diseñar funciones de cota, de forma que no se generen algunos estados si no van a conducir a ninguna solución, o a una solución peor de la que ya se tiene. De esta forma se ahorra espacio en memoria y tiempo de ejecución.

== Heurísticas ==

Algunas heurísticas son comúnmente usadas para acelerar el proceso. Como las variables se pueden procesar en cualquier orden, generalmente es más eficiente intentar ser lo más restrictivo posible con las primeras (esto es, las primeras con menores valores posibles). Este proceso poda el [[Árbol (estructura de datos)|árbol de búsqueda]] antes de que se tome la decisión y se llame a la subrutina recursiva.

Cuando se elige qué valor se va a asignar, muchas implementaciones hacen un examen hacia delante (FC, Forward Checking), para ver qué valor restringirá el menor número posible de valores, de forma que se anticipa en a) preservar una posible solución y b) hace que la solución encontrada no tenga restricciones destacadas.

Algunas implementaciones muy sofisticadas usan una función de cotas, que examina si es posible encontrar una solución a partir de una solución parcial. Además, se comprueba si la solución parcial que falla puede incrementar significativamente la eficiencia del algoritmo. Por el uso de estas funciones de cota, se debe ser muy minucioso en su implementación de forma que sean poco costosas computacionalmente hablando, ya que lo más normal es que se ejecuten en para cada nodo o paso del algoritmo. Cabe destacar, que las cotas eficaces se crean de forma parecida a las funciones [[Heurística]]s, esto es, relajando las restricciones para conseguir mayor eficiencia.

Con el objetivo de mantener la solución actual con coste mínimo, los algoritmos vuelta atrás mantienen el coste de la mejor solución en una variable que va variando con cada nueva mejor solución encontrada. Así, si una solución es peor que la que se acaba de encontrar, el algoritmo no actualizará la solución. De esta forma, devolverá siempre la mejor solución que haya encontrado.

== Ejemplos de aplicación de backtracking ==

SATISFABILITY

----

Inicialmente A contiene la expresión booleana que constituye el problema.

Elegir subproblema de A, p.ejemplo : (x+y+z)(x'+y)(y'+z)(z'+x)(x'+y'+z').

Elegir una cláusula con mínimo número de literales.

Elegir una variable x, y, z,... dentro de la cláusula y crear 2 subproblemas reemplazando x=V y x=F.

En el caso x=V

Omitir las cláusulas donde aparece x.

Omitir x' en las cláusulas que aparece x'.

En el caso x=F

Omitir las cláusulas donde aparece x'.

Omitir x en las cláusulas que aparece x.

Test

Si no quedan cláusulas. STOP. (solución encontrada).

Si hay una cláusula vacía. DROP.

En otro caso añadir a A

Nota: Observemos que si encontramos a A vacío entonces la expresión booleana no puede ser satisfecha.

 '''HAMILTON CYCLE (VIAJANTE DE COMERCIO)'''

----

En este caso los subproblemas S son caminos que parten de a y llegan a b a través de un sucesión de nodos T. (b es el mismo a lo largo de todo el algoritmo).

Inicialmente A contiene solamente el camino (a, vacío, b).

Elegimos un subproblema S cualquiera de A (y lo borramos de A) y añadimos ramas (c, a) del grafo (las c's son las adyacentes de a) . Estos caminos extendidos son los hijos. Ahora cada c juega el rol de a.

Examinamos c/ hijo:

Test:

1)Si G-T forma un camino hamiltoniano STOP (solución hallada)

2)Si G-T tiene un nodo de grado uno (excepto a y b) o si G-T-{a, b} es disconexo entonces DROP este subproblema .

3) Si 1) y 2) fallan add subproblema en A.

 '''EXACT COVER'''

----

Dado un conjunto finito U y una familia se subconjuntos {Tj} de U definimos una matriz A donde cada fila se corresponde con un elemento ui de U y cada columna de A con un subconjunto Tj . Ponemos aij=1 si uiU pertenece a Tj y aij=0 en caso contrario. Interpretamos que xj=1 significa que elegimos Tj y 0 en caso contrario.

Se trata de averiguar si es factible Ax=1 donde A y x son binarias y las componentes de 1 son unos.

S0= un vector de ceros (raíz del árbol)

Cada nodo S del árbol es una sucesión x cuyas primeras k componentes le han sido asignados un 1 o un 0 y el resto de componentes son ceros. Reemplazamos S por 2 subproblemas Si (i=1,2) poniendo xk+1 =1 y xk+1=0 respectivamente.

Test

if Ax=1 STOP

if Ax>1 DROP Si

if Ax<1 add Si to A

== Ejemplos de problemas comunes resueltos usando Vuelta Atrás ==

'''Problema de las N Reinas'''

----

Disponemos de un tablero de ajedrez de tamaño NxN, y se trata de colocar en él N reinas de manera que no se amenacen según las normas del ajedrez.

proc NReinas (↕[1 . . . i ]: TSolución, ↓N: N, ↑ok: B)
variables j : N
inicio
si i=N entonces ok=CIERTO
en otro caso
ok=FALSO
j=1
mientras ¬ok ^ (j≤N) hacer
si EsFactible (R, j) entonces
R[i + 1]= j
NReinas (R, N, ok)
finsi
j=j+1
finmientras
finsi
fin

func EsFactible (↓R[1 . . . i ]: TSolución, ↓j : N): B
variables factible: B
inicio
factible=CIERTO
k=1
mientras factible ^ (k≤i) hacer
si (j=R[k])\/(i+1−k= |j−R[k]|) entonces
factible=FALSO
finsi
k=k+1
finmientras
devolver factible
fin

                          

'''Problema de la mochila 0,1'''

----

Dados n elementos e1,e2,...,en con pesos p1,p2,...,pn y beneficios b1,b2,...,bn, y dada una mochila capaz de albergar hasta un máximo de peso M (capacidad de la mochila), queremos encontrar cuáles de los n elementos hemos de introducir en la mochila de forma que la suma de los beneficios de los elementos escogidos sea máxima, sujeto a la restricción de que tales elementos no pueden superar la capacidad de la mochila. 

'''Problema del laberinto'''

----

Se tiene una matriz bidimensional de nxn casillas para representar un laberinto cuadrado. Cada casilla está marcada como visitada o no visitada. Se debe ir desde la casilla (1,1) a la (n, n) haciendo movimientos horizontales y verticales.

        [[Image:Alg5.jpg]]

*[[Problema de las parejas]]
*[[Formación de una palabra con n cubos]]
*[[Sudoku backtracking|Sudoku]]
*[[Problema del laberinto]]
*[[Problema del laberinto con límite]]
*[[Problema del dominó]]
*[[Problema de los movimientos de un caballo]]
*[[Problema del reparto del botín]]
*[[Problema de la mochila utilizando Vuelta Atrás]]
*[[Minimización de cableado en placa]]
*[[Coloreado de grafos]]
*[[Problema del viajante sobre grafos dirigidos]]
*[[Las ocho reinas]]

== Backtracking para la enumeración ==

----

El problema de la enumeración consiste en encontrar todas las soluciones del problema, es por ello que tendremos que recorrer el árbol de estados al completo.

Algoritmo de Backtracking para la enumeración:

proc Bactracking Enum(↕X[1 . . . i ]: TSolución, ↑num: N)
variables L: ListaComponentes
inicio
si EsSolución (X) entonces num num+1
EscribeSolución (X)
en otro caso
L Candidatos (X)
mientras ¬Vacía (L) hacer
X[i + 1] Cabeza (L); L Resto (L)
BacktrackingEnum (X, num)
finmientras
finsi
fin

== Aplicaciones ==

Vuelta atrás se usa en la implementación de los [[Lenguajes de programación]] tales como [[Planner|Lenguaje de programación Planner]] y [[Prolog]]. Además, se usa en los análisis sintácticos de los compiladores. Su uso en [[Inteligencia artificial]] ha sido muy importante, dando lugar a nuevos tipos de búsquedas como el [[A*|A estrella]].

== Branch & Bound ( Ramificación y poda ) ==

----

Este método busca una solución como en el método de backtracking, pero cada solución tiene asociado un costo y la solución que se busca es una de mínimo costo llamada óptima. Además de ramificar una solución padre (branch) en hijos se trata de eliminar de consideración aquellos hijos cuyos descendientes tienen un costo que supera al óptimo buscado acotando el costo de los descendientes del hijo (bound). La forma de acotar es un arte que depende de cada problema. La acotacion reduce el tiempo de búsqueda de la solución óptima al "podar" (pruning) los subarboles de descendientes costosos.

[[Category:Algoritmos]]

Vuelta atrás (backtracking)

2010-04-29T19:08:10Z

Asanto uci: Página creada con '{{Referencia}} Vuelta Atrás "Vuelta atrás", (Backtracking) es una estrategia para encontrar soluciones a problemas que satisfacen restricciones. El término "backtrack" fu…'

{{Referencia}}

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 los años 1950s.

== Concepto ==

En su forma básica, la idea de backtracking se asemeja a un recorrido en profundidad dentro de un grafo dirigido. El grafo en cuestión suele ser un árbol, o por lo menos no contiene ciclos. Sea cual sea su estructura, existe sólo implícitamente. El objetivo del recorrido es encontrar soluciones para algún problema. Esto se consigue construyendo soluciones parciales a medida que progresa el recorrido; estas soluciones parciales limitan las regiones en las que se puede encontrar una solución completa. El recorrido tiene éxito si, procediendo de esta forma, se puede definir por completo una solución. En este caso el algoritmo puede bien detenerse (si lo único que se necesita es una solución del problema) o bien seguir buscando soluciones alternativas (si deseamos examinarlas todas). Por otra parte, el recorrido no tiene éxito si en alguna etapa la solución parcial construida hasta el momento no se puede completar. En tal caso, el recorrido vuelve atrás exactamente igual que en un recorrido en profundidad, eliminando sobre la marcha los elementos que se hubieran añadido en cada fase. Cuando vuelve a un nodo que tiene uno o más vecinos sin explorar, prosigue el recorrido de una solución.

 

Algoritmo de Backtracking

proc Backtracking (↕X[1 . . . i ]: TSolución, ↑ok: B)
variables L: ListaComponentes
inicio
si EsSolución (X) entonces ok CIERTO
en otro caso
ok FALSO
L=Candidatos (X)
mientras ¬ok ^ ¬Vacía (L) hacer
X[i + 1] Cabeza (L); L Resto (L)
Backtracking (X, ok)
finmientras
finsi
fin

Podemos visualizar el funcionamiento de una técnica de backtracking como la exploración en profundidad de un grafo.

Cada vértice del grafo es un posible estado de la solución del problema. Cada arco del grafo representa la transición entre dos estados de la solución (i.e., la toma de una decisión).

Típicamente el tamaño de este grafo será inmenso, por lo que no existirá de manera explícita. En cada momento sólo tenemos en una estructura los nodos que van desde el estado inicial al estado actual. Si cada secuencia de decisiones distinta da lugar a un estado diferente, el grafo es un árbol (el árbol de estados).

== Enfoque ==

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 [[Eficiencia de los algoritmos|tiempo]] de ejecución.

Vuelta atrás está muy relacionado con la [[Búsqueda combinatoria]].

== Diseño e implementación ==

Esencialmente, la idea es encontrar la mejor combinación posible en un momento determinado, por eso, se dice que este tipo de algoritmo es una [[Búsqueda en profundidad]]. Durante la búsqueda, si se encuentra una alternativa incorrecta, la búsqueda retrocede hasta el paso anterior y toma la siguiente alternativa. Cuando se han terminado las posibilidades, se vuelve a la elección anterior y se toma la siguiente opción (hijo [si nos referimos a un árbol]). Si no hay más alternativas la búsqueda falla. De esta manera, se crea un árbol implícito, en el que cada nodo es un estado de la solución (solución parcial en el caso de nodos interiores o solución total en el caso de los nodos hoja).

Normalmente, se suele implementar este tipo de algoritmos como un procedimiento [[Recursividad|recursivo]]. Así, en cada llamada al procedimiento se toma una variable y se le asignan todos los valores posibles, llamando a su vez al procedimiento para cada uno de los nuevos estados. La diferencia con la [[Búsqueda en profundidad]] es que se suelen diseñar funciones de cota, de forma que no se generen algunos estados si no van a conducir a ninguna solución, o a una solución peor de la que ya se tiene. De esta forma se ahorra espacio en memoria y tiempo de ejecución.

== Heurísticas ==

Algunas heurísticas son comúnmente usadas para acelerar el proceso. Como las variables se pueden procesar en cualquier orden, generalmente es más eficiente intentar ser lo más restrictivo posible con las primeras (esto es, las primeras con menores valores posibles). Este proceso poda el [[Árbol (estructura de datos)|árbol de búsqueda]] antes de que se tome la decisión y se llame a la subrutina recursiva.

Cuando se elige qué valor se va a asignar, muchas implementaciones hacen un examen hacia delante (FC, Forward Checking), para ver qué valor restringirá el menor número posible de valores, de forma que se anticipa en a) preservar una posible solución y b) hace que la solución encontrada no tenga restricciones destacadas.

Algunas implementaciones muy sofisticadas usan una función de cotas, que examina si es posible encontrar una solución a partir de una solución parcial. Además, se comprueba si la solución parcial que falla puede incrementar significativamente la eficiencia del algoritmo. Por el uso de estas funciones de cota, se debe ser muy minucioso en su implementación de forma que sean poco costosas computacionalmente hablando, ya que lo más normal es que se ejecuten en para cada nodo o paso del algoritmo. Cabe destacar, que las cotas eficaces se crean de forma parecida a las funciones [[Heurística]]s, esto es, relajando las restricciones para conseguir mayor eficiencia.

Con el objetivo de mantener la solución actual con coste mínimo, los algoritmos vuelta atrás mantienen el coste de la mejor solución en una variable que va variando con cada nueva mejor solución encontrada. Así, si una solución es peor que la que se acaba de encontrar, el algoritmo no actualizará la solución. De esta forma, devolverá siempre la mejor solución que haya encontrado.

== Ejemplos de aplicación de backtracking ==

SATISFABILITY

----

Inicialmente A contiene la expresión booleana que constituye el problema.

Elegir subproblema de A, p.ejemplo : (x+y+z)(x'+y)(y'+z)(z'+x)(x'+y'+z').

Elegir una cláusula con mínimo número de literales.

Elegir una variable x, y, z,... dentro de la cláusula y crear 2 subproblemas reemplazando x=V y x=F.

En el caso x=V

Omitir las cláusulas donde aparece x.

Omitir x' en las cláusulas que aparece x'.

En el caso x=F

Omitir las cláusulas donde aparece x'.

Omitir x en las cláusulas que aparece x.

Test

Si no quedan cláusulas. STOP. (solución encontrada).

Si hay una cláusula vacía. DROP.

En otro caso añadir a A

Nota: Observemos que si encontramos a A vacío entonces la expresión booleana no puede ser satisfecha.

 '''HAMILTON CYCLE (VIAJANTE DE COMERCIO)'''

----

En este caso los subproblemas S son caminos que parten de a y llegan a b a través de un sucesión de nodos T. (b es el mismo a lo largo de todo el algoritmo).

Inicialmente A contiene solamente el camino (a, vacío, b).

Elegimos un subproblema S cualquiera de A (y lo borramos de A) y añadimos ramas (c, a) del grafo (las c's son las adyacentes de a) . Estos caminos extendidos son los hijos. Ahora cada c juega el rol de a.

Examinamos c/ hijo:

Test:

1)Si G-T forma un camino hamiltoniano STOP (solución hallada)

2)Si G-T tiene un nodo de grado uno (excepto a y b) o si G-T-{a, b} es disconexo entonces DROP este subproblema .

3) Si 1) y 2) fallan add subproblema en A.

 '''EXACT COVER'''

----

Dado un conjunto finito U y una familia se subconjuntos {Tj} de U definimos una matriz A donde cada fila se corresponde con un elemento ui de U y cada columna de A con un subconjunto Tj . Ponemos aij=1 si uiU pertenece a Tj y aij=0 en caso contrario. Interpretamos que xj=1 significa que elegimos Tj y 0 en caso contrario.

Se trata de averiguar si es factible Ax=1 donde A y x son binarias y las componentes de 1 son unos.

S0= un vector de ceros (raíz del árbol)

Cada nodo S del árbol es una sucesión x cuyas primeras k componentes le han sido asignados un 1 o un 0 y el resto de componentes son ceros. Reemplazamos S por 2 subproblemas Si (i=1,2) poniendo xk+1 =1 y xk+1=0 respectivamente.

Test

if Ax=1 STOP

if Ax>1 DROP Si

if Ax<1 add Si to A

== Ejemplos de problemas comunes resueltos usando Vuelta Atrás ==

'''Problema de las N Reinas'''

----

Disponemos de un tablero de ajedrez de tamaño NxN, y se trata de colocar en él N reinas de manera que no se amenacen según las normas del ajedrez.

proc NReinas (↕[1 . . . i ]: TSolución, ↓N: N, ↑ok: B)
variables j : N
inicio
si i=N entonces ok=CIERTO
en otro caso
ok=FALSO
j=1
mientras ¬ok ^ (j≤N) hacer
si EsFactible (R, j) entonces
R[i + 1]= j
NReinas (R, N, ok)
finsi
j=j+1
finmientras
finsi
fin

func EsFactible (↓R[1 . . . i ]: TSolución, ↓j : N): B
variables factible: B
inicio
factible=CIERTO
k=1
mientras factible ^ (k≤i) hacer
si (j=R[k])\/(i+1−k= |j−R[k]|) entonces
factible=FALSO
finsi
k=k+1
finmientras
devolver factible
fin

                          

'''Problema de la mochila 0,1'''

----

Dados n elementos e1,e2,...,en con pesos p1,p2,...,pn y beneficios b1,b2,...,bn, y dada una mochila capaz de albergar hasta un máximo de peso M (capacidad de la mochila), queremos encontrar cuáles de los n elementos hemos de introducir en la mochila de forma que la suma de los beneficios de los elementos escogidos sea máxima, sujeto a la restricción de que tales elementos no pueden superar la capacidad de la mochila.

            [[Image:Alg1.jpg]]            [[Image:Alg2.jpg]] 

'''Problema del laberinto'''

----

Se tiene una matriz bidimensional de nxn casillas para representar un laberinto cuadrado. Cada casilla está marcada como visitada o no visitada. Se debe ir desde la casilla (1,1) a la (n, n) haciendo movimientos horizontales y verticales.

[[Image:Alg4.jpg]]
[[Image:Alg5.jpg]]

*[[Problema de las parejas]]
*[[Formación de una palabra con n cubos]]
*[[Sudoku backtracking|Sudoku]]
*[[Problema del laberinto]]
*[[Problema del laberinto con límite]]
*[[Problema del dominó]]
*[[Problema de los movimientos de un caballo]]
*[[Problema del reparto del botín]]
*[[Problema de la mochila utilizando Vuelta Atrás]]
*[[Minimización de cableado en placa]]
*[[Coloreado de grafos]]
*[[Problema del viajante sobre grafos dirigidos]]
*[[Las ocho reinas]]

== Backtracking para la enumeración ==

----

El problema de la enumeración consiste en encontrar todas las soluciones del problema, es por ello que tendremos que recorrer el árbol de estados al completo.

Algoritmo de Backtracking para la enumeración:

proc Bactracking Enum(↕X[1 . . . i ]: TSolución, ↑num: N)
variables L: ListaComponentes
inicio
si EsSolución (X) entonces num num+1
EscribeSolución (X)
en otro caso
L Candidatos (X)
mientras ¬Vacía (L) hacer
X[i + 1] Cabeza (L); L Resto (L)
BacktrackingEnum (X, num)
finmientras
finsi
fin

== Aplicaciones ==

Vuelta atrás se usa en la implementación de los [[Lenguajes de programación]] tales como [[Planner|Lenguaje de programación Planner]] y [[Prolog]]. Además, se usa en los análisis sintácticos de los compiladores. Su uso en [[Inteligencia artificial]] ha sido muy importante, dando lugar a nuevos tipos de búsquedas como el [[A*|A estrella]].

== Branch & Bound ( Ramificación y poda ) ==

----

Este método busca una solución como en el método de backtracking, pero cada solución tiene asociado un costo y la solución que se busca es una de mínimo costo llamada óptima. Además de ramificar una solución padre (branch) en hijos se trata de eliminar de consideración aquellos hijos cuyos descendientes tienen un costo que supera al óptimo buscado acotando el costo de los descendientes del hijo (bound). La forma de acotar es un arte que depende de cada problema. La acotacion reduce el tiempo de búsqueda de la solución óptima al "podar" (pruning) los subarboles de descendientes costosos.

[[Category:Algoritmos]]