Jak znaleźć cykle, które razem obejmują największą liczbę nieudostępnionych krawędzi na ukierunkowanym wykresie?

26

Nie jestem teoretykiem informatyki, ale myślę, że ten problem ze światem rzeczywistym należy tutaj.

Problem

Moja firma ma kilka jednostek w całym kraju.

Zaoferowaliśmy pracownikom możliwość pracy na innej jednostce. Ale jest warunek: łączna liczba pracowników w jednostce nie może się zmienić.

Oznacza to: Pozwolimy pracownikowi opuścić jego jednostkę, jeśli ktoś chce jego miejsce.

Przykładowe (fikcyjne) dane żądania:

Name            Origin    Destination
Maria              1  ->  2
Marcos             2  ->  3
Jones              3  ->  4
Terry              4  ->  5
Joe                5  ->  6
Rodrigo            6  ->  1
Barbara            6  ->  1
Marylin            1  ->  4
Brown              4  ->  6
Benjamin           1  ->  3
Lucas              4  ->  1

Powyższe, wykreślone: Wizualizacja powyższych danych

Zobacz, jak musimy wybierać między opcjami czerwonym, niebieskim lub czarnym?

Prawdziwy problem jest nieco bardziej złożony, ponieważ mamy 27 jednostek i 751 żądań. Proszę spojrzeć na wizualizację

Cel

Po zebraniu wszystkich wniosków, jak zaspokoić większość z nich?

Aplikacja teorii (?)

G(V,E)VE

EV

Pytanie

Jeśli ten problem jest wyrażony jako

„Jak znaleźć cykle, które łącznie obejmują największą liczbę nieudostępnionych krawędzi na ukierunkowanym wykresie”?

Czy zadowolimy większość wnioskodawców?

Czy to prawda, istnieje algorytm pozwalający znaleźć ten optymalny zestaw cykli?

Czy to podejście Greddy rozwiąże problem?

  1. G
  2. G
  3. G

Możesz mi pomóc?

Czy znasz inny sposób na opisanie pierwotnego problemu (uszczęśliwienie większości osób zgłaszających żądanie)?

Edycja : zmieniono dział na jednostkę, aby lepiej opisać problem.

motobói
źródło
3
Czy na pewno chcesz po prostu uniknąć korzystania z tej samej krawędzi więcej niż raz? Z opisu aplikacji uważam, że powinieneś unikać używania tego samego wierzchołka więcej niż raz, co jest silniejszym warunkiem.
Tsuyoshi Ito,
3
@TsuyoshiIto: Jak rozumiem z opisu, warunkiem jest, aby w każdym wierzchołku stopień niezależny był równy poziomowi przejściowemu. Zatem rozłączność wierzchołków nie jest potrzebna.
Yoshio Okamoto,
7
Nawiasem mówiąc, jeśli moje rozumowanie jest poprawne, problem powinien zostać rozwiązany w czasie wielomianowym za pomocą przepływu sieci. Mianowicie, jeśli damy jednostkę zysku za jednostkę przepływu wzdłuż krawędzi i damy jednostkową pojemność na każdej krawędzi, problemem jest znalezienie obiegu maksymalnego zysku.
Yoshio Okamoto,
3
W tym poście omówiono uogólnienie problemu okasaki.blogspot.co.uk/2008/03/what-heck-is-math-trade.html (pomyśl o każdej osobie, która ma jeden przedmiot do wymiany, a mianowicie o miejscu pracy).
Radu GRIGore,
4
Niesamowite pytanie sprawia, że ​​czujemy, że to, co robimy, może być naprawdę wykorzystane w prawdziwym życiu :).
Gopi,

Odpowiedzi:

9

OK, przeczytałem kod TradeMaximizer i uważam, że rozwiązuje on następujący, bardziej ogólny problem.

PROBLEM: Podany jest ukierunkowany wykres, którego łuki mają koszty. Znajdź zestaw cykli rozłącznych wierzchołków, który najpierw maksymalizuje liczbę pokrywanych wierzchołków i drugi minimalizuje całkowity koszt.

xyxyyz

Rozwiązanie:

  1. xxLxRxLxRxyxLyR

  2. Znajdź idealne dopasowanie minimalnego kosztu na wykresie dwustronnym.

>1

(W rzeczywistości TradeMaximizer dokonuje iteracji we wszystkich optymalnych rozwiązaniach, zgodnie z dwoma powyższymi kryteriami, w celu heurystycznej optymalizacji innych rzeczy, takich jak długość największego cyklu. Duże cykle zwiększają szansę, że „umowa” nie przejdzie, ponieważ jedno osoba zmienia zdanie).

PS: Autor, Chris Okasaki, potwierdził, że tak właśnie działa kod, na blogu .

Radu GRIGore
źródło
Udało mi się znaleźć rozwiązanie pierwotnego problemu za pomocą TradeMaximizer. Jutro opublikuję szczegóły.
motobói
@ motobói, ale wszystko, co musisz zrobić, to to, co napisałem w drugim akapicie ...
Radu GRIGore,
Znalazłem wyjaśnienie na temat algorytmu: boardgamegeek.com/wiki/page/TradeMaximizer
motobói
Czy możesz wyjaśnić lub wskazać wyjaśnienie, dlaczego konieczne jest usuwanie łuków między mocnymi połączonymi komponentami?
motobói
@ motobói, Jest to optymalizacja (dla przeciętnego przypadku). Kroki (1) i (2) powinny wystarczyć.
Radu GRIGore
22

11

Ponieważ wszystkie koszty i zdolności są ograniczone stałymi, prosty algorytm anulowania cyklu znajdzie wymagany obieg w czasie wielomianowym. Jest to prawie taki sam jak oczywisty chciwy algorytm:

while G has any negative-cost directed cycles
    γ = arbitrary negative-cost directed cycle
    reverse every edge in γ
    negate the cost of every edge in γ
return the subgraph of reversed edges

O(VE)0EEO(VE2)

To nie jest najszybszy znany algorytm.

Jeffε
źródło
myślicie, że to działa, dopóki osoba nie chce pracować w więcej niż jednej „jednostce”, prawda? używając sformułowania oryginalnego pytania. ale jeśli ludzie chcą pracować w więcej niż jednej jednostce, podejrzewają, że ta abstrakcja się załamuje. OP stwierdził problem w kategoriach tylko jednej jednostki, ale wydaje mi się to raczej sztucznie ograniczające. [co człowiek ma tylko jedną preferencję ...?]
vzn
1
Co to jest „osoba” i „jednostka”? To jest pytanie o wykresy.
Jeffε
Jestem zdziwiony: czy mój przykład nie jest przykładem dla tego algorytmu? Po wybraniu C cykle C_1 i C_2 nie są już cyklami (ponieważ każdy cykl ma jedną odwróconą krawędź); C nie zostanie ponownie użyte, ponieważ ma dodatni koszt po odwróceniu krawędzi i nie wprowadzono żadnych nowych cykli. Czy mówimy o tym samym problemie? Chciałbym mieć matematyczne sformułowanie problemu.
FiB
3
CCC1C2CCC1C2C=C1+C2C
najwyraźniej „jednostka” jest czymś w rodzaju „departamentu”, a użytkownicy rejestrują prośby o przeniesienie między działami [niezupełnie konkretne stanowiska w działach]? Wykres FIB wydaje się mieć jednostki jako wierzchołki i krawędzie jako żądania położenia między jednostkami. FiB - „chciałbym mieć matematyczne sformułowanie problemu” .. to naprawdę zależy od ciebie, aby dostarczyć precyzyjne sformułowanie .. wydajesz się być w połowie drogi ..
wer 16'12
4

To chciwe podejście nie zawsze daje najlepsze rozwiązanie.

Cn{(v1,v2),,(vn,v1)}C1C2n1C

CnC1C2

C1C22(n1)=2n2

n2

Kłamstwo
źródło
-3

prawdopodobnie istnieje sposób / sformułowanie teorii grafów, aby rozwiązać ten problem, ale ten problem brzmi bardziej jak problem permutacji, w którym niektóre ze wszystkich permutacji są odrzucane, a inne są poprawne. permutacje są pracownikami, a stanowiska są „stanowiskami” w firmie. permutacja jest odrzucana, jeśli nie spełnia wymagań „osoba [x] chce pozycji [y]”. rozróżnienie granic jednostek / depts / org jest w tym przypadku nieco zbędne do rozwiązania.

ten typ problemu permutacji z ograniczeniami można łatwo przekształcić w wystąpienie problemu SAT (satysfakcji). przypisania zmiennych boolowskich reprezentują pracowników, a klauzule ograniczeń reprezentują ograniczenia „osoba [x] chce pozycji [y]”. istnieją w pobliżu klasyczne przykłady tego zjawiska, zwykle nazywane problemem „stołu”, w którym masz miejsca siedzące i gości, a nie wszyscy goście chcą siedzieć obok siebie (lub bardzo podobnie niektórzy goście chcą siedzieć obok innych gości).

i oczywiście istnieją wyrafinowane solwery SAT dla dość dużych instancji, obejmujące z grubsza nawet setki zmiennych i klauzul, na PC, a jeśli problem nie jest „trudny”, w tysiącach.

patrz np. [1] w celach zawodowych i [2] w przypadku ćwiczeń w klasie. istnieje również pewne strukturalne podobieństwo do tak zwanych „problemów z szufladami”, które są dobrze badane w kręgach SAT, gdzie gołębie są przypisane do szuflad i masz mniej lub więcej dziur niż gołębie. w takim przypadku gołębie są jednak ogólnie postrzegane jako wymienne. innymi słowy problem ze stołem obiadowym jest jak problem szuflady z silniejszymi ograniczeniami, a goście / gołębie mają wymagane preferencje.

należy oczywiście pamiętać / pamiętać, że w przypadku tego rodzaju problemów, w zależności od ograniczeń, odpowiedzią może być „takie ograniczone rozwiązanie nie istnieje”.

[1] algorytm stołu obiadowego, autor: crato

[2] CS402 princeton HW SAT

[3] Problem satysfakcji, wikipedia

vzn
źródło
Próbowałem permutacji przy użyciu znaku towarowego. Ustaw pracownika jako użytkownik chce handlować jego jednostka X dla jednostki Y . Ale oprogramowanie nie pozwoli na handel tym samym przedmiotem przez więcej niż jednego użytkownika (jego jednostkę). Każdy element musi być unikalny. Aby temu zaradzić, musiałbym powiedzieć, że [(Jones) chce wymienić Unit-C-James na Unit-D-Laura lub Unit-D-Sergio lub Unit-D-Mary]
motobói