szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 25 kwi 2016, o 13:53 
Użytkownik

Posty: 28
Lokalizacja: Warszawa/Radom
Dane mamy następujące zadanie:

Są 2 kajaki, n osób oraz zbiór par, które chcą razem przepłynąć się kajakiem (jedna osoba może chcieć się przepłynąć kolejno z wieloma osobami). Zastosować algorytm znajdujący skojarzenie doskonałe do wyznaczenia rozkładu jazdy kajaków, tak aby zminimalizować ilość kursów pojedynczych kajaków. Należy przy tym spełnić życzenia wszystkich osób.

No i pierwszym nasuwającym się pomysłem jest jest budowa grafu w następujący sposób: bierzemy ludzi jako wierzchołki a krawędzie dajemy pomiędzy tymi wierzchołkami, które odowiadają osobom, które chcą razem przepłynąć się kajakami. W takim grafie znajdujemy skojarzenie doskonałe, wybieramy 2 krawędzie (czyli 4 osoby do 2 kajaków) i usuwamy je z grafó oraz dodajemy do rozkładu jazdy. Następnie znowu wyznaczamy skojarzenie itd.

Okazuje sie jednak, że to naiwne rozwiązanie jest błędne, a oto kontrprzykład:

Pięć osób: a,b,c,d,e i pary które chcą się razem przepłynąć:
ab,ac,ad,ae,bd,be,cd

Czyli graf ma 5 wierzchołków, 7 krawędzi.
1. maksymalne skojarzenie: ae,cd -> płyną równolegle
zostają ab,ac,ad,bd,be
2. maksymalne skojarzenie: ac,be -> płyną równolegle
zostają ab,ad,bd
i te 3 pary płyną pojedynczo

A lepiej ożna tak:
ab,cd
ad,be
ae,bd
ac


Należy zatem szukać skojarzenia w innym grafie - niestety nie wiem jakim...

Jedyne co mi wiadomo, to z grafu G (ten opisany wyżej) można otrzymać go za pomocą jakichś dwóch elementarnych operacji, ale nie mam pojęcia jakich - próbowałem drzew rozpinających itp. (może coś przeoczyłem?) Stąd moja prośba o pomoc w rozwiązaniu powyższego problemu. Generalnie dążymy do:


G -> G' -> G''

i w grafie G'' szukamy skojarzenia. Takie wskazówki dostałem.

Pozdrawiam.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 3 wrz 2016, o 17:20 
Użytkownik

Posty: 1086
Lokalizacja: Lublin/Warszawa
Napisałeś w treści zadania, że pewne osoby chcą kolejno przepłynąć z innymi. Mam nadzieję, że nie chodzi o to, że podana kolejność par musi być zachowana dla konkretnych osób, w swoim rozwiązaniu nie zachowywałeś tej kolejności. Dlatego zakładam, że żadna kolejność par nie jest ważna.

Zbudujmy graf nieskierowany z par które mają razem przepływać tzn niech wierzchołkami grafu będą pary, a krawędziami połączmy te pary, które są rozłączne (nie mają wspólnego elementu). Wtedy krawędź oznacza, że wierzchołki (pary) połączone tą krawędzią mogą płynąć razem w dwóch łódkach. Szukamy w tym grafie maksymalnego skojarzenia - otrzymamy zbiór krawędzi, czyli par par osób które płyną razem w dwóch łódkach. Wierzchołki nie wybrane do skojarzenia płyną pojedynczo.
Nie zawsze znajdę skojarzenie doskonałe, bo może ono nie istnieć, jak np. w podanym przez Ciebie przykładzie.
Dla Twojego przykładu graf będzie złożony z 7 wierzchołków: ab, ac, ad, ae, bd, be, cd i 5 krawędzi:
ab - cd, cd - be, ac - be, ac - bd, ad - be, ae - cd, ae - bd. Maksymalne skojarzenie w tym grafie to ab - cd, ad - be, ae - bd, pozostaje wierzchołek: ac, czyli się zgadza.
Algorytm wyszukujący maksymalne skojarzenie jest np. tutaj:
http://wazniak.mimuw.edu.pl/index.php?title=Zaawansowane_algorytmy_i_struktury_danych/Wyk%C5%82ad_8
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 krawędzie w grafie.  manduka  2
 Ścieżka alternująca w grafie dwudzielnym  5darek5  0
 Podgraf dwudzielny w grafie  ucaps  1
 Najdłuższe drogi w grafie.  snowjay  2
 Cykl eulera w grafie i jego grafie krawędziowym.  krzysiel00  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl