A veces, problemas que parecen ser muy distintos resultan ser similares si lo piensas de la manera en cómo resolverlos (como lo hace un computador). Por ejemplo: ¿Que tienen en común Pac-Man y conducir a Quito? Todos involucran problemas de encontrar
rutas o búsquedas de caminos.
Para Pac-Man, se nececitaría un mapa del laberinto. Este mapa debe mostrar
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 Loja hasta Quito, podríamos usar un mapa del Ecuador, que muestre conexiones, caminos, entre ciudades cercanas. Ningún solo camino conecta directamente a Loja con Quito, pero hay varias secuencias de caminos que sí.
Explorar un laberinto
Veamos con más profundidad 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 (espacios en blanco) 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.
AHORA PIENSA EN UNA CIUDAD QUE TE GUSTARÍA VISITAR Y ESCRIBE LA RUTAS DE CIUDADES QUE SEGUIRÍAS