Algoritmos resolución de problemas mediante búsquedas

Ejercicios módulo Modelos de Intelixencia Artificial

Instalación y Ejecución con uv

Instalación

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

Crea y activa un entorno virtual con uv:

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

Instala las dependencias del proyecto declaradas en pyproject.toml

uv sync

Recueda que puedes emplear la interfaz de pip:

pip install -r requirements.txt

Instala el linter ruff:

uv sync --group lint

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

Búsqueda básica de Z a N:

python a_star.py Z N

uv run a_star.py Z N

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

python3 a_star.py N J

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:

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
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:

Primero actualiza los hijos directos del nodo modificado
Para cada hijo actualizado, llama recursivamente a __update_g() para actualizar sus propios hijos
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

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:

Replace old node with new (lower g-cost) node in frontier
Propagate g-decrement to all descendants in frontier via __update_g() recursive call
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

State Representation: States are strings (single character). Grid lookup via World.find_position(state) returns (row, col) tuple—required for heuristic calculation.
Frontier State Equality: Two nodes with same state are considered equal; frontier operations use this semantic, not object identity.
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.
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
Algorithm Termination: Returns None if no path exists (unreachable goal), or tuple (frontier, reached, path) if found.

FilesExpand file tree

README.md

Latest commit

History