226 Colorare

[ditzone]

Aici puteţi discuta despre problema Colorare.

[•alex_prg]

aici e clar back nu ? am incercat unul care verifica toate posibilitatile de colorare da imi iese din timp pentru multe teste ... nu stiu cum sal mai optimizez 

[ditzone]

Poate te inspira un pic solutia de la Zebughil (solutia in 3^n)
http://info.devnet.ro/articole.php?page=art&art=74&artpage=5

[•tm_radu]

Pe testul :

Cod:

5 4
1 2
3 4 
4 5
3 5

va da cumva 3 36?
inca ceva...trebuie colorat graful cu exact p culori sau cu maxim p culori?

[•bogdan2412]

Da, e bine 3 36...

"Se cere determinarea numarului minim de culori necesar pentru o colorare valida. Pentru acest numar minim de culori se cere numarul de colorari valide ale nodurilor grafului."
Graful trebuie colorat cu exact p culori, unde p este minim...

Se poate rezolva problema si cu back in 0.01 daca te gandesti bine

[•tm_radu]

Eu am incercat alta metoda... numarul minim de culori l-am determinat ca fiind numarul maxim de muchii ce se intalnesc intr-un nod din cele n. Apoi pentru fiecare punct neselectat am pornit un DF din el, si am notat intr-un vector nr[] - numarul de culori in care poate fi colorat nodul i...iar numarul de culori este numarul minim de culori - numarul de vecini care i-am colorat deja.

Cod:

        1                           1(3)                      1(3)                         1(3)               
       / \            ->           / \            ->         / \             ->           / \                     
     /     \                     /     \                   /     \                      /     \              
    2      3                     2      3                  2(2)   3                    2(2)   3(2)             

in paranteza am notat numarul de moduri in care poate fi colorat nodul i
si la sfarsit inmultesc toate valorile dintre nr[];
ar trebui sa fie corect, insa iau WA.....de ce?

[•filipb]

E in mod evident WA pentru ca este cunoscut ca orice problema de colorare este NP-completa ( adica nu exista algoritmi polinomiali de rezolvare... ). Algoritmul tau este unul Greedy si pana acum nu s-a gasit nici un algoritm de acest gen pentru o problema de colorare. Deci sigur pentru grafuri mai mari algoritmul tau nu da rezultatul bun.
Un algoritm O(N!) este usor de scos, dar merge si folosind metoda de la zebughil ( un fel de dinamica pe multimi de noduri - tot exponential e, pentru ca ai 2^N submultimi de noduri, exponential in N ).

[•wefgef]

Un algoritm O(N!) este usor de scos, dar merge si folosind metoda de la zebughil ( un fel de dinamica pe multimi de noduri - tot exponential e, pentru ca ai 2^N submultimi de noduri, exponential in N ).

cica back optimizat merge cel mai bine.

[•bogdan2412]

Tocmai am spus mai sus ca backu (in O(N!)) merge in 0.01... rezolvarea in 3^n merge si in 0.2 pe unele cazuri.

[•greco]

Da, dar asta nu inseamna ca rezolvarea in N! e cea mai buna sau cea mai inteligenta.. e pur si simplu o rezolvare care se poate optimiza si opri in multe cazuri. Cred ca e mai util pentru cei care rezolva problema sa o rezolve prin cealalta metoda.

[•alex23]

Cat de mare e numarul maxim de posibilitati? Intra in long long?

[•filipb]

Da, intra pe long long.

[•ovidiuchis]

Cum se pot consulta sursele trimise la aceasta problema, avand in vedere ca nu este acces momentan.

[•pauldb]

Doar pentru unele probleme sunt accesibile sursele si acestea sunt marcate corespunzator. Colorare nu este una dintre aceste probleme.

[•ovidiuchis]

Ok. Se poate posta aici parte din sursa? sau hint-uri.

[•darkseeker]

Daca poate cineva as dori sa-mi dea  un test mai dificil ( nu ma refer la cele oficiale ) deoarece nu imi dau seama ce gresesc. Determin numarul minim de culori din prima colorare care mi-o da backtrackingul si apoi generez toate colorarile cu numarul de culori mergand doar pana la cel determinat prin metoda mentionata . Pe toate testele kre le-am dat .. imi merge.

[•razvan.popa]

Cum se combina 2 submultimi de noduri ale unei multimi la problema asta? 
Nu imi dau seama cum sa combin solutiile pentru dinamica...

L.E.
Se pare ca avea legatura cu submultimile independente ale grafului.

[•Andrei-27]

Metoda mea e:  pt fiecare componenta conexa retinem nr minim de culori in v[ ]. Pt fiecare c.c facem bfs si in functie de culorile vecine stabilim culoarea nodului curent. Parcurgem v[ ] - ul descrescator si facem inmultirile.