Algoritmos resolución de problemas mediante búsquedas

Ejercicios módulo Modelos de Intelixencia Artificial

Instalación y Ejecución con uv

Instalación

1. Clona el repositorio:

git clone https://github.com/dfleta/problem-solving-searching.git
cd problem-solving-searching

Si quieres instalar las dependencias de desarrollo del proyecto, utiliza uv, sinom salta al epígrafe "ejecución". 2. Instala uv:

python -m pip install uv

3. Crea y activa un entorno virtual con uv:

uv venv
source .venv/bin/activate  # En Linux/MacOS
# O en Windows:
# .venv\Scripts\activate

4. Instala las dependencias del proyecto declaradas en pyproject.toml

uv sync

Recueda que puedes emplear la interfaz de pip:

pip install -r requirements.txt

5. Instala el linter ruff:

uv sync --group lint

6. Si el programa devuelve el error:

.../problem-solving-searching/src/matrix_plotter.py:104: UserWarning: FigureCanvasAgg is non-interactive, and thus cannot be shown

será necesario instalar python tkinter en el sistema operativo para observar la gráfica:

sudo apt-get install python3-tk

Ejecución

El programa implementa el algoritmo A* y puede ejecutarse desde la línea de comandos con diferentes parámetros:

python a_star.py <estado_inicial> <estado_objetivo> [-v_c COSTO_VERTICAL] [-h_c COSTO_HORIZONTAL]

uv run a_star.py <estado_inicial> <estado_objetivo> [-v_c COSTO_VERTICAL] [-h_c COSTO_HORIZONTAL]

Parámetros

• estado_inicial: Estado desde donde comenzar la búsqueda
• estado_objetivo: Estado que se desea alcanzar
• -v_c: Costo para movimientos verticales (opcional, valor predeterminado: 1)
• -h_c: Costo para movimientos horizontales (opcional, valor predeterminado: 2)

Ejemplos de uso

1. Búsqueda básica de Z a N:

python a_star.py Z N

uv run a_star.py Z N

2. Búsqueda con costos personalizados

python a_star.py -v_c 2 -h_c 3 Z N

uv run a_star.py -v_c 2 -h_c 3 Z N

python3 a_star -h

usage: a_star.py [-h] [-v_c V_C] [-h_c H_C] start_state goal_state

A* Search Algorithm

positional arguments:
  start_state  Initial state
  goal_state   Goal state

options:
  -h, --help   show this help message and exit
  -v_c V_C     Cost for vertical movements
  -h_c H_C     Cost for horizontal movements

Ejemplos

python3 a_star.py -v_c 1 -h_c 2 N J

o

python3 a_star.py N J

o

uv run a_star.py N J

Algoritmo

El método __update_g() actualiza de manera recursiva todos los nodos de la frontera que son descendientes del nodo que se está actualizando. Veamos cómo funciona:

1. El método recibe dos parámetros:

   • g_decrement: la diferencia entre el valor g antiguo y el nuevo
   • new: el nodo que se acaba de actualizar

2. El proceso recursivo funciona así:

   def __update_g(self, g_decrement, new):
       # Itera sobre todos los elementos en la frontera
       for element in self.get_elements():
           # Verifica si el elemento tiene un padre y si ese padre es el nodo que acabamos de actualizar
           if element.parent and element.parent.state == new.state:
               # Actualiza el valor g del elemento
               element.g -= g_decrement
               # Recalcula el valor f (f = g + h)
               element.f = element.g + element.h
               # Llamada recursiva para actualizar los hijos de este elemento
               self.__update_g(g_decrement, element)

La recursión ocurre porque:

1. Primero actualiza los hijos directos del nodo modificado

2. Para cada hijo actualizado, llama recursivamente a __update_g() para actualizar sus propios hijos

3. Este proceso continúa hasta que se hayan actualizado todos los descendientes en la frontera

Ejercicio 1

Considérese el problema de encontrar un camino, en la situación representada en la figura, desde la posición $i$ hasta la posición $e$. El NPC (non-player character) puede moverse de forma horizontal y vertical, un solo cuadrado en cada movimiento (cada movimiento tiene coste uno). Las zonas sombreadas impiden el paso del NPC a través de ellas.

Consideraciones

• Para aquellos algoritmos en los que no es relevante el coste, el orden de los operadores (movimientos) es: arriba, abajo, izquierda, derecha.
• Si algún algoritmo no controla los ciclos, supondremos que existen mecanismos para eliminarlos.
• El coste del movimiento:
  • Vertical: 1.
  • Horizontal: 2.
• Para el algoritmo A se utilizará la distancia Manhattan como heurística:

$$ h(n) = {distancia \ horizontal} + {distancia \ vertical} $$

• En el ejemplo, la distancia Manhattan entre $i$ y $e$ es $4$.

Representación de la solución

• Resuelve el problema con cada uno de los algoritmos de búsqueda propuestos.
• Indica, para cada algoritmo, cuál se aplica para extraer los nodos de la frontera.
• Escribe:
  • La evolución del conjunto de nodos frontera.
  • El conjunto de nodos explorados durante el desarrollo del algoritmo.
  • La función coste y la heurística en los algoritmos que hagan uso de ellas.
• En la figura:
  • Nombra (enumera) los nodos según el orden en que son generados (incluidos en la frontera).
• Indica:
  • Cuándo la función test objetivo determina que el nodo chequeado es la solución.
  • La profundidad en la que se encuentra la solución.
• Razona y explica qué nodos y por qué conforman la solución.
• Representa:
  • El camino que conforma la solución (con una flecha en la figura).
  • El árbol de búsquedas.

Ejercicio 2

Preguntas específicas

1. La heurística utilizada en el algoritmo A, ¿es admisible? ¿Por qué?
   • ¿Podemos decir que el algoritmo es A*?

Consideraciones sobre la búsqueda A*

Figura 3.15 Evaluación de los algoritmos de búsquedas. Russell y Norvig (2022)

Epígrafe 3.5.4 "Satisficing search: Inadmissible heuristics and weighted A*". Russell y Norvig (2022)

Figura 3.15 Evaluación de los algoritmos de búsquedas. Russell y Norvig (2022)

Bibliografía

Russell, S. J., & Norvig, P. (2022). Artificial intelligence: a modern approach. Global edition. Pearson Education Limited.

---

Copilot Instructions - A* Search Algorithm

A continuación He incluido el análisis del proyecto realizado con copilot para explicar la arquitecura de la aplicación y las estructuras de datos usadas.

Project Overview

Purpose: Educational implementation of the A* pathfinding algorithm for grid-based state space search.

Architecture: The codebase decomposes the A* algorithm into core components:

• Node: Represents search tree nodes with state, g-cost, h-heuristic, and f-value (g+h)
• Frontier: Priority queue of unexplored nodes, sorted by f-value, with dynamic updates
• Reached: Set of already-explored nodes to prevent revisiting
• World: Static 6x5 grid world with obstacle cells ("-") and letter/symbol states
• Main a_star.py: Orchestrates search, calls heuristic, and formats output

Data Flow: Initial state → CLI args parse → a_star_search() initializes Frontier/Reached → loop: extract best node → if goal, return path; else expand successors with costs → output visualization

Key Patterns & Conventions

Grid World & Successor Generation

• States are single characters (letters A-Z, Y, Ñ, etc.) stored in World.WORLD 2D array
• Obstacles represented as "-" have no successors
• World.successor_function() applies four operators (up/down/left/right) with configurable costs:
  • Vertical (up/down): default cost 1, set via -v_c CLI arg → World.V_COST
  • Horizontal (left/right): default cost 2, set via -h_c CLI arg → World.H_COST
• Heuristic: Manhattan distance using actual grid positions, ignores obstacles

Node Equality & Hashing

• Node.__eq__() compares only state (not g/h), enabling frontier/reached lookups by state
• Node.__hash__() hashes state for Set membership; ensures set semantics on state uniqueness
• Node.__lt__() compares g-costs; used in Frontier updates when better path found

Set Implementation (Collection Pattern)

• Set base class uses OrderedDict to maintain insertion order while enabling O(1) lookups
• Frontier and Reached inherit from Set and add domain-specific methods:
  • Frontier.get_best_node(): extracts min by f-value and removes from set
  • Frontier.update(): replaces node if new g-cost is better; cascades g-decrement to descendants
  • Reached.get_nodes(): returns list of explored nodes for output

Frontier Update Strategy

When a better path to a node is found:

1. Replace old node with new (lower g-cost) node in frontier
2. Propagate g-decrement to all descendants in frontier via __update_g() recursive call
3. Updates f-values accordingly (f = g + h)

This maintains consistent g-costs across the frontier tree structure.

Developer Workflows

Running Search

# Basic search: Z (bottom-left) to N (middle-right)
python a_star.py Z N

# Custom costs: vertical=2, horizontal=3
python a_star.py -v_c 2 -h_c 3 Z N

# Via uv package manager
uv run a_star.py Z N

Testing

# Run all tests (uses pytest)
python -m pytest test/

# Run specific test file
python -m pytest test/test_a_star.py -v

Environment Setup

# Install runtime dependencies only
pip install -r requirements.txt

# Install with dev/test dependencies (using uv)
uv sync
uv sync --group lint

Code Quality

• Linter: ruff (configured via pyproject.toml)
• Python version: ≥3.11
• Output includes colored ASCII visualization and matplotlib plot

Important Notes for AI Agents

1. State Representation: States are strings (single character). Grid lookup via World.find_position(state) returns (row, col) tuple—required for heuristic calculation.

2. Frontier State Equality: Two nodes with same state are considered equal; frontier operations use this semantic, not object identity.

3. Test Imports: Tests import directly from a_star.py (not a package module), so they expect root-level functions. Preserve import paths when modifying function signatures.

4. Output Integration: problem_repr() expects:

   • solution: list of states forming path
   • explored.get_elements(): list of Node objects for coloring
   • frontier.get_elements(): list of Node objects for coloring
   • Uses Colors enum from cli_colors.py for terminal output

5. Algorithm Termination: Returns None if no path exists (unreachable goal), or tuple (frontier, reached, path) if found.