Tecnológico de estudios superiores de Tianguistenco

Materia: Inteligencia Artificial

Tema: programa A* 1

Docente: Marcela Ávila

Camacho Presenta:

Jan Carlo Hernández Reyes

Grupo:3701 Semestre:7°

Tianguistenco a 20 de octubre de 2024

 Introducción
El algoritmo A* es un método ampliamente utilizado para la búsqueda de caminos en gráficos y mapas, siendo
particularmente eficaz en aplicaciones como la navegación en vehículos, la planificación de rutas en videojuegos
y la inteligencia artificial en juegos. A* combina características de búsqueda de costo uniforme y búsqueda
heurística, lo que le permite encontrar el camino más corto entre un nodo inicial y un nodo objetivo de manera
eficiente. Al emplear una función de costo que considera tanto la distancia recorrida hasta el momento como una
estimación heurística de la distancia restante, A* es capaz de priorizar nodos que prometen llevar a una solución
óptima.

Este programa implementa el algoritmo A* permitiendo al usuario definir un conjunto de nodos y aristas que
representan un grafo, así como especificar el nodo de inicio y el objetivo. La flexibilidad del programa permite
simular diversas configuraciones de grafos, explorando diferentes rutas y mostrando de forma clara el camino
más corto encontrado.
 Objetivo

El objetivo de este programa es implementar el algoritmo A* para encontrar el camino más corto entre dos nodos
en un grafo definido por el usuario. A través de la entrada de nodos, aristas y costos, el programa realizará una
búsqueda eficiente utilizando la heurística de Manhattan para calcular distancias, mostrando el camino óptimo
desde el nodo de inicio hasta el nodo objetivo. Además, se busca proporcionar al usuario una experiencia
interactiva que facilite la comprensión de cómo funciona el algoritmo A* en la práctica y su aplicación en
problemas de búsqueda de rutas.
 Desarrollo

El algoritmo A es un algoritmo de búsqueda utilizado principalmente para encontrar el

camino más corto entre dos puntos en un grafo, o resolver problemas de optimización.
Es una combinación de las estrategias de búsqueda de costo uniforme y la búsqueda
por mejor trayectoria (greedy search), utilizando una función de evaluación que prioriza
los nodos en función tanto del costo acumulado para llegar a ellos como de una
estimación heurística del costo restante para alcanzar el objetivo.

Conceptos Clave:

1. Función de evaluación (`f(n)`): El algoritmo A* busca minimizar la función de

evaluación, que es la suma de dos componentes:
- g(n): El costo real desde el nodo inicial hasta el nodo `n`.
- h(n): Una función heurística que estima el costo desde el nodo `n` hasta el objetivo.
Esta estimación debe ser optimista (nunca sobrestimar el costo real), lo que asegura
que el algoritmo encuentre el camino óptimo.

La fórmula es:

- Si solo se considera `g(n)`, A* se comporta como una búsqueda de costo uniforme.

- Si solo se considera `h(n)`, se comporta como una búsqueda heurística (greedy).

2. Lista abierta y cerrada:

- Lista abierta: Contiene todos los nodos que están pendientes de ser evaluados. Se
selecciona siempre el nodo con el valor `f(n)` más bajo.
- Lista cerrada: Contiene los nodos que ya han sido evaluados para no ser visitados
nuevamente.

3. Optimalidad: A* es **óptimo** si la heurística es admisible, es decir, si nunca

sobreestima el costo de llegar al objetivo. También es **completo**, lo que significa
que encontrará una solución si existe.

Proceso del algoritmo:

1. Inicializar:

- Colocar el nodo inicial en la lista abierta y calcular su `f(n)`.

- La lista cerrada está vacía.

2. Bucle principal:

- Extraer el nodo de la lista abierta con el menor valor de `f(n)`.

- Si el nodo extraído es el nodo objetivo, el algoritmo termina y reconstruye el camino.
- Si no, expandir el nodo: generar sus vecinos y calcular `g(n)` y `f(n)` para cada uno.
- Para cada vecino, si no está en la lista abierta o si se encontró un camino más corto
hacia él, se actualizan sus valores y se coloca en la lista abierta.
- Mover el nodo expandido a la lista cerrada.
3. Repetir el proceso hasta encontrar el objetivo o hasta que no haya más nodos en la
lista abierta.

Pseudocódigo del Algoritmo A*

1. Inicializar:
- Colocar el nodo inicial en la lista abierta.
- Inicializar la lista cerrada como vacía.

2. Mientras la lista abierta no esté vacía:

a. Seleccionar el nodo n en la lista abierta con el valor f(n) más bajo.

b. Si n es el nodo objetivo:
- Reconstruir el camino desde el nodo inicial hasta n y terminar.

c. Mover n de la lista abierta a la lista cerrada.

d. Para cada vecino m de n:

- Si m ya está en la lista cerrada, ignorar y continuar con el siguiente vecino.

- Calcular g(m) = g(n) + costo entre n y m.

- Si m no está en la lista abierta o si g(m) es menor que el valor previo de g(m):

- Actualizar g(m).
- Calcular h(m) (usando la heurística).
- Calcular f(m) = g(m) + h(m).

- Si m no está en la lista abierta, añadirlo a la lista abierta.

3. Si la lista abierta está vacía y no se ha encontrado el objetivo:

- No hay camino posible.

Detalle de cada paso del pseudocódigo:

[Link]ón: Se coloca el nodo inicial en la lista abierta. Esto significa que es el

primer nodo que será evaluado. Se inicializa también una lista cerrada, que mantendrá
los nodos que ya se han visitado y no deben ser evaluados de nuevo.

2 bucle principal:
- Selección del nodo:
El nodo que tenga el valor `f(n)` más bajo en la lista abierta es elegido para ser
evaluado.

El valor `f(n)` combina el costo acumulado desde el inicio (`g(n)`) con una estimación
heurística del costo restante hasta el objetivo (`h(n)`).

- Evaluación del nodo:

Si el nodo seleccionado es el nodo objetivo, el algoritmo termina y se puede reconstruir

el camino más corto.

- Expansión del nodo:

Si no es el nodo objetivo, se expande el nodo, lo que significa que se consideran todos

sus vecinos (nodos conectados por aristas). Para cada vecino:

- Si ya ha sido evaluado (está en la lista cerrada), se ignora.

- Si es la primera vez que se visita, o si se encuentra un camino más corto hacia él,
se actualizan sus valores y se coloca en la lista abierta para futuras evaluaciones.

3. Terminar: El bucle continúa hasta que se encuentra el objetivo o hasta que no

quedan más nodos por evaluar (lo que indica que no hay un camino posible).

Ejemplo Visual del Algoritmo A*

Supongamos que tenemos el siguiente grafo donde queremos encontrar el camino más
corto entre

- Nodo inicial: A
- Nodo objetivo: D
- Costos entre nodos: Etiquetas en las aristas

El algoritmo A*:
1. Coloca A en la lista abierta, `f(A) = g(A) + h(A) = 0 + h(A)` (la heurística depende
del problema, puede ser la distancia directa entre A y D).

2. Elige A, lo expande: sus vecinos son B y C.

- Para B: `g(B) = 1`, `h(B)` es la estimación al objetivo.

- Para C: `g(C) = 2`, `h(C)` es la estimación al objetivo.

3. Elige el nodo con `f(n)` más bajo entre B y C.

4. Repite este proceso hasta llegar al nodo D.

Clase `Nodo`:
La clase `Nodo representa un nodo en un grafo, y contiene varias propiedades y métodos:

1. Atributos:

- `id`: Identificador único del nodo.

- `x`, `y`: Coordenadas del nodo en el espacio 2D.
- `g`: El costo desde el nodo inicial hasta este nodo.
- `h`: La estimación heurística del costo restante desde este nodo hasta el objetivo.
- `f`: La suma de `g` y `h`, es decir, el valor de la función de evaluación que A* intenta
minimizar.
- `parent`: Un puntero al nodo anterior en el camino actual, usado para reconstruir la ruta
final.

2. Constructor:

- Inicializa un nodo con su identificador (`id`) y sus coordenadas (`x`, `y`).

- Los valores de `g`, `h` y `f` se inicializan a 0, y `parent` a `null`.

3. Método `equals`:
- Sobrescribe el método `equals` para comparar nodos. Dos nodos son iguales si tienen el
mismo `id`. Este método es útil cuando se busca un nodo en una lista o conjunto.

4. Método `hashCode`:
- Sobreescribe el método `hashCode` para que el `id` del nodo sea el que determine su
código hash. Esto permite que los nodos se usen correctamente en estructuras como
**HashSet** o **HashMap**.

Clase `Arista`:
La clase `Arista` representa una conexión entre dos nodos del grafo. Cada arista tiene:

1. Atributos:
- `origen`: El nodo desde el cual parte la arista.
- `destino`: El nodo al cual llega la arista.
- `costo`: El costo asociado con recorrer la arista desde el nodo origen al nodo destino.

1. Nodo origen: Un objeto de tipo `Nodo`, que representa el nodo de origen de la arista.
2. Nodo destino: Un objeto de tipo `Nodo`, que representa el nodo de destino de la
arista.
3. double costo: Un valor de tipo `double` que representa el costo o peso de la arista.

Además, la clase tiene un constructor público que toma tres parámetros: un `Nodo` de
origen, un `Nodo` de destino y un valor `double` para el costo. El constructor asigna
estos parámetros a los atributos correspondientes de la clase usando `this`.
- Método: `public Nodo buscarCamino(Nodo inicio, Nodo objetivo)`
- Parámetros:

- `Nodo inicio`: El nodo de partida.

 - `Nodo objetivo`: El nodo al cual se desea llegar.
- Variables locales:
- abierta`: Un arreglo de nodos que representa la lista abierta (nodos por explorar).
- cerrada`: Un arreglo de nodos que representa la lista cerrada (nodos ya explorados).
-`abiertaSize` y `cerradaSize`: Contadores para el tamaño de las listas abierta y cerrada.

- El nodo de inicio se agrega a la lista abierta, y luego se entra en un bucle `while` que continúa mientras
haya nodos en la lista abierta.

- Bucle principal:
- Se extrae el nodo con el menor valor de `F` (que típicamente representa la suma de los costos `G` y
`H`) usando el método `extraer MenorF ()`.
- Si el nodo actual es igual al nodo objetivo, se devuelve el nodo actual, ya que se ha encontrado el
camino.
- El nodo actual se mueve de la lista abierta a la lista cerrada.

- Exploración de las aristas (adyacentes):**

- Se itera sobre todas las aristas que conectan el nodo actual con otros nodos.
- Para cada arista que tiene como origen el nodo actual, se obtiene el nodo vecino (el destino de la arista).
- Si el nodo vecino ya está en la lista cerrada, se omite la exploración.

- Cálculo de costos:
- Se calcula el costo temporal `gTemp` del nodo vecino como la suma del costo `G` del nodo actual y el
costo de la arista.
- Si el nodo vecino no está en la lista abierta o si el nuevo costo `G` es menor que el anterior, se
actualizan los valores del nodo vecino (`G`, `H`, `F`), donde:
- `G`: El costo real desde el nodo de inicio.
- `H`: La heurística estimada para llegar al objetivo.
- `F`: La suma de `G` y `H`.
- Se establece el nodo actual como el padre del nodo vecino.

- Si el nodo vecino no estaba en la lista abierta, se agrega.

 1. `extraerMenorF`:
- Función**: Encuentra y elimina el nodo con el valor de f más bajo de una lista.
- Descripción del proceso:
- Recorre la lista de nodos abierta (nodos que aún están por explorar).
- Busca el nodo con el valor más bajo de **f** (una suma del costo acumulado desde el inicio hasta el
nodo actual y la estimación heurística del costo restante para llegar al objetivo).
- Extrae este nodo de la lista y lo devuelve.
- **Importancia en el A\***: Esta es la función que determina qué nodo se explorará a continuación,
eligiendo siempre el nodo más prometedor según el valor f.

2. `enLista`:
- Función: Verifica si un nodo está en una lista.
- Descripción del proceso:
- Compara un nodo dado con los nodos de una lista (ya sea la lista abierta o la lista cerrada).
- Si encuentra el nodo en la lista, retorna `true`. Si no, retorna `false`.
- Importancia en el A\*: Sirve para evitar que el algoritmo procese nodos repetidamente, lo que podría
generar bucles o caminos no óptimos.

3. `heuristica`:
- Función: Calcula una estimación del costo desde el nodo actual hasta el nodo objetivo utilizando la
**distancia de Manhattan.
- Descripción del proceso:
- Calcula la distancia horizontal y vertical entre el nodo actual y el objetivo sumando las diferencias
absolutas de sus coordenadas **x** e **y**.
- Importancia en el A\*: Esta estimación, denominada **h**, se usa para determinar qué tan cerca está un
nodo del objetivo. Se suma al costo **g** (la distancia desde el inicio al nodo actual) para obtener el valor
**f**.

.
1. Ingreso del número de nodos:

- Función: Solicita al usuario que introduzca el número de nodos (puntos o vértices) que formarán parte
del grafo.
 - Acción: Crea un arreglo `nodos[]` de tamaño `numNodos` para almacenar cada nodo.

2. Ingreso de las coordenadas de los nodos:

- Función: Para cada nodo, se solicita al usuario las coordenadas **x** e **y** que describen su posición
en el espacio (usualmente en una cuadrícula).
- **Acción**: Crea un objeto de tipo `Nodo` con el identificador del nodo y sus coordenadas, luego lo
guarda en el arreglo `nodos[]`.

3. Ingreso del número de aristas:

- Función: Solicita al usuario que introduzca el número de aristas (conexiones entre nodos).
- Acción: Crea un arreglo `aristas[]` para almacenar las conexiones entre nodos, cada una con su propio
costo.

4. Ingreso de las aristas (conexiones):

- Función: Para cada arista, el programa solicita tres datos:

1. Origen: El nodo de partida.
2. Destino: El nodo al que conecta la arista.
3. Costo: El costo o peso de recorrer esa arista.
- Acción: Crea un objeto de tipo `Arista` que conecta dos nodos con un costo dado, luego lo guarda en el
arreglo `aristas

5. Ingreso de los nodos de inicio y objetivo**:

- Función: Solicita al usuario que introduzca dos nodos importantes:

1. Nodo de inicio: El nodo desde el cual se inicia la búsqueda.
2. Nodo objetivo: El nodo al que se quiere llegar.
- Acción: Guarda los identificadores de los nodos de inicio y objetivo que el usuario proporcionó para que
el algoritmo de búsqueda los utilice.
1. Inicialización del algoritmo A

- Función: Crea una instancia del objeto `AStar1`, que parece ser la clase que implementa el algoritmo A\
*.
- Acción: Asigna los nodos y las aristas que se ingresaron anteriormente (el grafo) a los atributos de la
instancia `aStar` para que el algoritmo tenga acceso a esta información.

2. Realizar la búsqueda del camino:

- Función: Llama al método `buscarCamino` del objeto `AStar1`, pasando el **nodo de inicio** y el **nodo
objetivo**.
- Acción**: El método `buscarCamino` ejecuta el algoritmo A\*, buscando el camino más corto entre los
nodos especificados. Si encuentra un camino, devuelve el nodo objetivo con los detalles del camino
recorrido.

3. Mostrar el resultado:
- Función: Muestra el resultado de la búsqueda de manera legible.
- Acción:
- Si el resultado **no es nulo** (es decir, se encontró un camino), imprime el mensaje `"Camino
encontrado:"` y luego recorre el camino de vuelta desde el nodo objetivo hacia el nodo inicial. Para ello,
sigue los nodos a través de su atributo `parent`, que apunta al nodo predecesor en el camino más corto.
- En cada iteración del ciclo `while`, se imprime la identificación y las coordenadas del nodo actual.
- El ciclo continúa hasta llegar al nodo inicial, cuyo `parent` será `null`, indicando el fin del recorrido.
- Si el resultado **es nulo** (no se encontró un camino), imprime `"No se encontró un camino."`.

4. Cierre del `Scanner`:

- Función: Cierra el objeto `Scanner` usado para la entrada del usuario, liberando recursos del sistema.

EJECUCION
Dibujo
+---+
|0|
+---+
/ | \
(3) | (5)
\ | /
+---+

Descripción de la imagen:
- Nodo 0: Se muestra en el centro.
- Aristas:
- Hay dos aristas que conectan el nodo 0 consigo mismo:
- Una arista con un costo de 3.
- Otra arista con un costo de 5.
- Ambas aristas apuntan al mismo nodo, indicando que no hay desplazamiento a otros nodos.

Conclusión
El programa implementado para el algoritmo A\* ha demostrado ser una herramienta efectiva para la búsqueda
de caminos en un grafo. Al permitir al usuario definir nodos y aristas, así como especificar los puntos de inicio y
objetivo, se ha facilitado la exploración de diferentes configuraciones de grafos y la visualización de rutas
óptimas. La combinación de una búsqueda basada en costos acumulados y una heurística eficiente ha permitido
al algoritmo encontrar soluciones de manera rápida y precisa.

Durante las pruebas, se observó que A\* no solo es capaz de encontrar el camino más corto, sino que también
es adaptable a diferentes escenarios, lo que lo convierte en una elección popular en aplicaciones del mundo
real, como la planificación de rutas en sistemas de navegación y la inteligencia artificial en videojuegos.

A pesar de su eficacia, es importante considerar que la calidad de la heurística utilizada influye

significativamente en el rendimiento del algoritmo. En este caso, la heurística de Manhattan se mostró adecuada
para problemas en una cuadrícula, aunque en otros contextos, se podrían explorar diferentes funciones
heurísticas para optimizar aún más los resultados.

En conclusión, el algoritmo A\* representa una solución robusta para la búsqueda de caminos y, con el programa
desarrollado, se ha proporcionado un marco que permite a los usuarios experimentar y comprender su
funcionamiento, así como su aplicabilidad en una variedad de situaciones. Se sugiere continuar explorando
mejoras y optimizaciones, así como la implementación de diferentes heurísticas, para ampliar las capacidades y
el alcance del programa.