Se implemento el Algoritmo Simulated Anneling basándose en el siguiente algoritmo:

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 j e{1,2,3} 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 coloración f' con la probabilidad de
exp((c(f)-c(f'))/T) y asignamos a f (la coloración 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 decidio que se permutarían solo las variables que estuvieran mal, deacuerdo a la evaluación de la variable de costo. Y esto se decidío porque nos dimos cuenta que el algoritmo tardaba mas en encontrar la solución, si después de evaluada f, se escogía cualquier variable para permutar, y no una que específicamente era considerada mala.

2. Se observo, que en algunos casos, el algoritmo perdía mucho tiempo en intentos de "mejorar" una coloración inicial dada con permutaciones de las variables malas, y se decidío 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 después de k nuevas coloraciones no se encuentra, entonces se decide que no se puede colorear con el numero de colores propuesto al inicio.
 

Casos de Prueba

Inicialmente hicimos pruebas con un "grafo duro" que solo puede ser coloreado con 5 colores y se encontró los colores y el numero cromático satisfactoriamente:

Posteriormente se probo con algunos grafos sencillos y la respuesta fue casi instantánea.
 
 

Finalmente se probo con este grafo, y el algoritmo llego a la conclusion de que solo se puede colorear con 5 colores.

Conclusiones

El algoritmo Simulated Anneling, funciona muy bien el contexto de coloración de grafos planos, aunque deben ser hechas algunas adaptaciones para que el algoritmo funcione mejor. Solo en algunos casos de grafos dificiles, el algoritmo no pudo encontrar solución, aun sabiendo nosotros que si la había. Es por eso que estamos en el camino de hacerle algunas mejoras para que pueda encontrar solución siempre que la haya.