Informatyka UJ forum

cct · pijak Dołączył: 21 Mar 2006 Posty: 202 Przeczytał: 0 tematów

Wierzę, że się przydadzą. Powinny generować dobre dane (tj bez powtórzeń etc.), ale w przypadku niezgodności z odpowiedzią można poszukać czy coś przypadkiem nie trafiło się złego.

Wersje windowsowe:

[link widoczny dla zalogowanych]
[link widoczny dla zalogowanych]
[link widoczny dla zalogowanych]

[link widoczny dla zalogowanych]
[link widoczny dla zalogowanych]

Wersje linuxowe, kompilowane na Virgo:

[link widoczny dla zalogowanych]
[link widoczny dla zalogowanych]
[link widoczny dla zalogowanych]

[link widoczny dla zalogowanych]
[link widoczny dla zalogowanych]

EDIT: jak zauważył Chlebek, moje U nie czyściło do konca pamięci (technicznie rzecz ujmując, w ogóle nie czyściło, i na tym polega cały bajer ;)), ale coś się krzaczyło czasem dla niektórych mniejszych testów, więc poprawiłem metodą brute_memset_na_ilość_elementów nieco binarki. Jakby komuś wyskakiwał ANS to niech porówna jeszcze z nową wersją.

przem

dzieki cct na pewno sie przyda

chlebek

dzieki wielkie

cct · pijak Dołączył: 21 Mar 2006 Posty: 202 Przeczytał: 0 tematów

Doszły binarki do uruchamiania pod linuxem (na prośbę Insa).

Tymczasem, ponieważ parę osób pytało - szybki opis kursorowej reprezentacji grafu Robsona-ceceta (nazwa od niezależnego odkrycia reprezentacji przez dwóch paranaukowców w początkach XXI wieku ;))

Do trzymania krawędzi wystarczy np. rekordzik:

Spectro

chlebek

czy ktos mial problem z RTE w tym zadaniue ?

Yoter

ja - za mało alokowanej pamięci...

chlebek

Spectro

Ja miałem RTE przez chwilę, ale po zamianie intów na shorty do oznaczania numerów wierzchołków już tego błędu nie było.

Aha, wartość przepływów i przepustowość trzymam w charach, choć można byłoby od biedy obie rzeczy w jednym polu zmieścić :P .

chlebek

poszlo, a jednak blad przy wczytywaniu tego nowego grafu

Yoter

@chlebek : to nie był żart ;p

trywialna

@cct: czy mi sie zdaje czy twoj generator testów do V (pod windowsem) jest tak naprawde generatorem testow dla U?

edit: wycofuje pytanie

hansu

@cct: To badz jeszcze dobrym opensourcowcem i dorzuc kody zrodlowe do tych wszystkich binarek ktore podlinkowales ;P

trywialna

Ma może ktoś jakieś testy do V? mam ansa...

cct · pijak Dołączył: 21 Mar 2006 Posty: 202 Przeczytał: 0 tematów

Rogal

Hmmm może się nie znam i co prawda nie byłem na wykładzie, ale tak na pierwszy rzut oka DFS nie wydaje mi się najlepszym pomysłem. BFS powinien sprawdzić się znacznie lepiej.

dzendras

Rogal: Nam p. Jeżabek mówił, że do zadań U i V wystarczy DFS i co ważne będzie to szybsze od wersji z BFS. Bez BFS nie obejdzie się za to w zadaniu Z2.

Spectro

I nic dziwnego:
W standardowej wersji metoda Forda-Fulkersona działa w czasie O(m*|f|), a ponieważ przepustowość każdej krawędzi wynosi co najwyżej 1, to |f| = n, zatem czas: O(m*n). To trochę lepiej niż O(m^2*n) z wersji Edmondsa-Karpa :P .

edit: Trochę głupot tu napisałem ;] .

Rogal

Spectro: Nie mąć ludziom w głowach proszę bo pytanie o złożoność czegoś takiego z BFS-em może pojawić się na egzaminie.

edited: Żeby nie było złożoność zarówno BFS-a jak i DFS-a w tym przypadku to po prostu O(m*|f|) gdzie |f| oznacza maksymalny przepływ, a że przepustowość każdej krawędzi jest jednostkowa i ścieżek jest na pewno mniej niż wierzchołków (w obu zadaniach) to złożoność jest O(mn).

edited2: Żeby było jeszcze jaśniej Edmonds-Karp na takich szczególnych grafach jak te które mamy w tym zadaniu działa w czasie O(mn) a nie żadne O(m^2*n) jak raczył napisać Spectro :wink:

edited3: Teraz to już się pewnie czepiam, ale

cct · pijak Dołączył: 21 Mar 2006 Posty: 202 Przeczytał: 0 tematów

hansu

cct ma racje - w tym szczegolnym przypadku DFS bedzie wydajniejszy od BFSa, wprawdzie tylko o stala, ale i tak dosc istotnie.

Natomiast w ogolnym przypadku algorytmu EK dla dowolnej sieci przeplywowej DFS jest mocno chybionym pomyslem, bo w EK potrzebujemy wybrac najkrotsza sciezke od zrodla do ujscia i takie wlasnie postepowanie gwarantuje nam ze ze iteracji petli zwiekszajacej wartosc przeplywu bedzie EV a nie |f|, jak to jest w ogolnym przypadku metody Forda-Fulkersona. Natomiast tutaj, dzieki temu ze |f| <= V, mozemy uzyc dowolnej z tych metod a i tak nie wyjdziemy asymptotycznie poza EV. No ale tak jak napisal cct DFS jest wydajniejszy...

Spectro

Rogal

Spector: Eeee dobra, co do ostatniego masz rację - w tym przypadku to ja byłem półprzytomny :D

Pomyliło mi się z przypadkiem, gdy pomiędzy daną parą wierzchołków może być więcej niż jedna krawędź - ale wtedy możemy z tych kilku krawędzi zrobić przecież jedną, która ma przepsutowość > 1.

cct: Tyż prawda, że akurat w zad. V DFS zadziała lepiej. Nie mniej graf w V to już jest tak szczególny, że tutaj wogóle nie powinno się stosować przepływu tylko H-K i dlatego takie cuda przechodzą. Natomiast w U wydaje mi się, że BFS powinien działać lepiej, nie mniej trzebaby przeprowadzić szereg testów.

Spectro

Rogal

Spectro: Łatwo zrobić, żeby BFS działał w czasie zupełnie pesymistycznym. Wystarczy graf 2-dzielny z podpiętym źródłem i ujściem (taki jak w zad V) albo nawet ogólniej - graf k-dzielny - czyli taki podzielony na kilka warstw - przy czym każda warstwa jest połączona krawędziami tylko z poprzednią (w szczególności ze źródłem) i następną (w szczególności z ujściem). Wtedy każda ścieżka ma długość k+1 i za każdym razem przeglądane są wszystkie wierzchołki (czy tam prawie wszystkie :wink: )

Natomiast przypadek pesymistyczny dla DFS-a zależałby nie tylko od samej struktury grafu ale przede wszystkim od tego w jakiej kolejności w wierzchołku pamiętane są poszczególne krawędzie. Tak więc generalnie gdyby krawędzie ustawić w porządku losowym (albo może sortowanie coś pomoże?) to o przypadek pesymistyczny bardzo trudno (jak np. dla QuickSorta)

Nie mniej jednak idea wyszukiwania najkrótszej ścieżki podoba mi się znacznie bardziej niż wyszukiwania ścieżki losowej :D A wogóle to imho najprzyjemniejsze jest szukanie najszerszej ścieżki korzystając z Dijkstry, no ale to już też jest inna para kaloszy.