A veces, problemas que parecen ser muy distintos resultan ser parecidos cuando piensas acerca de la manera en cómo resolverlos. ¿Que tienen en común Pac-Man, la familia real de Gran Bretaña y conducir a Orlando? Todos involucran problemas de encontrar rutas o búsquedas de caminos:
  • ¿Como está relacionado el actual Príncipe Guillermo con el Rey Guillermo III, quien fundó la Universidad de William y Mary (College of William and Mary) en 1693?
  • ¿Qué camino debería seguir un fantasma para llegar a Pac-Man lo más rápido posible?
  • ¿Cuál es la mejor manera de conducir de Dallas, Texas a Orlando, Florida?
Nos tienen que dar algo de información para resolver cualquiera de estas preguntas.
Por ejemplo, el árbol familiar de la familia real de Gran Bretaña mostraría conexiones entre personas que han estado directamente relacionadas. El Príncipe Guillermo es el hijo de Carlos Felipe Arturo Windsor. Carlos es el hijo de la Reina Isabel II. El problema es encontrar una cadena corta en el árbol familiar que conecte al Príncipe Guillermo y a Guillermo III, al usar estas conexiones directas. Como puedes ver en el siguiente árbol, podrían requerirse bastantes conexiones.
Árbol familiar real con Isabel II y Guillermo III resaltados
Para Pac-Man, necesitamos un mapa del laberinto. Este mapa muestra las conexiones entre casillas abiertas adyacenes en el laberinto (o la falta de conexiones si es que hay una pared en medio) y el problema es encontrar un camino que lleve al fantasma a Pac-Man.
Laberinto de Pac-Man con el fantasma y Pac-Man resaltados
Para poder encontrar una ruta de conducción desde Dallas hasta Orlando, podríamos usar un mapa de los Estados Unidos, que muestre conexiones, caminos, entre ciudades cercanas. Ningún solo camino conecta directamente a Dallas con Orlando, pero hay varias secuencias de caminos que sí.
Mapa de carreteras de Estados Unidos con Dallas y Orlando resaltados

Explorar un laberinto

Echemos un vistazo con más profundidad a algo parecido a Pac-Man, un juego de computadora en el que el personaje principal es controlado al hacer clic en destinos en un laberinto. El juego se muestra a continuación. Trata de hacer clic en algunas ubicaciones para mover al personaje, representado por el círculo amarillo, hacia el objetivo, representado por el rectángulo rojo.
¿Observas cómo el personaje se movió hacia el objetivo? Para hacer que eso ocurra, el programa necesita determinar el conjunto de movimientos preciso que el personaje debe seguir para llegar al lugar donde el usuario hizo clic, y luego animar esos movimientos. Puede haber múltiples caminos que el personaje pueda seguir, y el programa necesita escoger el mejor de esos mejor caminos.
Antes de decidir sobre un algoritmo, las reglas de movimiento deben establecerse primero: las paredes están hechas de casillas grises y las ubicaciones permitidas para viajar están vacías. En cada paso, el personaje puede moverse de una casilla a una casilla adyacente. Este personaje, como una torre de ajedrez, no se puede mover diagonalmente.
Aquí está la idea detrás del algoritmo que usa este programa: en cada paso, muévete 1 casillas más cerca del objetivo (el lugar en donde hizo clic el usuario). Pero ¿qué significa "más cerca del objetivo"? Viajar en línea recta hacia el objetivo con frecuencia causará que el personaje choque contra una pared. El algoritmo necesita determinar cuáles de las casillas adyacentes en efecto están "más cerca del objetivo" y podemos hacer eso al asignarle un "costo" a cada casilla que represente el número mínimo de pasos que el personaje tendría que tomar para llegar desde ese vértice al objetivo. Aquí hay un algoritmo para asignarle un costo a cada casilla:
  1. Empieza en la casilla objetivo. ¿Qué tan lejos está el objetivo del objetivo? Cero pasos, entonces marca el objetivo con el número 0.
  2. Encuentra todas las casillas en el laberinto que están exactamente a un paso del objetivo. Márcalas con el número 1. En este laberinto, si el objetivo es la casilla de salida, entonces solo hay una casilla que está exactamente a un paso.
  3. Ahora encuentra todas las casillas en el laberinto que están exactamente a dos pasos del objetivo. Estas casillas están a un paso de aquellas marcadas con 1 y todavía no han sido marcadas. Marca estas casillas con el número 2.
  4. Marca todas las casillas en el laberinto que están exactamente a tres pasos del objetivo. Estas casillas están a un paso de aquellas marcadas con 2 y todavía no han sido marcadas. Marca estas casillas con el número 3.
  5. Sigue marcando casillas en el laberinto en orden creciente de distancia desde el objetivo. Después de marcar las casillas con el número k, marca con el número k, plus, 1 todas las casillas que están a un paso de aquellas marcadas con k y aún no han sido marcadas.
Eventualmente, el algoritmo marca la casilla en donde el personaje empieza. Entonces el programa puede encontrar un camino hacia el objetivo al escoger una secuencia de casillas desde el inicio tales que los números en las casillas siempre disminuyan a lo largo del camino. Si vieras el número como la altura de la casilla, sería como ir cuesta abajo.
A continuación, puedes jugar con el algoritmo de marcado de costos. Haz clic en "Reiniciar algoritmo" para volver a iniciar los pasos.
¿Qué pasa si el usuario estuviera intentando ir desde la casilla inicial hasta el objetivo? Al usar el algoritmo de marcar casillas, la casilla inicial está a 13 pasos del objetivo. Aquí hay una imagen que muestra las conexiones entre las posibles ubicaciones para el personaje, el inicio, el objetivo y la distancia más corta de cada ubicación al objetivo:
Grafo correspondiente al laberinto
Hay una casilla inmediatamente al sur del inicio (renglón cuatro, columna tres) que está a solo 12 pasos del objetivo. Así que el primer movimieno es "sur". Al sur de esa casilla está un 11. De nuevo hacia el sur. De nuevo hacia el sur a un 10. Luego al este a un 9. Dos veces más hacia el este a un 7, luego hacia el norte cinco veces a un 2. Termina por ir una vez hacia el oeste, a un 1, y por último una vez hacia el norte, al objetivo.
Por ahora, no discutiremos exactamente cómo implementar este algoritmo de búsqueda en un laberinto, pero puedes encontrar divertido pensar cómo podrías representar el laberinto y el personaje al usar JavaScript, y cómo podrías implementar el algoritmo.

Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom junto con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.