Problem kojarzenia małżeństw - zmodyfikowany

Witam,

Od jakiegoś czasu zmagam się z tym problemem i próbuję rozwikłać 2 zagadki :)

1. Czy da się w jakiś szybki sposób (nie brutem) wyznaczyć wszystkie możliwe rozwiązania?
2. Załóżmy taką sytuację: mamy 10 panien i 20 kawalerów, ale interesuje nas skojarzenie tylko tych 10 panien. Czy wykorzystując ten sam algorytm co w klasycznym problemie jestem w stanie uzyskać taki rezultat? Jak na mój rozum to chyba tak, ale nie chciałbym, żeby w pewnym momencie okazało się inaczej.

Byłbym wdzięczny za solidną odpowiedź.

Pozdrawiam

Czy ktoś tu w ogóle wie o co chodzi? :/
Dla niezorientowanych polecam:
http://edu.i-lo.tarnow.pl/inf/utils/002_roz/ol023.php

I jeszcze może sprostuję, że każda "panna" ma mieć tylko jednego "kawalera", a pozostałych 10 kawalerów zostaje samotnikami. Coś mi się zdaje, że i to sprostowanie na niewiele się zda... ehh..

http://wazniak.mimuw.edu.pl/index.php?title=Zaawansowane_algorytmy_i_struktury_danych/Wyk%C5%82ad_7

Tu jest profesjonalny opis zagadnienia.

Ad 1) Nie wiem ;D
Ad 2) Ocb w pytaniu?

;p

Ad 2) Chodzi o to że mam 10 zadań do wykonania i 20 potencjalnych wykonawców. Interesuje mnie TYLKO wykonanie tych zadań. To, którzy wykonawcy znajdą zatrudnienie mnie mniej interesuje, chcę ich tylko potem znać. Jaśniej chyba już się nie da. :P

A co do linka, to niestety nie pomógł. ;/

Co do drugiej kwestii:

Jeżeli masz n kobiet i m mężczyzn (m>n), dodajesz sobie do problemu m-n "lalek", z których każda zna wszystkich mężczyzn i stosujesz dla takiego grafu podany wcześniej algorytm.

Good point, dzięki. Dziwne ze sam na to nie wpadłem, bo bardzo podobne modyfikacje już wcześniej do swojego algo wprowadziłem. :D A swoją drogą ciekawe, czy bez "lalek" by zadziałało, bo mam wrażenie, że owszem.

Przecież w problemie maksymalnego skojarzenia robi się dokładnie to czego chcesz w drugim punkcie. Nie wiem dalej o co biega, czego nie rozumiesz w tej kwestii: http://en.wikipedia.org/wiki/Hopcroft–Karp_algorithm -> "produces as output a maximum cardinality matching – a set of as many edges as possible with the property that no two edges share an endpoint". Graf dwudzielny nie musi mieć równej ilości wierzchołków w obu "częściach".

Co do wyszukania wszystkich rozwiązań to może najpierw zrobić maksymalne skojarzenie, a potem szukać jakichś ścieżek alternujących i zmieniać skojarzenie według nich - tak samo jak przy ścieżkach powiększających tylko tutaj ścieżka przechodziłaby przez tyle samo krawędzi wolnych co skojarzonych (no bo maksymalnego skojarzenia już się nie da powiększyć). Tylko, że pewnie do wyznaczania tych ścieżek alternujących trzeba wymyślić jakiś algorytm działający w sensownym czasie.

donkey7 napisał(a)

Przecież w problemie maksymalnego skojarzenia robi się dokładnie to czego chcesz w drugim punkcie.

Niezupełnie, w tym punkcie tylko starałem się ustalić, czy ilość "panien" i "kawalerów" musi być równa i czy w przeciwnym razie klasyczny algorytm się nie posypie.

donkey7 napisał(a)

Graf dwudzielny nie musi mieć równej ilości wierzchołków w obu "częściach".

Dokładnie o to stwierdzenie mi chodziło :)

Temat uważam za zamknięty. Dzięki wszystkim, którzy wtrącili swoje 3 grosze. :)
Pozdrawiam

LOL. To na przyszłość staraj się formułować pytania jaśniej. W ogóle to Hrypa podał złe rozwiązanie raczej, tzn mało praktyczne. Jeśli chcesz mieć po równo po obu stronach to po prostu dodaj sobie jakieś wierzchołki (tutaj: panny) bez żadnych wychodzących krawędzi (tutaj: znajomości). To nie zmieni ani trochę maksymalnego skojarzenia. Złożoności chyba też.