Utwórz nowy wątek Odpowiedz w wątku  [ Posty: 6 ] 
POlitycy 
Autor Wiadomość
Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 27 paź 2009, o 00:30
Posty: 138
Post POlitycy
Przyjaciele zza wielkiej wody donoszą, że znalezienie deterministycznego wielomianowego algorytmu do tego zadania jest problemem otwartym. Czy komuś z Was się udało? :D

_________________
Mięso = Morderstwo


7 lis 2010, o 22:50
Zobacz profil
Gwiazda 3
Avatar użytkownika

Dołączył(a): 23 lis 2009, o 08:40
Posty: 175
Post Re: POlitycy
Niestety nie, ale po sieci krąży trochę pdf'ów opisujących algorytm, który dla 3-kolorowalnych grafów rzekomo znajduje w wielomianowym czasie kolorowanie używając co najwyżej n^(3/14) kolorów. W zadaniu w zupełności nam wystarcza znalezienie 4-kolorowania, co dla n=100 jest zagwarantowane.

Ale jednak jakoś nie miałem siły tego analizować, więc zakodziłem randa - 0.00s na wszystkich testach i oczywiście 100 pkt :P


7 lis 2010, o 22:58
Zobacz profil
Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 27 paź 2009, o 00:30
Posty: 138
Post Re: POlitycy
Sebastian Daniel Nowak napisał(a):
Niestety nie, ale po sieci krąży trochę pdf'ów opisujących algorytm, który dla 3-kolorowalnych grafów rzekomo znajduje w wielomianowym czasie kolorowanie używając co najwyżej n^(3/14) kolorów. W zadaniu w zupełności nam wystarcza znalezienie 4-kolorowania, co dla n=100 jest zagwarantowane.

Ale jednak jakoś nie miałem siły tego analizować, więc zakodziłem randa - 0.00s na wszystkich testach i oczywiście 100 pkt :P


Jest 300 razem? :)

_________________
Mięso = Morderstwo


7 lis 2010, o 22:59
Zobacz profil
Gwiazda 3
Avatar użytkownika

Dołączył(a): 23 lis 2009, o 08:40
Posty: 175
Post Re: POlitycy
Nie ma tak pięknie, 30 pkt w plecy za stałą w Tekstowych, miałem O(nm) tylko używałem list z stl'a. Do tego dochodzi kolejne 20 za System zapisów, turbomatching okazał się za wolny.

/edit
W sumie zastanawia mnie, jakiej używaliście heurezy? Ja losowo chodziłem dfs'em po grafie i zachłannie przydzielałem kolory aż do otrzymania poprawnego 4-kolorowania.


7 lis 2010, o 23:06
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 25 paź 2009, o 12:35
Posty: 37
Post Re: POlitycy
Sebastian Daniel Nowak napisał(a):
Nie ma tak pięknie, 30 pkt w plecy za stałą w Tekstowych, miałem O(nm) tylko używałem list z stl'a. Do tego dochodzi kolejne 20 za System zapisów, turbomatching okazał się za wolny.

/edit
W sumie zastanawia mnie, jakiej używaliście heurezy? Ja losowo chodziłem dfs'em po grafie i zachłannie przydzielałem kolory aż do otrzymania poprawnego 4-kolorowania.

Ja miałem backtracking z dwukolorowaniem. Najpierw z grafu wybierałem trójkąty i zapisywałem graf vector<PII> adj[MAXV]; - dla każdego lista gości, z którymi jest w trójkącie. backtracking jakoś standardowo - jak przeszedł po wszystkich gościach i nie znalazł rozwiązania to czyściłem i w losowej kolejności do nich wchodziłem. Wynik: 45.

Wogle wieeeelki szacun dla Ciebie za napisanie randoma, który wszedł!
Random górą!


7 lis 2010, o 23:18
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 20 lis 2009, o 22:04
Posty: 40
Post Re: POlitycy
Też mam randoma na 100. Tyle, że na tych trójkach, 2-kolorowaniu i chodziłem bfsem. ;)


7 lis 2010, o 23:42
Zobacz profil
Wyświetl posty nie starsze niż:  Sortuj wg  
Utwórz nowy wątek Odpowiedz w wątku  [ Posty: 6 ] 


Kto przegląda forum

Użytkownicy przeglądający ten dział: Brak zidentyfikowanych użytkowników i 2 gości


Nie możesz rozpoczynać nowych wątków
Nie możesz odpowiadać w wątkach
Nie możesz edytować swoich postów
Nie możesz usuwać swoich postów
Nie możesz dodawać załączników

Skocz do:  
cron


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group. Forum style based on STSoftware Hestia.
Przyjazne użytkownikom polskie wsparcie phpBB3 - phpBB3.PL