I. Introducción.

 En este proyecto, al igual que en el proyecto de medio término, hemos desarrollado un sistema para coloreo grafos, un problema NP-duro [Garey-Johnson 1979, Littman, 1997]. Anteriormente, el sistema sólo podía colorear grafos planos a través del método de Davis-Putnam y ahora hemos modificado el programa para colorear grafos de cualquier tipo. Este problema es más complejo puesto que se requieren más recursos de cómputo para calcular un número cromático ? mayor que cuatro. Por esta razón, para hallar una solución en un tiempo óptimo, hemos agregado un algoritmo no determinístico: Simulated Annealing (SA) (recocido simulado) que nos ayuda a acercarnos al número cromático ? que buscamos. Posteriormente, el método completo de Davis & Putnam buscará mejorar la solución entregada por SA para disminuir ? a través de particiones binarias.
 
 

II. ¿Por qué usar un método incompleto?.

 Para colorear un grafo dado, es necesario tomar en cuenta 2 atributos: número de vértices (V) y el número de aristas (L), además de las restricciones inherentes a la coloración: Dos vértices unidos por una misma arista, no pueden tener el mismo color.

 Cuando representamos ésta información en forma clausular usando el formato de la forma normal conjuntiva (FNC), obtenemos un número considerable de cláusulas. Por ejemplo, para un grafo completo de 7 vértices (42 aristas) se requieren 308 cláusulas con 98 literales. Si aplicamos el método completo de Davis & Putnam para adivinar el número cromático ? en varias iteraciones, entonces será demasiado tiempo y recursos invertidos para encontrarlo. En otras palabras, resulta demasiado ineficiente y costoso.

  Por esta razón, necesitamos un algoritmo incompleto que realice ésta ardua tarea. Hemos escogido Simulated Annealing basándonos en pruebas realizadas por [Chams, Hertz, 1987] y [Johnson, Aragon, McGeoch,1991] obteniendo buenos resultados.
 
  Como método incompleto, SA obtiene o se acerca al número cromático deseado de una manera más rápida que D&P. Como no sabemos si en realidad el ?’ obtenido por SA es el correcto, D&P intenta mejorarlo, o en el peor de los casos, llegar al mismo ?’ obtenido por SA. De esta manera, es probable que D&P trabaje con menos cláusulas y literales (pues hay menos colores que probar). Finalmente, es D&P quien devuelve el número cromático correcto y colorea el grafo.
 

III. Desarrollo.

El sistema está formado básicamente de las siguientes partes:

•  Representación del grafo.
•  Algoritmo Simulated Annealing
•  Generación y Representación de la Forma Normal Conjuntiva.
•  Particiones binarias con Davis&Putnam.

III.1 Representación del grafo.

La forma en que almacenamos un grafo en la memoria es a través de una matriz de adyacencia, en la cual se registran todas las incidencias entre los vértices. Hemos adaptado a dicha matriz para que solo almacene una dirección de dicha adyacencia, es decir, si el vértice 1 es adyacente al vértice 2, solo aparece la adyacencia de 1 a 2 pero no de 2 a 1. El siguiente es un ejemplo de dicha matriz:

III.2 Simulated Annealing

Tomando las siguientes consideraciones:

Dada una coloración f, c(f) denota el numero de aristas "malas" (u,v) tales que f(u)=f(v). Nosotros escogeremos aleatoriamente para cara vértice v en V un color je{1..K} y colorearemos el vértice con el color j escogido. Nosotros escogemos la coloración f', si c(f') es menor o igual a c(f). Si c(f`) > c(f), nosotros escogemos la coloracion f' con la probabilidad de exp((c(f)-c(f'))/T) y asignamos a f (la coloracion anterior) la probabilidad de 1-exp((c(f)-c(f'))/T).

Una vez implementado se hicieron algunas modificaciones que sobre pruebas con grafos duros (grafos para los cuales existen pocas coloraciones posibles) se realizaron.

1. Las permutaciones que se realizan normalmente sobre alguna variable cualquiera de f, se decidió que se permutarian solo las variables que estuvieran mal, deacuerdo a la evalución de la variable de costo. Y esto se decidió porque nos dimos cuenta que el algoritmo tardaba mas en encontrar la solución, si después de evaluada f, se escogia cualquier variable para permutar, y no una que especificamente era considerada mala.

2. Se observo, que en algunos casos, el algoritmo perdia mucho tiempo en intentos de "mejorar" una coloración inicial dada con permutaciones de las variables malas, y se decidio hacer un algoritmo Simulated Anneling "desesperado", cuando se llega a una temperatura baja, en nuestro caso 0.5 grados y no se ha alcanzado la solución; entonces nuevamente se propone una coloración aleatoria y se reinicializa la temperatura, si despues de k nuevas coloraciones no se encuentra, entonces se decide que no se puede colorear con el numero de colores propuesto al inicio.

3. El esquema de enfriamiento se escogio en base a ensayos del algoritmo.
 

III.3 Reducción a la Forma Normal Conjuntiva

Para generar reducir el grafo a una fórmula FNC, lo hacemos a través de 3 partes:
a) Generación de las cláusulas que especifican que cada vértice tiene al menos un color:

{V11 v V12 v . . . v V1c}
{V21 v V22 v . . . v V2c}
     .
     .
{Vn1 v Vn2 v . . . v Vnc}

 donde Vij es el vértice i con el color j.
 
b) Generación de las cláusulas que especifican que cada vértice sólo tiene un color:

{~V11 v ~V12 v . . . v ~V1c}
{~V21 v ~V22 v . . . v ~V2c}
     .
     .
{~Vn1 v ~Vn2 v . . . v ~Vnc}

c) Generación de las cláusulas que especifican que cada par de vértices unidos por la misma arista NO deben tener el mismo color:

for (y=0;y<V;y++)            /* busca adyacencias*/
      for (x=y+1; x< V; x++)
            if (A[y,x]=1) {         /* hay adyacencia */
                 siguiente=0
                 for w=k to k+C-1 {
                       M[w,(y-1)*C+siguiente] = 0
                       M[w,(x-1)*C+siguiente] = 0
                       siguiente ++;
                 }
                 k+=C
            } /* if */

Como se puede apreciar en los incisos anteriores, el número de cláusulas que se general es:
No. de vértices * 2 + Número de aristas * Número de colores
De tal forma que, para un grafo con 4 vértices, 6 aristas y 4 colores, tendremos un total de 32 cláusulas.
 En la matriz, estas cláusulas están representadas en renglones, mientras que las columnas representan a las variables o proposiciones.
 

III.4 Algoritmo de Davis&Putnam.

La implementación de este algoritmo la hicimos en forma recursiva, definiendo 3 funciones en C:

· int *davisputnam(int mFNC[][],int vred[])
· void sustituye(int TF,int x,int mFNC[][])
· void reduce(int mFNC[][],int vred[])

La función davisputnam() es quien se encarga de llamar a las demás funciones y quien escoge una variable aleatoriamente para asignarle algún valor de verdad cuando no hay cláusulas unitarias y no se puede realizar la propagación. Cuando falla la asignación de verdad, entonces intenta asignarle el complemento de dicho valor e intenta de nuevo solucionar. Si ninguno de los valores funciona, significa que la cláusula es insatisfactible.

La función sustituye() se encarga de hacer la propagación de una literal sobre todas las cláusulas de la fórmula, eliminando cláusulas donde aparece la literal en forma positiva y con valor TRUE, así como eliminando la literal de cláusulas donde aparece en forma negada. Por tanto, puede eliminar cláusulas o literales en cláusulas.

La función reduce() es quien se encarga de buscar cláusulas de una literal, con el fin de propagar a través de sustituye().
 
 

CONCLUSIONES.
 
 Como hemos visto, la implementación de un método completo para soluciónar un problema NP-duro es, sin duda, una buena opción. La deficiencia que presenta se refleja en los recursos invertidos. Por esta razón, cuando necesitamos obtener el número cromático de un grafo, no es conveniente utilizar dicho método, sino que, usar un método incompleto es más favorable ya que  requiere menos recursos. Esto es lo que hace Simulated Annealing. El problema que queda en el aire es saber si el resultado ofrecido por SA es el mejor. Así que D&P intentará mejorarlo (pero ahora con más información), devolviendo el número cromático correcto.
 
 

REFERENCIAS

M.Garey, D.Johnson. Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman New York, 1979.

Chams, M., A. Hertz & D. de Werra, "Some experiments with simulated annealing for coloring graphs", Eur. J. Op. Res. 32, pp. 260-266, 1987.

Johnson, D., C. R.Aragon, L. A. McGeoch & C. Schevon, "Optimization by Simulated Annealing: an Experimental Evaluation – PartII (Graph Coloring and Number Partitioning)" Opns. Res. 39:3, pp.378-406, 1991.