Contenido principal
Curso: Ciencias de la computación > Unidad 1
Lección 1: Introducción a los algoritmosEncontrar un camino
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.
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.
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í.
Explorar un laberinto
Los juegos de laberintos son divertidos, así que vamos a profundizar en uno. En nuestro juego, el personaje principal puede navegar a ciertos destinos en un laberinto.
Como el jugador humano, tú controlas al personaje principal al hacer clic en el siguiente destino en el laberinto, y la computadora averigua cómo mover al personaje ahí. El destino está marcado con un rectángulo rojo etiquetado como "GOAL" (META), y el personaje empieza desde su primer destino, el cuadrado de salida. Intenta jugarlo a continuación:
¿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:
- Empieza en la casilla objetivo. ¿Qué tan lejos está el objetivo del objetivo? Cero pasos, entonces marca el objetivo con el número 0.
- 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.
- 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.
- 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.
- Sigue marcando casillas en el laberinto en orden creciente de distancia desde el objetivo. Después de marcar las casillas con el número
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:
Hay una casilla inmediatamente al sur del inicio que está a solo 12 pasos del objetivo. Así que el primer movimiento 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.
¿Quieres unirte a la conversación?
Tengo una duda en cuanto al juego de "Explorar un laberinto". Si el punto amarillo estuviera en la posición de la esquina superior izquierda y el destino fuera la posición de la esquina inferior derecha, ¿Porque el punto amarillo siempre toma la vía que va en sentido {izquierda-derecha-arriba-abajo}? y no toma la vía que va en sentido {arriba-abajo-izquierda-derecha} si las dos opciones tienen el mismo numero de pasos.(11 votos)
pero cabe la posibilidad de que no llegues a donde tu quieras(6 votos)
i like the examples they put because they are somehow a fun way to learn about this(10 votos)
bueno pues creo que esta muy interesante poder poner a funcionar nuestra cabeza y poder dar nuestro punto de vista(15 votos)
Esta todo el tema en ingles y me es complicado gracias.(3 votos)
eso es verdad yo siempre lo uso cuando algo esta en ingles(2 votos)
¿Si no se pudiera llegar al objetivo por un algo bloqueando el camino al objetivo, que pasaría?(6 votos)
A mi me encanta la programacion(3 votos)
este es un programa parecido al que se usa en pac man o las mismas técnicas? y se puede hacer otro juego que no sea laberinto con este programa?(2 votos)- ¿como podemos lograr algo si usamos codigos?(2 votos)
- ¿como podemos implementar un algoritmo de busqueda en una formula?(2 votos)
muy buen juego y entretenido(2 votos)