Introducción
Existen un conjunto de técnicas de diseño de algoritmos que se han aplicado en forma consistente para la solución de problemas. Una de ellas es la fuerza bruta.
En esta técnica se evalúan todas las posibles soluciones y se elige alguna. Generalmente la primera que se encuentre.
Un problema típico es el siguiente: ubicar 8 reinas en un tablero de ajedrez de tal forma que ninguna de ellas se amenace.
En la siguiente figura se presenta un ejemplo de posibles configuraciones del tablero.
Por medio de la técnica de fuerza bruta se verifican todas las distintas posibles posiciones para las 8 reinas y se descartan aquellas en las cuáles éstas se amenazan. Sin embargo el número de combinaciones diferentes es muy alto: 64! /56! = 178,462,987,637,760 posibilidades. El algoritmo podría terminar cuando ubique una configuración válida.
La fuerza bruta también se aplica para buscar elementos en un arreglo: se examinan los registros del primero hasta encontrar el elemento a buscar.
def busquedaSecuencial(x, A):
""" Busca el elemento x en el arreglo A."""
assert isinstance(A, list)
i = 0
while i < len(A) and A[i] != x:
i += 1
return None if i == len(A) else i
El problema que presenta la técnica de fuerza bruta es que el número de soluciones candidatas puede ser computacionalmente prohibitivo.
Técnica de Backtracking
Backtracking es un refinamiento de la técnica de fuerza bruta. La solución es representada por una lista de valores los cuales se van recopilando por medio de un recorrido en el árbol de soluciones.
Se inicia con la lista vacía. La idea es encontrar una lista [v1, v2, v3, …, vk] que sea una solución al problema.
En el ejemplo anterior se evalúa [S(1)]; si no es solución se considera [S(1), S(1,1)]; si no es posible ubicar ninguna solución en el subárbol S(1,1), se intenta con el subárbol S(1,2) y así sucesivamente. Este recorrido recibe el nombre de búsqueda por primero en profundidad.
def backTracking(v):
assert v es una lista v[0], v[1], ..., v[i]
assert v[k] es un punto de la solución
if vector es una solución:
return vector
for vp in posibles(v[i]):
if v + [vp] es un vector acceptable:
sol = backTracking(v + [vp])
if sol != []:
return sol
return []
El problema del laberinto
En este problema suponemos la existencia de un laberinto, en el cual está ubicado un queso. La idea es encontrar algún camino, a partir de una posición inicial, que lleve al queso (en caso de que exista).
Para representar el laberinto utilizaremos una matriz de valores enteros, representada por medio de una lista de listas, en donde la posición [i, j] puede tomar los siguientes valores:
- 0 si es una casilla libre
- 1 si es una casilla en donde hay una pared
- 3 es la casilla que contiene el queso.
Para simplificar la creación del laberinto se utiliza una tira de caracteres. Por medio de la tira se especifica la configuración del laberinto. La función creaLaberiton recibe una tira y retorna una lista de listas. Analice el siguiente código.
stringLab = "00000000000000\n" + \
"01111111111110\n" + \
"00000000000010\n" + \
"01111111111110\n" + \
"01111111111110\n" + \
"01111111111110\n" + \
"00000000003110"
def creaLaberinto(stringLab) :
""" Crea un laberinto a partir de una tira de entrada.
Entradas:
stringLab : tira que contiene el diseño del
laberinto.
Salidas:
Laberinto representado por una matriz, tal que
la entrada i,j contiene: 0 - si la casilla está
libre, 1 - si hay pared, 3 - posición en donde
está el queso.
Restricciones:
Todas las entradas de la tira son 0, 1 o 3. Las
filas se representan por un cambio de línea.
No hay líneas vacías.
"""
lista = stringLab.split()
lista = [ x[:-1] if x[-1] == "\n" else x for x in lista]
lista = [[int(ch) for ch in x] for x in lista]
return lista
def impLab(laberinto):
""" Imprime un laberinto.
Entradas:
laberinto : laberinto a imprimir.
Salidas:
Ninguna.
Restricciones:
El laberinto está representado por listas de
listas, y es una representación consistente. """
for x in laberinto:
for y in x:
print(y, end= "")
print()
laberinto = creaLaberinto(stringLab)
impLab(laberinto)
El siguiente código resuelve el problema del laberinto.
def recorrido(i, j):
""" Dado un laberinto en donde se ubica un queso,
retorna en una lista de pares ordenados (x,y)
que indican el camino desde una posición inicial
(i,j) hasta la posición en que se encuentra el
queso.
Entradas:
(i, j) : posición inicial a partir de donde
se realizará la búsqueda de un camino
hasta la posición del queso.
Salidas:
Lista con las casillas, expresadas como pares
ordenados, que llevan desde la posición inicial
hasta la posición en que se encuentra el queso.
Si no existe un camino retorna la lista vacía.
"""
if laberinto[i][j] == 3:
return [(i, j)]
if laberinto[i][j] == 1:
return []
laberinto[i][j] = -1
if i > 0 and laberinto[i - 1][j] in [0, 3]: # Norte
camino = recorrido(i - 1, j)
if camino: return [(i, j)] + camino
if j < len(laberinto[i]) - 1 and laberinto[i][j + 1] in [0, 3]: # Este
camino = recorrido(i, j + 1)
if camino: return [(i, j)] + camino
if i < len(laberinto) - 1 and laberinto[i + 1][j] in [0, 3]: # Sur
camino = recorrido(i + 1, j)
if camino: return [(i, j)] + camino
if j > 0 and laberinto[i][j - 1] in [0, 3]: # Oeste
camino = recorrido(i, j - 1)
if camino: return [(i, j)] + camino
return []
for x in recorrido(6,13) : print(x)
Observe que recorrido es la función que implementa la técnica de backtracking. La función recibe la posición en el laberinto a partir de la cual se desea realizar la búsqueda y retorna una lista con las posiciones que conforman el camino. La función recorrido se invoca con la posición inicial. En el ejemplo esa posición es la (6, 13) – ver línea 044.
Lo primero que se hace en recorrido es verificar si con la posición (i, j) se tiene una solución (línea 018). Por otra parte si en esa misma posición hay un bloque (no se puede caminar !) retorna []. Para evitar que el ratón «camine por lugares ya andados» se marca la posición (i, j) con el valor de -1.
En esta implementación se supone que los desplazamientos válidos son los que se muestran en la siguiente figura.
Por ejemplo, en la línea 026 se verifica si el movimiento Norte es válido. En la línea 027 se realiza una invocación recursiva con el objetivo de encontrar un camino desde esa nueva posición que está al norte. Si el camino existe entonces se retorna la lista que contiene (i, j) más ese camino (ver línea 028).
Si ninguno de los movimientos es posible se retorna [] (ver línea 042).
Introducción a la programación 