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
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.
Al igual que en el caso anterior el dominio es de 3 colores, pero la solución no se encuentra, es decir es inconsistente.
1 comentarios:
Estaria de pelos que compartieras el codigo de tu programa para la solucion de PSR (Teorema De Los 4 Colores)
Publicar un comentario