Problem Kolorowania Wierzcholkow Grafu.

[MeHow]

Witam, zaczne od mojego problemu. Otoz potrzebuje algorytm, ktory kolorowalby wierzcholki grafow, tak zeby zadne wierzcholki polaczone krawdzia nie mialy tej samej barwy. Problem nazywa sie tez problemem kolorowania map. Algorytm musi byc optymalny, wiem ze jest to NPC, dlatego sprawia mi taki problem, guglalem, ale na polskich stronach sa tylko algorytmy heurystyczne, natomiast gdy odnalazlem upragniony algorytm na stronie anglojezycznej, wstyd sie przyznac, ale nie jestem w stanie go sobie przetlumaczyc. Oto link: http://www.geocities.com/dharwadker/vertex_coloring/ . Algorytm rozpoczyna sie od podpunktu 3.1, a wczesniej znajduja sie definicje w nim przydatne. Czy ktos bylby tak mily i pomogl mi go zrozumiec albo podal jakies informacje, gdzie moge znalezc po polsku algorytm rozwiazujacy moj problem?

 

Przepraszam za zamieszanie.

 

Pozdrawiam

mehow

[Haquim]

http://www.geocities.com/dharwadker/vertex_coloring/ . Algorytm rozpoczyna sie od podpunktu 3.1, a wczesniej znajduja sie definicje w nim przydatne. Czy ktos bylby tak mily i pomogl mi go zrozumiec albo podal jakies informacje, gdzie moge znalezc po polsku algorytm rozwiazujacy moj problem?

Przepraszam za zamieszanie.

Pozdrawiam

mehow

algorytm zbiorów rozłącznych do niczego dobrego nie prowadzi :) ponieważ także ten probelm (wyznaczania zbiorów rozłącnzych ) jest NP-zupełny .

http://en.wikipedia.org/wiki/NP-complete#Example_problems

http://www.cs.auc.dk/~luca/FS2/NP-completeness.html

 

PS: Jest nawet matematyczny dowód na to że każdy problem NP-zupełny można przekształcić w inny co daje w wyniku Tezę że jeśli ktoś opracuje efektywny algorytm dla jakiegokolwiek problemu NP-zupełnego opracuje dla wszystkich .Jak na razie nie ma algorytmów "rozsądnych" dla problemów NP :)

 

Więc zastanów się nad jakimś algorytmem przybliżonym .

Edytowane 29 Października 2006 przez Haquim

[MeHow]

Niestety algorytm nie moze byc przyblizony :/ , musi podawac dokladny wynik. Tak wiec, czy zna ktos algorytm? Nie musi byc rozsadny, chodzi o to, zeby dawal wynik dla malych grafow, ale dokladny.

[Haquim]

Niestety algorytm nie moze byc przyblizony :/ , musi podawac dokladny wynik. Tak wiec, czy zna ktos algorytm? Nie musi byc rozsadny, chodzi o to, zeby dawal wynik dla malych grafow, ale dokladny.

Algorytm jest prosty jak drut , trzeba zastosować backtracking (technikę powrotów)

Opis algorytmu :

http://www.algorytm.org/index.php?option=c...5&Itemid=28

Materiały :

http://sequoia.ict.pwr.wroc.pl/~witold/aiuwr/search_s.pdf

http://www.asdpb.republika.pl/wyk58.pdf

 

W Cormenie też powinien być opis.

Powodzenia

[MeHow]

Witaj, przepraszam, ze dopiero teraz odpisuje. Powiedz mi jednej rzeczy. Czy jestes pewny, ze algorytm ten jest optymalny? Tzn czy pomaluje graf przy najmniejszej liczbie potrzebnych kolorow?

 

Pozdrawiam

mehow

[Haquim]

Witaj, przepraszam, ze dopiero teraz odpisuje. Powiedz mi jednej rzeczy. Czy jestes pewny, ze algorytm ten jest optymalny? Tzn czy pomaluje graf przy najmniejszej liczbie potrzebnych kolorow?

Pozdrawiam

mehow

Jest optymalny tylko jest nierozsądny obliczeniowo więc przy większej liczbie mozesz sobie poczekać że hoho .

[MeHow]

Ja to wiem :) , niestety taki musi byc.

 

A powiedz mi, czy wiesz moze jaka jest jego zlozonosc obliczeniowa dokladnie?

[Haquim]

Ja to wiem :) , niestety taki musi byc.

A powiedz mi, czy wiesz moze jaka jest jego zlozonosc obliczeniowa dokladnie?

n!*koszt wyboru kolejnego wierzhołka do pokolorowania - bo tyle masz różnych kolejności w których możesz dobierać wierchołki do pokolorowania

[MeHow]

Witaj.

 

Nastal czas zastosowania algorytmu i gleboko sie zastanawiam, gdzie jest cale to powracanie, wydaje mi sie, ze ten algorytm moze sie pomylic.

 

Otoz mamy taki graf

 

A-B-C-D-E //zwykle 5 wierzcholkow polaczonych ze soba w liste, dzialam tak jak algorytm.

 

wybieram peirwszy wierzcholek A, ladnie mi go maluje kolorem 1, potem zalozmy, ze kolejny niepokolorowany wierzcholek ze zbioru to D, wiec maluje go takze na 1. Nastepne iteracje dla B C i E nie spelniaja warunku i ich nie koloruje, przechodze do nastepnej iteracji dla koloru = 2. Wybieram wierzcholek B, koloruje, potem E, koloruje... i klops. Zapowiada sie, ze algorytm sobie nie poradzil z tak prostym grafem.

[Haquim]

 

1)Tak wykonałeś 1 iterację i otrzymałeś 1 z możliwych pokolorowań

2)Teraz powinieneś wrócić i sprawdzić inną kolejność

 

BTW: Kolejne wierchołki ze zbioru wierzchołków pokolorowanych dobiera się zpośród sąsiadów już pokolorowanych wierzchołków.(Ponieważ graf jest spójny ten warunek nie jest niemożliwy do spełnienia)

Edytowane 2 Grudnia 2006 przez Haquim

[MeHow]

Witaj Haquim, mam do Ciebie jeszcze jedna wielka prosbe. Czy znasz moze jakis algorytm, aby sprawdzic, czy graf jest planarny? Tzn czy mozna go tak poprzeksztalcac, aby krawedzie nie przecinaly sie. Wiem, ze istnieje algorytm Hopcroft'a Tarjana, ale niestety na polskich stronach nic nie znajduje, a wywody po angielsku niestety mnie pokonaly ze wzgledu na brak znajomosci tak specyficznego slownictwa.

 

Czy dysponujesz moze jakas ksiazka, czymkolwiek, moze nawet wiedza ;) jak taki algorytm powinien dzialac?

[Ragnor]

Witaj Haquim, mam do Ciebie jeszcze jedna wielka prosbe. Czy znasz moze jakis algorytm, aby sprawdzic, czy graf jest planarny? Tzn czy mozna go tak poprzeksztalcac, aby krawedzie nie przecinaly sie. Wiem, ze istnieje algorytm Hopcroft'a Tarjana, ale niestety na polskich stronach nic nie znajduje, a wywody po angielsku niestety mnie pokonaly ze wzgledu na brak znajomosci tak specyficznego slownictwa.

 

Czy dysponujesz moze jakas ksiazka, czymkolwiek, moze nawet wiedza ;) jak taki algorytm powinien dzialac?

 

Cześć! Jak tak bardzo interesują Cie algorytmy to proponuję zapoznać się z księgą: "Wprowadzenie do algorytmów" Cormena, tam znajdziesz większość odpowiedzi (algorytmów) jakie poszukujesz.

[MeHow]

Wyglada na to, ze bede musial przejsc sie po prostu do biblioteki na dluzsze posiedzenie i wyszukac powyzsze.