Laboratorio 5

Problema de Satisfaccion de Restricciones

• Implementar un algoritmo para PSR que utilice heurística de Grado, heurística MVR y Forward Checking para el Problema de Coloracion de Mapas

Implementamos el Problema de Satisfacción de Restricciones, para el Problema de Coloración de Mapas, mediante los siguientes algoritmos:

• Algoritmo con Heurística MVR
  
• Algoritmo con Heurística de Grado
• Algoritmo con Forward Checking
• Algoritmo con Heurística MVR y Forward Checking

Tenemos a continuación el caso visto en clase:

• Ciudades: WA, NT, SA, Q, NSW, V, T
  
• Grafo de Adyacencia:

• Colores: rojo, azul, verde

Y los respectivos resultados obtenidos luego de utilizar cada uno de los algoritmos ya mencionados:

Luego tambien lo hemos aplicado para el siguiente caso:

• Ciudades: A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z

• Grafo de Adyacencia:

• Colores: rojo, azul, verde, amarillo

Y donde los resultados fueron, para el caso del:

• MVR: (A . rojo) (B . azul) (C . verde) (G . rojo) (F . azul) (K . verde) (J . rojo) (L . amarillo) (E . verde) (D . rojo) (I . azul) (M . amarillo) (H . verde) (N . azul) (O . rojo) (P . verde) (Q . amarillo) (R . azul) (S . rojo) (T . verde) (U . rojo) (W . azul) (V . verde) (X . azul) (Y . rojo)
  (Z . verde)

• Grado: (B . rojo) (I . rojo) (J . azul) (M . verde) (E . amarillo) (K . verde) (N . rojo) (O . azul) (P . amarillo) (Q . verde) (R . rojo) (S . azul) (T . verde) (C . azul) (D . azul) (F . rojo)
  (G . amarillo) (L . amarillo) (U . azul) (X . rojo) (Y . azul) (H . amarillo) (W . rojo) (A . verde)
  (V . verde) (Z . verde)

• Forward Checking: (A . rojo) (B . azul) (C . verde) (D . rojo) (E . verde) (F . rojo) (G . amarillo) (H . azul) (I . amarillo) (J . rojo) (K . verde) (L . azul) (M . azul) (N . verde) (O . rojo) (P . amarillo) (Q . verde) (R . azul) (S . rojo) (T . verde) (U . rojo) (V . azul) (W . amarillo) (X . azul) (Y . rojo)(Z . verde)
  

• MVR + FC: (A . rojo) (B . azul) (C . verde) (G . rojo) (F . azul) (K . verde) (J . rojo) (L . amarillo) (E . verde) (D . rojo) (I . azul) (M . amarillo) (H . verde) (N . azul) (O . rojo)
  (P . verde) (Q . amarillo) (R . azul) (S . rojo) (T . verde) (U . rojo) (W . azul) (V . verde)
  (X . azul) (Y . rojo) (Z . verde)
  

Veamos la implementación:

Escogemos por ejemplo la opción MVR y tenemos en la parte superior izquierda la conexión, parte inferior resultado luego de colorear, y lado derecho respuesta de las asignaciones hechas:

Escogemos la opción Grado:

Adjuntamos nuestras prueba aquí.