Symulowane Wyżarzanie i Tabu Search na przykładzie kolorowania grafów

Witam,

Doszedłem już chyba do końca internetu. Przeczytałem wiele artykułów na wyżej wymieniony temat. Nawet zainwestowałem trochę w ebooki.

Niestety nie do końca rozumiem pewne aspekty:

1. Jak określić sąsiedztwo rozwiązania N(x)
2. Jak określić zbiór możliwych rozwiązań
3. Jak obliczyć funkcję kosztu
4. W przypadku zmiany koloru wierzchołka, jak dokonywać naprawy innych wierzchołków.

Proszę o pomoc
Pozdrawiam
Darek

1. Jak masz pokolorowany graf V to sąsiedztwem będzie ten sam graf V, tylko że z inaczej pokolorowanymi wierzchołkami (np. zmieniony kolor jednego wierzchołka, lub kilku wierzchołków).
2. Zbiór możliwych rozwiązań to wszystkie możliwe pokolorowania grafu. W klasycznym problemie kolorowania grafu rozwiązaniami są grafy z tak pokolorowanymi wierzchołkami, że żadne dwa sąsiadujące wierzchołki nie mają tego samego koloru. Generalnie w implementacji można przyjąc dwa podejścia: albo generujesz rozwiązania tylko dopuszczalne, albo akceptujesz rozwiązania niedopuszczalne w nadziei, że dojdziesz w końcu do tych dopuszczalnych.
3. Zależy jak zdefiniujesz funkcję kosztu. Można np. ją zdefiniować tak, że dla każdych dwóch sąsiadujących wierzchołków, które mają ten sam kolor dajesz punkt karny. Suma punktów karnych jest funkcją kosztu. Tak więc dążysz aby funkcja kosztu była równa 0. Jak ją obliczyć? Przechodzisz się po grafie algorytmem takim jak BFS i zliczasz, które sąsiadujące wierzchołki mają ten sam kolor. Ewentualnie grupujesz wierzchołki o tym samym kolorze i patrzysz, czy któreś ze sobą sąsiadują. Możesz też obliczać taką funkcję inkrementalnie, tzn. dla sąsiadów rozwiązania odpowiednio modyfikować funkcję tylko dla wierzchołków, którch kolor się zmienił.
4. Najprościej możesz chodzić BFS i zmieniać kolory wierchołków dopóki pokolorowanie nie będzie prawidłowe lub dopóki nie przejdziesz wszystkich wierzchołków.

Generalnie to jest temat rzeka, całe ksiązki pisze się o tym problemie. Jedna z nich to "Optymalizacja dyskretna. Metody i modele kolorowania grafów", dosyć przystępnie napisana. Poszukaj przykładowych kodów na necie, jest tego sporo.

Witam szukam przykładu symulowanego wyżarzania kolorowania grafów. Może ktoś mi pomoże i rozpisze jakiś przykład albo ktoś wie gdzie znaleźć jakiś przykład.