Búscalo aquí:

Problemas de Satisfacción de Restricciones: Coloración de Mapas

Un problema de satisfacción de restricciones es un tipo especial de problemas que satisfacen algunas propiedades adicionales las cuales pueden involucrar una o varias variables al mismo tiempo. Muchos de los problemas que se plantean en Inteligencia Artificial pueden formalizarse como un problema de satisfacción de restricciones (PSR) también llamados problemas de satisfacción de condiciones (CSP). En este post se mostrará los resultados de la aplicación de algunas técnicas para la solución de problemas de satisfacción de restricciones para el coloreado de mapas (grafos).


De esta manera, podemos definir formalmente a un problema de satisfacción de restricciones (PSR/CSP) como:

  • Un conjunto finito de variables X1, ...Xn
  • Un conjunto finito de Dominios Di asociados a cada variable Xi, especificando los posibles valores que puede tomar.
  • Un conjunto finito de restricciones C1,...,Cm que definen una serie de propiedades que deben verificar los valores asignados a las variables

  • Una solución al problema es la asignación de valores a las variables {X1 = v1, ...., Xn = vn} tal que vi pertenece al conjunto de dominios Di y se verifican las restricciones.

    Esta formulación permite una representación simple del problema, y el uso de heurísticas de propósito general, independientes del problema al que se desee aplicar.

    Una de las aplicaciones de los problemas de satisfacción de restricciones es el coloreado de mapas. Este problema consiste en colorear un mapa con 4 colores como minimo, donde, cada región correspondiente al mapa debe tener un color distinto a cualquiera de sus vecinos próximos (teorema de los 4 colores); por ejemplo se podría colorear el mapa de los departamentos o regiones políticas de un país usando únicamente cuatro colores.

    El Teorema de los 4 colores esta basado en la Teoría de Grafos por lo tanto es totalmente formal.

    Una de las técnicas más utilizadas es usando el backtracking (algoritmo voraz), la cual se cuenta entre una de las técnicas más sencillas para dar solución a este problema bajo el riesgo del coste computacional al dar muchas 'vueltas atrás' innecesarias hasta dar con la solución final.


    Para evitar el problema que genera la técnica del backtracking es que se hace uso de algunas heurísticas una de ellas es la heurística de grado que consiste en ir escogiendo la variable con más restricciones e ir dándoles solución

    Otra heurística ampliamente usada es la heurística del valor más restrictivo (MVR) que consiste en ir escogiendo las variables con menos valores legales e ir dándoles solución.

    Estas heurísticas pueden ser implementadas junto a algoritmos netos de Inteligencia Artificial como el algoritmo de forward checking y poder obtener mejores resultados.


    Para mayores detalles de la implementación de estos algoritmos para la satisfacción de restrcciones en el coloreado de mapas pueden ir AQUI y AQUI.

    Los gráficos mostrados son resultados de la implementación realizada en Java.

    Quieres leer más post como éste???...suscribete aquí!!!

    3 comentarios:

    1. hola dime tienes la aplicacion de coloreas mapas el de la imagen...

      ResponderEliminar
    2. Hola Sr Valverde seria tan amable de enviarme su codigo para examinarlo y aprender mas? sobre esto de colorear mapas con PSR. mi mail es Solman28@gmail.com

      ResponderEliminar
    3. Mayores detalles lo pueden encontrar en la web enm la que se trabajo esta aplicación: http://joshi.ueuo.com/laboratorio.php?&idart=25

      ResponderEliminar

    Bienvenido a jcGeorge's Blog!!!

    Por favor deja tu comentario, consulta o sugerencia, procura mantener habilitado tu perfil de Blogger o deja un enlace a tu blog o web.

    Gracias por leer este blog!!!

    Related Posts Plugin for WordPress, Blogger...