headerphoto

Algorytmy z powrotami - Przykładowe zastosowania algorytmów z powrotami

Kolorowanie grafu

Problem kolorowania grafu polega na znalezieniu wszystkich sposobów na pokolorowanie grafu nieskierowanego przy wykorzystaniu najmniejszej liczby kolorów tak, aby sąsiadujące ze sobą wierzchołki miały różne kolory. Powszechnym zastosowaniem kolorowania grafów jest np. kolorowanie map geograficznych. Mapę taką można w łatwy sposób przedstawić za pomocą grafu. Każdy region na mapie reprezentowany jest przez wierzchołek, jeżeli jeden region sąsiaduje z drugim, to rysujemy krawędź między odpowiadającymi im wierzchołkami.

Algorytm z powrotami tworzy abstrakcyjne drzewo przestrzeni stanów. Węzłom w drzewie przypisane są numery dostępnych kolorów, zaś każdemu poziomowi odpowiada jeden z wierzchołków do pokolorowania. Algorytm przechodząc w głąb drzewa, sprawdza czy wierzchołek sąsiadujący z aktualnie analizowanym wierzchołkiem został już pokolorowany danym kolorem. Jeśli tak, to uznaje dany węzeł (kolor) za nieobiecujący, cofa się i próbuje pokolorować wierzchołek innym kolorem.

Zadaniem algorytmu z powrotami jest znalezienie wszystkich sposobów pokolorowania wierzchołków w grafie za pomocą danej liczby kolorów.