• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

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

Aruba Cloud VPS - 50% taniej przez 3 miesiące!
+1 głos
566 wizyt
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

0 głosów
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?

 

0 głosów
odpowiedź 4 lutego 2018 przez Wiciorny Ekspert (277,800 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 (36,720 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.

0 głosów
odpowiedź 4 lutego 2018 przez jankustosz1 Nałogowiec (36,720 p.)
Nie wiem czy by to zadziałało ale ja bym tam algorytmu zachłannego szukał. Np. w taki sposób:

Na koniec kolejki dajesz tych którzy w nikogo nie rzucają lub rzucają w najmniej osób. Jeżeli jest przypadek że nie da się go wstawić bo ktoś z tyłu w niego rzuci to musisz stworzyć nową kolejkę i tam go dać. Ale nie wiem czy to jest ok.

Podobne pytania

0 głosów
1 odpowiedź 580 wizyt
pytanie zadane 16 stycznia 2023 w C i C++ przez polandonion Dyskutant (7,560 p.)
0 głosów
0 odpowiedzi 106 wizyt
0 głosów
1 odpowiedź 179 wizyt
pytanie zadane 23 czerwca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

93,093 zapytań

142,054 odpowiedzi

321,493 komentarzy

62,435 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj

Wprowadzenie do ITsec, tom 1 Wprowadzenie do ITsec, tom 2

Można już zamawiać dwa tomy książek o ITsec pt. "Wprowadzenie do bezpieczeństwa IT" - mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy aż 15% zniżki! Dziękujemy ekipie Sekuraka za fajny rabat dla naszej Społeczności!

...