Temas importantes para el desarrollo de
la segunda parte del TPE

Contenedores asociativos ordenados

Clase comparador

Conceptos de Búsqueda Heurística

Algoritmo A*

Aclaraciones para la entrega
Laboratorio
Análisis y Diseño de Algoritmos 2
Contenedores asociativos ordenados

Por ejemplo:


Contenedores asociativos: map y set
Características

Usan una relación de orden entre las claves.

Dos claves son equivalentes cuando ninguna es menor que
la otra.

Garantiza que la complejidad de la mayoría de las
operaciones nunca es mayor del orden logaritmico.

Garantiza que los elementos están ordenados de forma
ascendente de acuerdo a las claves.
Laboratorio
Análisis y Diseño de Algoritmos 2
Contenedores asociativos ordenados

Es necesario saber como comparar dos claves. Para esto se
utiliza el parámetro comparador.
Laboratorio
Análisis y Diseño de Algoritmos 2
Comparador

Para tipos de datos básicos:




Se utiliza el comparador por defecto Less<Key>
Es un objeto función de tipo binario.
Define el operador (TipoU t1,TipoU t2), el cual determina si
t1 es menor que t2.
Para tipos de datos definidos por el usuario:


Es necesario definir un comparador
El comparador debe contener el operador (TipoU,TipoU).
Laboratorio
Análisis y Diseño de Algoritmos 2
Comparador

Ejemplo:
class Comparador {
public:
bool operator()(const TipoU & s1, const TipoU & s2) const {
return s1< s2;
}
};
map<TipoU, int, Comparador> mapa;
class TipoU {
…
bool operator < (TipoU t1) const {
…
}
…
Laboratorio
Análisis y Diseño de Algoritmos 2
Búsqueda

Espacio de búsqueda
mover derecha
mover abajo
mover abajo
mover derecha
mover arriba
Laboratorio
Análisis y Diseño de Algoritmos 2
mover derecha
Búsqueda heurística



Tanto DFS y BFS son algoritmos de búsqueda por “fuerza
bruta”, ya que no requieren ningún conocimiento específico del
dominio.
Sin embargo, existen problemas donde el espacio de búsqueda
es muy grande, y es necesario añadir a los algoritmos de
búsqueda conocimiento del dominio para mejorar la eficiencia.
Esto da lugar a los algoritmos de búsqueda “heurística”.
Las “funciones de evaluación heurística” (o simplemente
heurística) nos permiten estimar el costo del camino óptimo
entre dos estados. A la hora de diseñar una función heurística
se debe hacer un compromiso entre:
 El costo computacional de cada evaluación
 La calidad de la estimación retornada
Laboratorio
Análisis y Diseño de Algoritmos 2
Heurística



En general, las soluciones encontradas con los algoritmos de
búsqueda heurística son sub-óptimas.
Existe un tipo de función heurística llamadas “admisibles”. Una
función de evaluación heurística admisible nunca asigna a un
estado un valor heurístico mayor al costo o distancia real.
Para muchos algoritmos de búsqueda heurística (como el A*,
por ejemplo), está garantizado que las soluciones encontradas
serán las óptimas siempre que se utilicen heurśiticas
admisibles.
Heurística
Un ejemplo
...
(x, y)
...
(goalx, goaly)
h = 2,8
Función Heurística h
Distancia Euclídea
h=2
 x  goal x 2   y  goal y 2
...
...
...
Heurística
Otro ejemplo
...
Bloqueado
...
h = 2,8
Función Heurística h
Distancia Euclídea
h=2
 x  goal x 2   y  goal y 2
...
...
Heurística
Se definen los siguientes costos:
f(n)
es el costo heurístico asociado a un estado n.
g(n) es el costo para alcanzar un estado n a partir del
estado inicial.
h(n) es el costo heurístico para alcanzar un objetivo desde
el estado n.
La relación que existe entre los costos es:
f(n) = g(n) + h(n)
Heurística
Estado
inicial
f = g + h = 5,23
1
1
1
h = 2,23
Estado
Evaluado
g=3
Estado
Objetivo
A*




A* expande los nodos en el orden de sus valores heurísticos
f(n).
El algoritmo mantine dos estructuras:

Lista Abierta: con nodos generados sin expandir

Lista Cerrada: con los nodos que ya han sido expandidos
En cada ciclo el algoritmo lleva a cabo los siguientes pasos:

Saca el nodo de la Lista Abierta con el menor valor f(n)

Expande el nodo, generando todos sus hijos, les aplica la
función heurística y los coloca la Lista Abierta en el orden de
su valor heurístico.

Coloca el nodo en la Lista Cerrada.
El algoritmo termina cuando se elije el estado objetivo para la
expansión.
Trabajo práctico Especial 2º parte

Se debe almacenar la siguiente información:


para cada esquina:
 Dos coordenadas que indiquen su posición relativa en el
plano.
para cada cuadra:
 El nombre de la calle,
 El estado de la calle
Laboratorio
Análisis y Diseño de Algoritmos 2
Requisitos de la entrega

Implementación:






La clase grafo con las correcciones solicitadas en la primer
entrega.
Los algoritmos BFS-Forest, DFS-Forest y Puntos de
Articulación, funcionando correctamente con el grafo
parametrizado con esquinas y calles.
Las funciones necesarias para cargar y guardar el grafo en
un archivo.
El algoritmo A* que resuelva el problema solicitado.
Una interfaz gráfica que permita:
 Editar el grafo de la ciudad (Agregar y Eliminar Vertices y
Arcos, etc).
 Guardar y cargar el grafo del archivo.
Permitir ejecutar y ver el resultado de cada uno de los
algoritmos.
Laboratorio
Análisis y Diseño de Algoritmos 2
Requisitos de la entrega

Informe:



Debe incluir las correcciones solicitadas en la primer
entrega del trabajo, junto con el informe realizado para dicha
entrega.
Descripción del algoritmo A*, incluyendo una descripción de
la implementación realizada y el cálculo de la complejidad.
Breve descripción de los pasos necesarios para realizar las
operaciones básicas de edición del grafo y ejecución de los
algoritmos, utilizando la interfaz gráfica desarrollada.
Laboratorio
Análisis y Diseño de Algoritmos 2
Fechas

Fecha de entrega:
19 y 20 de noviembre

Defensa:
26 y 27 de noviembre
Laboratorio
Análisis y Diseño de Algoritmos 2
Descargar

Biblioteca estándar de templates de C++ Standard Template Libra