ditzone
Vizitator
|
|
« : Aprilie 03, 2006, 22:44:41 » |
|
Aici puteţi discuta despre problema Colorare.
|
|
|
Memorat
|
|
|
|
•alex_prg
Strain
Karma: -5
Deconectat
Mesaje: 21
|
|
« Răspunde #1 : Aprilie 06, 2006, 22:32:34 » |
|
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
|
|
|
Memorat
|
reality is just an illusion created by the lack of alcohol
|
|
|
|
•tm_radu
|
|
« Răspunde #3 : Iulie 12, 2006, 00:38:30 » |
|
Pe testul : va da cumva 3 36? inca ceva...trebuie colorat graful cu exact p culori sau cu maxim p culori?
|
|
|
Memorat
|
Daca nu merge o preblema, depaneaz-o, si abia apoi arunci calculatoru pe geam
|
|
|
•bogdan2412
|
|
« Răspunde #4 : Iulie 12, 2006, 08:11:07 » |
|
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
|
|
|
Memorat
|
|
|
|
•tm_radu
|
|
« Răspunde #5 : Iulie 12, 2006, 13:04:52 » |
|
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. 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?
|
|
|
Memorat
|
Daca nu merge o preblema, depaneaz-o, si abia apoi arunci calculatoru pe geam
|
|
|
•filipb
|
|
« Răspunde #6 : Iulie 12, 2006, 13:59:54 » |
|
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 ).
|
|
« Ultima modificare: Iulie 12, 2006, 14:21:01 de către filipb »
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #7 : Iulie 13, 2006, 14:54:48 » |
|
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.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•bogdan2412
|
|
« Răspunde #8 : Iulie 14, 2006, 09:31:27 » |
|
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.
|
|
|
Memorat
|
|
|
|
•greco
|
|
« Răspunde #9 : Iulie 14, 2006, 21:00:38 » |
|
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.
|
|
|
Memorat
|
Jump in the cockpit and start up the engines Remove all the wheelblocks there's no time to waste Gathering speed as we head down the runway Gotta get airborne before it's too late.
|
|
|
•alex23
Strain
Karma: -7
Deconectat
Mesaje: 13
|
|
« Răspunde #10 : August 25, 2008, 20:34:01 » |
|
Cat de mare e numarul maxim de posibilitati? Intra in long long?
|
|
|
Memorat
|
|
|
|
•filipb
|
|
« Răspunde #11 : August 25, 2008, 21:19:00 » |
|
Da, intra pe long long.
|
|
|
Memorat
|
|
|
|
•ovidiuchis
Strain
Karma: 0
Deconectat
Mesaje: 2
|
|
« Răspunde #12 : Decembrie 05, 2010, 22:04:02 » |
|
Cum se pot consulta sursele trimise la aceasta problema, avand in vedere ca nu este acces momentan.
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #13 : Decembrie 05, 2010, 22:23:26 » |
|
Doar pentru unele probleme sunt accesibile sursele si acestea sunt marcate corespunzator. Colorare nu este una dintre aceste probleme.
|
|
|
Memorat
|
Am zis
|
|
|
•ovidiuchis
Strain
Karma: 0
Deconectat
Mesaje: 2
|
|
« Răspunde #14 : Decembrie 05, 2010, 23:02:53 » |
|
Ok. Se poate posta aici parte din sursa? sau hint-uri.
|
|
|
Memorat
|
|
|
|
•darkseeker
|
|
« Răspunde #15 : Martie 09, 2011, 20:11:20 » |
|
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.
|
|
|
Memorat
|
|
|
|
•razvan.popa
Strain
Karma: -3
Deconectat
Mesaje: 12
|
|
« Răspunde #16 : Februarie 28, 2013, 17:23:51 » |
|
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.
|
|
« Ultima modificare: Martie 01, 2013, 11:19:53 de către Popa Razvan »
|
Memorat
|
|
|
|
•Andrei-27
Strain
Karma: 0
Deconectat
Mesaje: 17
|
|
« Răspunde #17 : August 03, 2018, 01:12:33 » |
|
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.
|
|
|
Memorat
|
|
|
|
|