Schnellere Pseudo-Polynom-Zeitalgorithmen für PARTITION

Ich möchte N gegebene Zahlen (kann gleich sein oder nicht) in 2 Teilmengen aufteilen, so dass die 2 Teilmengen eine möglichst nahe Summe haben und auch die Kardinalität der Mengen gleich ist (wenn n gerade ist) oder sich nur um 1 unterscheidet ( wenn n ungerade ist).

Ich denke, wir können dies in der Pseudopolynomzeit tun , wobei die Summe der Zahlen in der Menge ist. $O(n^2 A)$ $A$

Kann ich es besser machen? Gibt es nämlich einen Pseudo-Polynom-Zeitalgorithmus, der in der Zeit mit läuft ? $O(n^c A)$ $c < 2$

Danke im Voraus!

ds.algorithms co.combinatorics partition-problem Firebrandt
quelle

Beachten Sie, dass Knapsack als Sonderfall über ein FPTAS verfügt . Siehe zB ELLawler. Schnelle Approximationsalgorithmen für Rucksackprobleme .

Mathieu Chapelle

@Oleksandr, besser gemeint ist, dass es einen Pseudo-Polynom-Algorithmus gibt, der in O (nA) läuft. Entschuldigung, dass ich nicht in Latex posten kann.

Firebrandt

Ich befürchte, dass diese Frage an der Grenze zu elementar ist. Beispiel: "Ist das Partitionsproblem mit der zusätzlichen Einschränkung, dass die beiden Sätze die gleiche Kardinalität haben müssen, immer noch NP-vollständig?" kann eine typische Hausaufgabenfrage sein, und ich befürchte, dass das Aufschreiben der Antwort negative Auswirkungen auf einige Kurse in Bezug auf die Komplexität der Berechnungen haben kann.

Tsuyoshi Ito

Wie ist das zu elementar? Der offensichtliche Ansatz ergibt , und die Frage ist, ob es einen besseren Algorithmus gibt, der in der Zeit läuft, wobei . Ich vermute, dass dies eine offene Frage ist.

O (n^{2} A)

$O(n^2A)$

O (n^{c} A)

$O(n^c A)$

c < 2

$c < 2$

Peter Shor

@Firebrandt: Ich habe mir erlaubt, Ihre ursprüngliche Frage zu bearbeiten, um meine Version Ihrer Klarstellung hinzuzufügen (Ändern von in mit , da ich denke, dass dies wahrscheinlich eine offene Frage ist). Sie können es wieder in ändern, wenn Sie möchten. Ich denke, die Frage, die durch Ihre Kommentare geklärt wird, ist eindeutig auf Forschungsebene.

O (n A)

$O(nA)$

O (n^{c} A)

$O(n^cA)$

c < 2

$c<2$

O (n A)

$O(nA)$

Peter Shor

Antworten:

Man kann das Entscheidungsproblem in Zeit lösen . $\tilde{O}(nA)$

Lassen Sie die Reihenfolge der Zahlen . Definieren Sie als eine Menge, so dass wenn eine Teilfolge von der Länge , die sich zu summiert . Wenn wir berechnet haben , benötigen wir nur zusätzliche Zeit, um gründlich zu durchlaufen und Ihr Problem zu lösen. $S$ $F_S$ $(i,j)\in F_S$ $S$ $j$ $i$ $F_S$ $O(nA)$ $F_S$

Wenn und zwei sind, die partitionieren , dann $S_1$ $S_2$ $S$

F_{S} = F_{S_{1}} + F_{S_{2}}

$F_S = F_{S_1} + F_{S_2}$

wobei ist die Minkowski-Summe, und die Addition zwischen Tupeln wird koordinatenweise definiert. $A+B=\{a+b | a\in A, b\in B\}$

Behauptung: Die Berechnung von aus und dauert . $F_S$ $F_{S_1}$ $F_{S_2}$ $\tilde{O}(|S|A)$

Beweis: Wenden Sie die 2D-Faltung auf zwei Tabellen der Größe. $A\times |S|$

Der Algorithmus unterteilt die Sequenz in zwei gleich große Sequenzen, wendet jeweils eine Rekursion an und nimmt die Minkowski-Summe des Ergebnisses. Sei die Laufzeit im ungünstigsten Fall, wenn die Eingabe in den Algorithmus Elemente enthält und eine Obergrenze der Summe ist. Wir haben was . $T_A(n)$ $n$ $A$

T_{A} (n) = 2 T_{A} (n / 2) + A \tilde{O} (n)

$T_A(n) = 2 T_A(n/2) + A \tilde{O}(n)$

T_{A} (n) = \tilde{O} (n A)

$T_A(n) = \tilde{O}(n A)$

Der versteckte Faktor ist . $\log$ $\log n \log nA$

Chao Xu
quelle

Wenn sich jemand um die Faktoren kümmert , können wir durch sorgfältige Analyse nachweisen, dass die zeitliche Komplexität für Chaos Algorithmus . $\log$ $O(nA\log(nA))$

Beweis. In der geraden Schicht des Rekursionsbaums teilen wir die Menge in zwei gleich große Mengen und , was und auf der ungeraden Schicht des Rekursionsbaums teilen wir die Menge in zwei "gleich summierte" Mengen und . Um genau zu sein, können wir eine Menge mit der Summe in zwei Mengen und wobei jede von ihnen eine Summe von ergibt , wobei höchstens ein Element übrig bleibt. Wir können dieses Element mit trivialer dynamischer Programmierung in $S$ $S_1$ $S_2$

T_{e} (n, A) = T_{o} (n / 2, A^{'}) + T_{o} (n / 2, A - A^{'}) + O (n A \log (n A)),

$T_e(n,A)=T_o(n/2,A')+T_o(n/2,A-A')+O(nA\log(nA)),$

S

$S$

S_{1}

$S_1$

S_{2}

$S_2$

S

$S$

A

$A$

S_{1}

$S_1$

S_{2}

$S_2$

\leq A / 2

$\leq A/2$

O (A)

$O(A)$ . Dies ergibt wobei. Daher haben wir wobei , und . Dies ergibt .

T_{o} (n, A) = T_{e} (n_{1}, A / 2) + T_{e} (n - n_{1}, A / 2) + O (n A \log (n A)),

$T_o(n,A)=T_e(n_1,A/2)+T_e(n-n_1,A/2)+O(nA\log(nA)),$

n_{1} = | S_{1} |

$n_1=|S_1|$

T (n, A) \leq \sum_{i = 1}^{4} T (n_{i}, A_{i}) + O (n A \log (n A)),

$T(n,A)\leq \sum_{i=1}^4T(n_i,A_i)+O(nA\log(nA)),$

\sum_{i = 1}^{4} n_{i} \leq n

$\sum_{i=1}^4n_i\leq n$

\sum_{i = 1}^{4} A_{i} \leq A

$\sum_{i=1}^4A_i\leq A$

\forall i, n_{i} \leq n / 2, A_{i} \leq A / 2

$\forall i,~n_i\leq n/2,~A_i\leq A/2$

T (n, A) = O (n A \log (n A))

$T(n,A)=O(nA\log(nA))$

hqztrue
quelle