Jak znaleźć nieidentyczne elementy z wielu wektorów?

Question

Biorąc pod uwagę kilka wektorów/zestawów, z których każdy zawiera wiele liczb całkowitych, które są różne w obrębie jednego wektora. Teraz chcę sprawdzić, czy istnieje zestaw, który składa się z wyodrębnienia tylko jednego elementu z podanych wektorów/zestawów, w tym samym czasie, gdy wyodrębnione liczby są nieidentyczne od siebie.

Przykładowo, jeżeli określa a, b, c, d, jak:

a <- (1,3,5); 
b <- (3,6,8); 
c <- (2,3,4); 
d <- (2,4,6) 

znajdę się zestawy, takie jak (1, 8, 4, 6) lub (3, 6, 2, 4) ..... w rzeczywistości, muszę tylko znaleźć jeden taki zestaw, aby udowodnić istnienie.

stosując brutalne wyszukiwanie siły, można sprawdzić maksymalne kombinacje m^k, gdzie m jest rozmiarem podanych zbiorów, k jest liczbą podanych zestawów.

Czy istnieją jakieś sprytniejsze sposoby? Dziękujemy!

Answer 1

Można sformułować problem jako dopasowywanie w graf dwudzielny:

• węzeł z lewej strony są twoje zestawy,
• węzeł z prawej strony są całkowitą pojawiające się w zestawach.

Istnieje krawędź pomiędzy węzłem "zestaw" i węzłem "całkowitym", jeśli zbiór zawiera podaną liczbę całkowitą. Następnie próbujesz znaleźć dopasowanie na tym wykresie dwudzielnym: każdy zestaw będzie powiązany z jedną liczbą całkowitą, a żadna liczba całkowita nie zostanie użyta dwukrotnie. Czas działania prostego algorytmu znalezienia takiego dopasowania to O (| V || E |), tutaj | V | jest mniejsze niż (m + 1) k i | E | jest równe mk. Masz więc rozwiązanie w O (m^2 k^2). Zobacz: Matching in bipartite graphs.

Algorytm dopasowania dwustronnego:

Algorytm działa na zorientowanych na wykresach. Na początku wszystkie krawędzie są zorientowane od lewej do prawej. Dwa węzły zostaną dopasowane, jeśli krawędź między nimi jest zorientowana od prawej do lewej, więc na początku dopasowanie jest puste. Celem algorytmu jest znalezienie "ścieżek rozszerzających" (lub ścieżek naprzemiennych), tj. Ścieżek, które zwiększają rozmiar dopasowania.

Ścieżka rozszerzająca to ścieżka na grafice skierowanej, rozpoczynająca się od niedopasowanego lewego węzła i kończąca się na niedopasowanym prawym węźle. Gdy już posiadasz ścieżkę rozszerzającą, musisz po prostu odwrócić wszystkie krawędzie wzdłuż ścieżki do jednego zwiększenia rozmiaru dopasowania. (Rozmiar dopasowania zostanie zwiększony, ponieważ masz jeszcze jedną krawędź, która nie należy do dopasowania.To nazywa się ścieżką naprzemienną, ponieważ ścieżka zmienia się naprzemiennie pomiędzy krawędziami nienależącymi do pasującego, od lewej do prawej i krawędziami należącymi do pasującego, od prawej do lewej)

Oto, jak znaleźć drogę do nadbudowy.

1. wszystkie węzły są oznaczone jako nieodwiedzonych,
2. wybrać się nieodwiedzonych i niezrównaną lewy węzeł
3. masz zrobić Głębokie pierwsze wyszukiwanie, aż znajdziesz niedopasowany prawy węzeł (wtedy masz rozszerzającą ścieżkę). Jeśli nie możesz znaleźć niedopasowanego prawego węzła, przejdziesz do 2.

Jeśli nie możesz znaleźć ścieżki rozszerzającej, dopasowanie jest optymalne.

Znaleźć ścieżkę rozszerzającą jest złożona O (| E |), a robisz to co najwyżej min (k, m) razy, ponieważ rozmiar najlepszego dopasowania jest ograniczony przez k i m. Więc dla twojego problemu złożoność będzie O (mk min (m, k)).

Możesz również zobaczyć this reference, sekcja 1., aby uzyskać pełniejsze wyjaśnienie z dowodami.