lunes, 14 de julio de 2008

Problema de Satisfacción de Restricciones (PSR)

Para conocer un poco sobre PSR puedes ver las diapositivas del curso aquí

En esta oportunidad hemos implementado un algoritmo Algoritmo para PSR que utiliza heurística de grado, heurística MVR y forward checking para el problema de coloración de mapas.

El problema de coloración de mapas ha sido simplificado a colorear un grafo, donde los nodos representan a los lugares del mapa y los arcos representan a las restricciones.
Inicialmente hemos usado un dominio de tres colores, lo que traía como consecuencia de que existan soluciones inconsistentes y por tanto el grafo no era coloreado. Debido a este problema se considero usar un dominio con cuatro colores, por la existencia del teorema de los cuatro colores, para el coloreado de grafos, el cual dice que todo grafo puede ser coloreado con a lo mas 4 colores.
Aplicando este cambio donde el dominio es ahora cuatro colores, entonces nuestro programa debe colorear cualquier grafo, es decir la solución siempre es consistente


A continuación se muestra algunas imagenes del programa.
En este caso el coloreado se realiza con un dominio de 3 colores, la solución es consistente.

Al igual que en el caso anterior el dominio es de 3 colores, pero la solución no se encuentra, es decir es inconsistente.

En este caso se usa un dominio de 4 colores, como se dijo antes el grafo debe ser coloreado( encuenrta solución)










1 comentarios:

Dj Osram dijo...

Estaria de pelos que compartieras el codigo de tu programa para la solucion de PSR (Teorema De Los 4 Colores)