Przypisanie numeru

Biorąc pod uwagę liczb tak, że istnieje przypisanie liczb który jest permutacją taki, że $k$ $A_1 \leq A_2 \leq ... \leq A_k$ $\sum\limits_{i=1}^k A_i = k(2k + 1)$ $i_1, i_2, ... , i_{2k}$ $1, 2, ... , 2k$

$i_1 + i_2 \leq A_1\\ i_3 + i_4 \leq A_2\\ .\\.\\.\\ i_{2k-1} + i_{2k} \leq A_k$

Nie mogę znaleźć wydajnego algorytmu, który rozwiązuje ten problem. Wydaje się, że jest to problem kombinatoryczny. Nie udało mi się znaleźć podobnego problemu z NP-Complete. Czy ten problem wygląda jak znany problem NP-Complete, czy można go rozwiązać za pomocą algorytmu wielomianowego?

np-complete decision-problem

— gprime
źródło

Czy poczyniłeś jakieś postępy w sprawie problemu?

— Yuval Filmus

Zapomniałem wspomnieć, że

A_{1} \leq A_{2} \leq . . . \leq A_{k}

$A_1 \leq A_2 \leq ... \leq A_k$

— gprime

Powiązany problem , również bez zadowalającej odpowiedzi. (Na pierwszy rzut oka może nie być jasne, w jaki sposób są ze sobą powiązane, ale jeśli

, problem jest równoznaczny ze znalezieniem permutacji

więc

K = 2 N

$K=2N$

1 \dots 2 N

$1 \ldots 2N$

i_{2 a - 1} - i_{2 a} = A_{i}

$i_{2a-1} - i_{2a} = A_i$

— Peter Shor

Odpowiedzi:

Ten problem jest całkowicie NP.

Załóżmy, że wszystkie są dziwne. Wiemy zatem, że skoro jest nieparzysta, jeden z i jest parzysty, a drugi jest nieparzysty. Możemy założyć, że jest nieparzysta, a jest parzysta. Pozwalając $A_j$ $i_{2j-1} + i_{2j} = A_j$ $i_{2j-1}$ $i_{2j}$ $i_{2j-1}$ $i_{2j}$ i $\pi_j = \frac{1}{2}(i_{2j-1}+1)$ , możemy pokazać, że jest to równoważne z prośbą o dwie permutacje,i, liczbtakich, że $\sigma_j = \frac{1}{2}(i_{2j})$ $\pi$ $\sigma$ $1 \ldots n$ . $\pi_j + \sigma_j = \frac{1}{2}(A_j+1)$

Ten problem jest znany jako NP-zupełny; zobacz ten problem z cstheory.se oraz artykuł W. Yu, H. Hoogeveen i JK Lenstry, do których odwołuje się odpowiedź.

— Peter Shor
źródło

Oto wskazówka na początek: ponieważ suma wszystkich liczb od do wynosi dokładnie , rozwiązanie jest możliwe tylko wtedy, gdy w rzeczywistości , i tak dalej. Tak więc biorąc pod uwagę wiemy , i tak dalej. Również . $1$ $2k$ $k(2k+1)$ $i_1 + i_2 = A_1$ $i_3 + i_4 = A_2$ $i_1$ $i_2$ $3 \leq A_j \leq 4k-1$

— Yuval Filmus
źródło

Jak więc wybrać

na początek? Nie widzę rozwiązania. Ale dzięki za właściwość

i_{1}

$i_1$

3 \leq A_{j} \leq 4 k - 1

$3 \leq A_j \leq 4k -1$

— gprime

Jeśli

są posortowane, wiemy, że

i tak dalej. Czy te kryteria wraz z

wystarczą? Jeśli tak, być może istnieje prosty algorytm dla tego problemu.

A_{i}

$A_i$

3 \leq A_{1}

$3 \leq A_1$

10 \leq A_{1} + A_{2}

$10 \leq A_1 + A_2$

21 \leq A_{1} + A_{2} + A_{3}

$21 \leq A_1 + A_2 + A_3$

\sum_{i} A_{i} = k (2 k + 1)

$\sum_i A_i = k(2k+1)$

— Peter Shor

Tak, są posortowane. Spróbuję użyć tego ...

— gprime

@PeterShor Musisz także wziąć pod uwagę granice z przeciwnego kierunku, tj.

, i tak dalej i tak dalej. Patrząc na problem anegdotycznie, wydaje się, że prosty, zachłanny algorytm powinien odkryć rozwiązania, gdy istnieją, i zawieść dokładnie, gdy nie istnieją - ale mam problem z udowodnieniem tego.

4 n - 1 \geq A_{n}, 8 n - 6 \geq A_{n - 1} + A_{n}

$4n-1 \geq A_n, 8n-6 \geq A_{n-1}+A_{n}$

— torquestomp

@torquestomp: Podnosisz dobry punkt. W rzeczywistości ograniczenia z jednego kierunku oznaczają także ograniczenia z drugiego, ale na pierwszy rzut oka wcale nie jest to oczywiste. Patrzyłem na podobny problem i nie mogłem wymyślić prostego algorytmu (ale dla mnie również wyglądało na to, że analog tych kryteriów był wystarczający).

— Peter Shor

Jest to pasujący problem, dlatego można go rozwiązać za pomocą algorytmu Edmonda. Zobacz wikipedia

— Będzie
źródło

Pomysł Stackexchange polega na zadaniu pytań i odpowiedzi, które są możliwie kompletne. Czy byłbyś w stanie rozwinąć swoją odpowiedź, aby była czymś więcej niż tylko linkiem do wikipedii?

— Luke Mathieson

Czy możesz rozwinąć? Nie rozumiem, jak mogę użyć tych algorytmów do rozwiązania mojego pytania.

— gprime

Właściwie dla mnie wygląda to na specjalny przypadek dopasowania 3, który jest NP-zupełny. Nie oznacza to, że problem PO jest kompletny.

— Peter Shor

Czy to może być dopasowanie dwustronne? Przyjrzę się dopasowaniu 3, aby zobaczyć, czy mogę to rozgryźć. Dzięki!

— gprime