PDF de programación - Capítulo 6 - Vuelta Atrás

Imágen de pdf Capítulo 6 - Vuelta Atrás

Capítulo 6 - Vuelta Atrásgráfica de visualizaciones

Publicado el 17 de Agosto del 2019
614 visualizaciones desde el 17 de Agosto del 2019
176,7 KB
21 paginas
Creado hace 8a (26/12/2015)
Capítulo 6

Vuelta Atrás1

Más vale una retirada a tiempo que una batalla
perdida.

Napoleón Bonaparte.

Resumen: En este tema se introduce el esquema algorítmico de Vuelta atrás, o
Backtracking, que es una técnica de carácter general utilizada para resolver una gran
clase de problemas, en especial de problemas que exigen un recorrido exhaustivo del
universo de soluciones.

1. Motivación

Dado un mapa M y un número n > 0 se pide encontrar las formas de colorear los
países de M utilizando un máximo de n colores, de tal manera que ningún par de países
fronterizos tenga el mismo color.

Una forma de resolver el problema es generar todas las posibles maneras de colorear
el mapa y después desechar aquellas en que dos países fronterizos tienen el mismo color.
Esta forma de resolver el problema sólo resulta aceptable si el conjunto de países, m, y el
conjunto de colores, n, son pequeños, ya que el número de posibles formas de colorear el
mapa viene dado por las variaciones con repetición de n elementos tomados de m en m:
V Rm
n = nm. En la siguiente tabla se muestra el número de posibilidades que habría que
generar para algunos valores de n y m.

n: colores m: países
3
5
3

17
17
50

no de posibilidades
129.140.163
762.939.453.125
717.897.987.691.852.588.770.249

Se observa, que si tomamos las 17 comunidades autónomas de España, el número de
posibilidades a generar con 5 colores sería superior a los 700 mil millones. Si consideramos
las 50 provincias, con sólo 3 colores, el número de posibilidades supera el millón de billones.

1 Miguel Valero Espada es el autor principal de este tema.

Modificado por Isabel Pita en el curso 2012/13.

115

116

Capítulo 6. Vuelta Atrás

En este capítulo se explica como abordar aquellos problemas cuya única forma conocida
de resolver es la generación de todas sus posibles soluciones, para obtener de entre ellas la
solución o soluciones reales.

2.

Introducción

Existen problemas, como el que se presenta en el apartado anterior, para los que no
parece existir una forma o regla fija que nos lleve a obtener una solución de una manera
eficiente y precisa. La manera de resolverlos consiste en realizar una búsqueda exhaustiva
entre todas las soluciones potenciales hasta encontrar una solución válida, o el conjunto de
todas las soluciones válidas. A veces se requiere encontrar la mejor (en un sentido preciso)
de todas las soluciones válidas.

La búsqueda exhaustiva en un espacio finito dado se conoce como fuerza bruta y con-
siste en ir probando sistemáticamente todas las soluciones potenciales hasta encontrar una
solución satisfactoria, o bien agotar el universo de posibilidades. En general, la fuerza bru-
ta es impracticable para espacios de soluciones potenciales grandes, lo cual ocurre muy
a menudo, ya que el número de soluciones potenciales tiende a crecer de forma exponen-
cial con respecto al tamaño de la entrada en la mayoría de los problemas que trataremos.
Obsérvense los valores que se proporcionan en el ejemplo de la sección anterior.

El esquema algorítmico de vuelta atrás es una mejora a la estrategia de fuerza bruta, ya
que la búsqueda se realiza de manera estructurada, descartando grandes bloques de solu-
ciones para reducir el espacio de búsqueda. La diferencia principal entre ambos esquemas
es que en el primero las soluciones se forman de manera progresiva, generando soluciones
parciales, comprobando en cada paso si la solución que se está construyendo puede condu-
cir a una solución satisfactoria. Mientras que en la fuerza bruta la estrategia consiste en
probar una solución potencial completa tras otra sin ningún criterio.

En el esquema de vuelta atrás, si una solución parcial no puede llevar a una solución
completa satisfactoria, la búsqueda se aborta y se vuelve a una solución parcial viable,
deshaciendo decisiones previas. Este esquema debe su nombre a este salto hacia atrás.

Tomemos como ejemplo el siguiente problema: dadas n letras diferentes, diseñar un
algoritmo que calcule las palabras con m letras (m ≤ n) diferentes escogidas entre las
dadas. El orden de las letras es importante: no será la misma solución abc que bac.

El número de soluciones potenciales o espacio de búsqueda es de nm, que representan
las variaciones con repetición de n letras tomadas de m en m. Realizar una búsqueda
exhaustiva en este espacio es impracticable.

Antes de ponernos a probar sin criterio alguno entre todas las posibles combinaciones
de letras, dediquemos un segundo a evaluar la estructura de la solución. Es evidente que
no podemos poner dos letras iguales en la misma palabra, así que vamos a replantear el
problema. Trataremos de colocar las letras de una en una, de forma que no se repitan. De
esta manera, toda solución del problema se puede representar como una tupla (x1, .., xm)
en la que xi representa la letra que se coloca en el lugar i-ésimo de la palabra.

La solución del problema se construye de manera incremental, colocando una letra
detrás de otra. En cada paso se comprueba que la última letra no esté repetida con las an-
teriores. Si la última letra colocada no está repetida, la solución parcial se dice prometedora
y la búsqueda de la solución continúa a partir de ella. Si no es prometedora, se abortan
todas las búsquedas que partan de esa tupla parcial.

De manera general, en los algoritmos de vuelta atrás, se consideran problemas cuyas
soluciones se puedan construir por etapas. Una solución se expresa como n-tupla (x1, .., xn)

Estructura de Datos y Algoritmos

2. Introducción

117

donde cada xi ∈ Si representa la decisión tomada en la i-ésima etapa de entre un conjunto
finito de alternativas.

Una solución tendrá que minimizar, maximizar, o simplemente satisfacer cierta función
criterio. Se establecen dos categorías de restricciones para los posibles valores de una tupla:

Restricciones explícitas, que indican los conjuntos Si. Es decir, el conjunto finito
de alternativas entre las cuales pueden tomar valor cada una de las componentes de
la tupla solución.

Restricciones implícitas, que son las relaciones que se han de establecer entre las
componentes de la tupla solución para satisfacer la función criterio.

Volviendo al ejemplo de las palabras con letras diferentes, hemos visto que la solución
será una m-tupla y que cada valor de la tupla es una letra en la palabra. Las restricciones
serán:

Restricciones explícitas para el problema de las palabras:

• Si = {1, . . . , n}, 1 ≤ i ≤ m. Es decir, cada letra tiene que pertenecer al alfabeto.

Restricciones implícitas para el problema de las palabras:

• No puede haber dos letras iguales en la misma palabra.

• Las soluciones son, por tanto, variaciones sin repetición de n elementos tomados
de m en m, es decir
(n−m)! . Si consideramos palabras de 5 letras sobre un
alfabeto de 27 letras distintas, el número de posibilidades se reduce de 275 =
14.348.907 a 27!

n!

22! = 9.687.600.

El espacio de soluciones potenciales a explorar estará formado por el conjunto de tuplas
que satisfacen las restricciones explícitas. Este espacio, se puede estructurar como un árbol
de exploración, donde en cada nivel se toma la decisión sobre la etapa correspondiente.

Se denomina nodo de estado a cualquier nodo del árbol de exploración que satisfaga las
restricciones explícitas, y corresponde a una tupla parcial o una tupla completa. Los
nodos solución serán los correspondientes a las tuplas completas que además satisfagan las
restricciones implícitas.

Un elemento adicional imprescindible es la función de poda o test de factibilidad, que
permite determinar cuándo una solución parcial puede conducir a una solución satisfactoria.
De tal manera que si un nodo no satisface la función de poda es inútil continuar la búsqueda
por esa rama del árbol. La función de poda permite pues reducir la búsqueda en el árbol
de exploración.

Una vez definido el árbol de exploración, el algoritmo realizará un recorrido del árbol
en cierto orden, hasta encontrar la primera solución. El mismo algoritmo, con ligeras mo-
dificaciones, se podrá utilizar para encontrar todas las soluciones, o una solución óptima.
El árbol de exploración no se construye de manera explícita, es decir no se almacena en
memoria, sino que se va construyendo de manera implícita conforme avanza la búsqueda
por medio de llamadas recursivas. Durante el proceso, para cada nodo se generarán los
nodos sucesores (estados alcanzables tomando una determinada decisión correspondiente
a la siguiente etapa). En el proceso de generación habrá distintos tipos de nodos:

Nodos vivos Aquellos para los cuales aún no se han generado todos sus hijos. Todavía

pueden expandirse.

Facultad de Informática - UCM

118

Capítulo 6. Vuelta Atrás

Nodo en expansión Aquel para el cual se están generando sus hijos.

Nodos muertos Aquellos que no hay que seguir explorando porque, o bien no han supe-
rado el test de factibilidad, o bien se han explorado insatisfactoriamente todos sus
hijos.

El recorrido del árbol de exploración se realiza en profundidad. Cuando se llega a un
nodo muerto, hay que deshacer la última decisión tomada y optar por otra alternativa
(vuelta atrás). La forma más sencilla de expresar este retroceso es mediante un algoritmo
recursivo, ya que la vuelta atrás se consigue automáticamente haciendo terminar la llamada
recursiva y volviendo a aquella que la invocó.

El coste de los algoritmos de vuelta atrás en el caso peor es del orden del tamaño
del árbol de exploración, ya que en el peor de los casos nos veremos obligados a recorrer
exhaustivamente todas las posibilidades. El espacio de soluciones potenciales suele ser,
como mínimo, exponencial en el tamaño de la entrada. La efectividad de la vuelta atrás va
a depender decisivamente de las funciones de poda que se utilicen, ya que si son adecuadas
permitirán reducir considerablemente el número de nodos explorados.

Se podrían realizar búsquedas más inteligentes haciendo que en cada momento se ex-
plore el nodo más prometedor, utilizando para ello algún t
  • Links de descarga
http://lwp-l.com/pdf16470

Comentarios de: Capítulo 6 - Vuelta Atrás (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad