Pytanie Jaki jest lepszy algorytm niż brute force do rozdzielania elementów w nakładających się kategoriach?


Mam arbitralny zestaw elementów (kropki poniżej) i pewną liczbę kategorii nakładających się w sposób arbitralny (A-C poniżej). Test polega na ustaleniu, czy każdy element może być przypisany do a pojedynczy do kategorii, do której już należy, tak, że każda kategoria kończy się co najmniej pewną liczbą pozycji.

Na przykład, możemy wymagać, aby każdy z nich, A, B i C, mógł złożyć wniosek jeden pozycja. Jeśli dostaniesz wszystkie 4 kropki poniżej, pokazanie, że jest to możliwe, jest łatwe: po prostu przyklej wszystkie elementy na liście, przeglądaj kategorie i każda kategoria usuwa element, do którego ma dostęp, i tak długo, jak każdy kategoria jest w stanie usunąć jeden przedmiot, zdajemy test.

Venn diagram, with three circles and colored dots in the overlapping sections

Załóżmy teraz, że usuwamy niebieską kropkę i powtarzamy test. Oczywiście możemy przypisać żółty do A, czerwony do B i zielony do C, i znowu mijamy. Trudno jednak skodyfikować to rozwiązanie: jeśli zastosujemy poprzednią metodę (znowu brak niebieskiej kropki), to załóżmy, że A zaczyna się od usunięcia zielonej kropki. Teraz, jeśli B usunie żółtą kropkę, nie zdamy testu (ponieważ C nie może usunąć czerwonej kropki), natomiast jeśli B usunie czerwony kropka, C może nadal wziąć żółty i przejść.

Można to rozwiązać za pomocą brutalnej siły poprzez powtarzanie każdego możliwego przypisania elementów do kategorii, sprawdzanie, czy warunek jest spełniony dla każdej iteracji, ale to nie będzie się dobrze skalować do dowolnych liczb pozycji i kategorii, i mam przeczucie istnieje mądrzejszy lub bardziej skuteczny sposób.

Nie znam nazwy tego problemu, co utrudnia badanie. Czy ma optymalne rozwiązanie? Jeśli tak, to jakiego rodzaju złożoności można się spodziewać po rozwiązaniu?


11
2017-08-23 20:19


pochodzenie


Nie przemyślałem tego w pełni, ale wydaje mi się, że powinno to być możliwe do rozwiązania dzięki dynamicznemu programowaniu, a tym samym znacznie skorzystać z memoizacji. - Oliver Charlesworth
To pytanie wydaje się być nie na temat, ponieważ wydaje się bardziej odpowiednie dla math.stackexchange.com. - Barmar
Być może brakuje mi jakiejś zasady, ale uważam, że teoria algorytmiczna jest gałęzią informatyki. Centrum pomocy mówi: "jeśli twoje pytanie obejmuje [...] algorytm oprogramowania [...], jesteś w odpowiednim miejscu, aby zadać pytanie!" - Giulio Franco
Próbowałem edytować to, aby wyglądało mniej jak pytanie do wyszukania lub pytanie "nazwij melodię". Jeśli dodałem do tego skrót, proszę, kontynuuj, aby go ulepszyć. - Todd A. Jacobs
@CodeGnome, wydaje mi się, że te poprawki znacznie poprawiają pocztę. - Shep


Odpowiedzi:


Miałeś rację, wskazując, że jest to problem przydziału, i jako taki można go rozwiązać za pomocą klasycznych algorytmów Graph Theory.

Możesz przetłumaczyć swój problem w następujący sposób:

enter image description here

Węzły po jednej stronie reprezentują kategorie, a węzły po drugiej stronie reprezentują elementy. Chcesz znaleźć maksymalne dopasowanie. Ten problem można zredukować do znalezienia maksymalny przepływ w wykres dwuczęściowy.

Fold-Fulkerson można użyć do znalezienia maksymalnego dopasowania w wykresie dwudzielnym w O (ES), gdzie E to liczba krawędzi, a S to maksymalny przepływ w sieci.


6
2017-08-23 20:34





Pozwolić D oznacza zbiór twoich kropek, i C oznacza zbiór kategorii.

Można zbudować dwuczęściowy wykres G (D ∪ C, E), gdzie D ∪ C jest zbiorem wierzchołków, a E jest zbiorem krawędzi między D i C.

(d, c) jest w E tylko wtedy, gdy kropka d należy do kategorii c.

Następnie jesteś zainteresowany znalezieniem maksymalne dopasowanie dwudzielne na tym wykresie.

Ponieważ wykres jest dwuczęściowy, może być rozwiązany przez dobrze znany Algorytm Hopcrofta-Karpa

Jeśli liczność obliczonego maksymalnego dopasowania jest równa wielkości C, wtedy można dopasować każdą kategorię do innej kropki, a to dopasowanie opisuje to przypisywanie.


3
2017-08-23 20:34