Jak skutecznie ustalić, czy dana drabina jest ważna?

W moim lokalnym klubie squasha jest drabina, która działa w następujący sposób.

Na początku sezonu budujemy tabelę z nazwiskiem każdego członka klubu w osobnej linii.
Następnie zapisujemy liczbę wygranych gier i liczbę gier rozegranych przy każdej nazwie (w formie: wygrywa gracz / gry).

Tak więc na początku sezonu stół wygląda następująco:

Carol 0/0
Billy 0/0
Alice 0/0
Daffyd 0/0

Dwoje graczy może rozegrać mecz, a jeden gracz wygra. Jeśli wygrywa gracz znajdujący się najbliżej dolnej krawędzi stołu, pozycja graczy jest zmieniana. Następnie powtarzamy krok 2., aktualizując liczbę wygranych i gier obok każdego gracza. Na przykład, jeśli Alice pokona Billy'ego, mamy

Carol 0/0
Alice 1/1
Billy 0/1
Daffyd 0/0

Mecze te trwają przez cały sezon i ostatecznie powodują, że gracze są umieszczani na liście w przybliżeniu według siły.

Niestety aktualizacja odbywa się w dość przypadkowy sposób, więc popełniane są błędy. Poniżej znajduje się kilka przykładów nieprawidłowych tabel, to znaczy tabel, których nie udało się utworzyć, wykonując powyższe kroki dla pewnej kolejności początkowej (zapomnieliśmy kolejności, którą zastosowaliśmy na początku sezonu) oraz sekwencji meczów i wyników:

Alice 0/1
Billy 1/1
Carol 0/1
Daffyd 0/0

Alice 2/3
Billy 0/1
Carol 0/0
Daffyd 0/0

Alice 1/1
Billy 0/2
Carol 2/2
Daffyd 0/1

Biorąc pod uwagę tabelę, w jaki sposób możemy skutecznie ustalić, czy jest poprawna? Możemy zacząć od odnotowania następujących kwestii:

Kolejność nazw nie ma znaczenia, ponieważ zapomnieliśmy o pierwotnej kolejności początkowej.
Całkowita liczba wygranych powinna wynosić połowę sumy rozegranych gier. (Pokazuje to, że pierwszy przykład powyżej jest nieprawidłowy).
Załóżmy, że tabela jest poprawna. Następnie jest multigraf - wykres uwzględniający wiele krawędzi, ale bez pętli - z każdym wierzchołkiem odpowiadającym graczowi i każdą krawędzią rozegranego meczu. Następnie łączna liczba gier rozegranych przez każdego gracza odpowiada stopniowi wierzchołka gracza w multigrafii. Jeśli więc nie ma multigrafów o odpowiednich stopniach wierzchołków, tabela musi być niepoprawna. Na przykład nie ma multigrafów z jednym wierzchołkiem stopnia pierwszego i jednym stopnia trzeciego, więc drugi przykład jest nieprawidłowy. [Możemy skutecznie sprawdzić, czy istnieje taka multigraf.]

Mamy więc dwie kontrole, które możemy zastosować na początek, ale nadal pozwala to na nieprawidłowe tabele, takie jak trzeci przykład. Aby zobaczyć, że ta tabela jest nieprawidłowa, możemy pracować wstecz, wyczerpując wszystkie możliwe sposoby powstania tabeli.

Zastanawiałem się, czy ktoś może pomyśleć o algorytmie wielomianowym (w liczbie graczy i liczbie gier) rozwiązującym ten problem decyzyjny?

algorithms graphs

— Ben
źródło

Być może istnieje twierdzenie typu Havla Hakimi'ego dla ukierunkowanych multigrafów ...

— Aryabhata

Dlaczego trzeci przykład może być niemożliwy? Co jeśli Alice wygra z Bobem, Carol z Bobem, a Carol z Daffydem. Następnie Alice wygrała 1 z 1 gier, Bob wygrał 0 z 2 gier, Carol wygrała 2 z 2 gier, a Daffyd wygrał 0 z 1 gier?

— utdiscant

utdiscant: Po każdej grze, jeśli wygrywa niższy gracz, gracze są zmieniani. Aby pokazać, że trzeci przykład jest możliwy, musisz podać konfigurację początkową i sekwencję gier - to znaczy z rozkazem - w wyniku podanej tabeli.

— Ben

aryabhata: Dzięki - tak, to byłby użyteczny krok. Niestety, brzmi to dość ciężko ...

— Ben

sugestia do przestudiowania / rozwiązania tego. określ to jako problem SAT. następnie wypróbuj wiele przypadkowych przypadków. sprawdź, czy jakieś są trudne dla standardowego solvera. jeśli nie, być może jest to ograniczony podzbiór w P.

— dniu

Odpowiedzi:

To nie jest pełna odpowiedź. Podaję prostsze stwierdzenie problemu i kilka uwag.

Zaczynamy od wykresu, w którym wierzchołki są oznaczone . $[n]$

$v$ $u$ $label(v)<label(u)$

$G$ $n$ $e$

$\mathsf{NP}$ $G$

Obserwacja

$label(v)$ $v$ $v$

Myślę, że powinno być możliwe połączenie tej obserwacji z Havel-Hakimi w celu uzyskania algorytmu wielomianowego czasu.

— Kaveh
źródło

Cześć. Dziękuję Ci. Czy mógłbyś powtórzyć swoją obserwację w kontekście drabin? Myślę, że istnieje przeciwprzykład dla wykresu rzędu 3, ale być może źle odczytałem.

— Ben

@Ben, myślę, że byłoby to następujące: możesz założyć, że ostatnia osoba na drabinie grała we wszystkie gry, które wygrał na początku turnieju i grała we wszystkie gry, które przegrał pod koniec turnieju . Daj mi znać, jeśli istnieje przeciw-przykład, nie sprawdziłem tego dokładnie.

— Kaveh

Niestety istnieją takie drabiny: A 2/2 B 0/1 C 0/1

— Ben

@Ben, myślę, że przykład jest zgodny z tym, co napisałem, tj. Nie jest kontrprzykładem dla obserwacji.

— Kaveh

Drabina jest ważna. Załóżmy, że ostatnia gra była stratą dla C. Zatem przed ostatnią grą drabina musiała wyglądać następująco: C 0/0 B 0/1 A 1/1, ale ta drabina jest nieważna. Dlatego nie możemy zakładać, że ostatnia gra była porażką dla C.

— Ben

Nie rozwiązałem problemu, ale mam częściowe wyniki, których stwierdzenia podano poniżej. Napiszę dowody, jeśli ktoś jest zainteresowany.

Propozycja . Załóżmy, że drabina (1) zawiera więcej niż jednego gracza (2) zawiera taką samą liczbę wygranych i przegranych; oraz (3) oznacza, że każdy gracz wygrał przynajmniej jedną grę i przegrał przynajmniej jedną grę. Wtedy drabina jest ważna.

$W_i$ $i$ $L_i$ $i$ $R_i$

$L_i=0$

{W.}_{ja} \leq \sum_{k : R_{k} > R_{ja}, {W.}_{k} > 0} ({L.}_{k} - 1)^{+} + \sum_{k : R_{k} < R_{ja}} {L.}_{k},

$W_i \le \sum_{k:R_k > R_i, W_k > 0} (L_k - 1)^+ + \sum_{k:R_k<R_i}L_k,$

L_{i}

$L_i$

W_{i} = 0

$W_i=0$

— Ben
źródło