Poszukiwanie algorytmu do rozwiązania pracy domowej z grafów

pytanie zadane 4 lutego 2018 w Algorytmy przez ekhm Nowicjusz (240 p.)
zmienione kategorie 4 lutego 2018 przez ekhm

Witam serdecznie,

Ostatnio próbuję znaleźć sposób w jaki mógłbym rozwiązać następujące zadania:

Zadanie 1.
W grupie osób określamy relację A nie lubi B. Relacja ta nie jest symetryczna.
Jeżeli istnieje ciąg relacji A1 nie lubi A2, A2 nie lubi A3 ... Ak nie lubi A1,
to wszystkie osoby w takim cyklu przynależą do jednej grupy "nie lubienia".
Dla podanych na wejściu par określających relacje wyznacz podział na maksymalne
grupy "nie lubienia". Podaj złożoność i uzasadnij poprawność swojego rozwiązania.

Tutaj udało mi się rozwiązać zadanie za pomocą wyznaczania silnie spójnych składowych a dokładniej algorytmu Tarjana, aczkolwiek mam problem z wyznaczeniem złożoności.

Zadanie 2.
W grupie niegrzecznych dzieci istnieją pewne animozje. Przedszkolanka postanowiła
ustawić dzieci w rzędzie. Jeżeli A nie lubi B, to nie może stać w rzędzie przed B (aby nie rzucać w niego papierkami).
a) Określ, czy grupę dzieci można ustawić w jednym rzędzie
b) Jeżeli nie, to podaj minimalną liczbę rzędów koniczną do ustawienia dzieci.
c) Podaj minimalną liczbę rzędów konieczną do ustawienia dzieci, jeżeli:
Dziecko A nie lubi dziecka B, to musi stać w rzędzie o niższym numerze.

Podaj złożoność i uzasadnij poprawność swojego rozwiązania powyższych punktów.

Niestety nie mam za bardzo pomysłu jak rozwiązać zadanie 2. Czy ktoś z was spotkał się może z podobnym zadaniem i dałby parę wskazówek? :)

Z góry dziękuję za pomoc i pozdrawiam

3 odpowiedzi

odpowiedź 5 lutego 2018 przez TenGumis Gaduła (3,440 p.)
wybrane 5 lutego 2018 przez ekhm

Najlepsza

Złożoność algorytmu tarjana z zadania 1 jest liniowa względem liczby wierzchołków i krawędzi tj. O(V + E)

.Odpowiedzią na zadanie drugie jest sortowanie topologiczne, które istnieje jeśli w grafie nie ma cykli. Zatem należy sprawdzić czy jest cykl. Jeśli jest dzieci nie da się ustwaić(dowodem może być zadanie 1 bo wtedy zawsze przed jakąś osobą musi stać ktoś kto jej nie lubi) w przeciwnym przypadku ustawieniem dzieci jest wynik sortowania topologicznego. Co do ilości rzędów należy rekurencyjnie wywoałć dfsa na grafie i gdy dojdziemy do liścia ustawić jego odległośc na jeden, a następnie dla każdego wierzchołka ustawiać jego odległość na minimum z jego dzieci (wichołków z niego osiągalnych) + 1. Odpowiedzią w tedy będzie maksymalna z tych policzonych wartości,

komentarz 5 lutego 2018 przez ekhm Nowicjusz (240 p.)

Czy w zadaniu 2a wystarczy sprawdzenia istnienia przynajmniej jednej spójnej składowej? SSS jest cyklem prawda?

komentarz 7 lutego 2018 przez TenGumis Gaduła (3,440 p.)

Jeśli masz na myśli silnie spójną składową to tak, ale algorytm sprawdzenia czy istnieje cykl jest prostszy: http://eduinf.waw.pl/inf/alg/001_search/0133.php

komentarz 7 lutego 2018 przez ekhm Nowicjusz (240 p.)

@TenGumis,
A propos podpunktu c dostałem informację że należy postępować jak w algorytmie sortowania topologicznego poprzez usuwanie źródeł. W pierwszym rzędzie źródła. Usuwamy te źródła i w ten sposób nowe źródła, które wstawiamy do kolejnego rzędu itd. aż wybierzemy wszystkie wierzchołki. Znalazłem algorytm sortowania topologicznego: http://www.onlineclassnotes.com/2016/03/sort-dependency-list-or-topological-sorting-in-php.html Zastanawiam się jak go zmodyfikować by otrzymać liczbę rzędów.

komentarz 7 lutego 2018 przez TenGumis Gaduła (3,440 p.)

Rozwiązanie jakie przychodzi mi do głowy to uzupełnianie zbioru źródeł (wierzchołków o stopniu wejściowym 0) dopiero gdy poprzedni się wyczerpie. Dzięki temu każde uzupełnianie zbioru zwiększa nam poszukianą wartośc o 1.


Q1, Q2 ← Kolejka z wierzchołkami o stopniu wchodzącym równym 0
dopóki Q1 jest niepusta rób
    usuń wierzchołek n z przodu kolejki Q1
    wypisz n
    dla każdego wierzchołka m o krawędzi e od n do m rób
        usuń krawędź e z grafu
        jeżeli do m nie prowadzi żadna krawędź to
            wstaw m do Q2
    jeżeli Q1 puste
        przenieś wierzchołki z Q2 do Q1. Wyczyść Q2.
        wynik++;

komentarz 7 lutego 2018 przez ekhm Nowicjusz (240 p.)
edycja 11 lutego 2018 przez ekhm

@TenGumis, A propos zadania 2a to zastanawiam się czy potrzebuję wykorzystać algorytm który podesłałeś do znajdowania cyklu w grafie. Obecnie sprawdzam czy algorytm Tarjana zwraca mi tablicę SSS. Wydaję mi się że to wystarczy by sprawdzić istnienie cyklu.

Wykorzystałem polecany przez ciebie algorytm do szukania cyklu w grafie. Ku mojemu zaskoczeniu teraz mam taką sytuację że algorytm Tarjana zwraca mi 0 SSS a za algorytm do szukania cykli w grafie skierowanym zwraca mi parę cykli. Jeśli dobrze rozumiem to cykl jest SSS?

odpowiedź 4 lutego 2018 przez Wiciorny Ekspert (269,710 p.)

Algorytm wszystkich możliwych permutacji zbioru ?

http://sebastianpawlak.com/pl/Informatyka/Algorytmy/Permutacje/index.html

Tak ja to widzę, czyli wszystkich możliwych przypadków

komentarz 4 lutego 2018 przez jankustosz1 Nałogowiec (35,880 p.)

Tylko że to jest brut i ma słabą złożoność, zapewne chodzi o jakiś szybszy algorytm.

komentarz 7 lutego 2018 przez ekhm Nowicjusz (240 p.)

@Wiciorny, Otrzymałem informację że takie rozwiązanie jest akceptowalne, zatem jeśli nie znajdę bardziej optymalnego rozwiązania to spróbuję w ten sposób. Zastanawiam się jak sprawdzać poszczególne nowe grupy. Biorąc pod uwagę że ilość rzędów musi być minimalna zatem grupy powinny być możliwie jak największe.