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:

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)$$V$$E$

$E$$V$

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.

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.

$x\to y$$x$$y$$y$$z$

Rozwiązanie:

1. $x$$x_L$$x_R$$x_L\to x_R$$x\to y$$x_L\to y_R$

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 .

$1$$-1$

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)$$0$$-E$$E$$O(VE^2)$

To nie jest najszybszy znany algorytm.

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

$C$$n$$\{(v_1, v_2),\dots,(v_n,v_1)\}$$C_1$$C_2$$n-1$$C$

$C$$n$$C_1$$C_2$

$C_1$$C_2$$2(n-1)=2n-2$

$\lfloor\frac{n}{2}\rfloor$

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