Zeitfensterblöcke verkaufen

Angesichts von Zeitfenstern, die Leute kaufen wollen. Person hat für jedes Zeitfenster einen Wert $n$ $k$ $i$ $h(i,j)\geq 0$ $j$ . Jede Person kann nur einen aufeinanderfolgenden Zeitfensterblock kaufen, der leer sein kann.

Gibt es einen Polynom-Zeit-Algorithmus , um den maximalen Wert zu berechnen, den der Verkäufer erreichen kann?

Ohne die Konsekutivitätsbeschränkung können wir jeden Zeitschlitz der Person zuweisen, die ihn am meisten schätzt. Wenn wir die Reihenfolge der Zeitschlitze der Personen festlegen, kann die dynamische Programmierung verwendet werden, um den Maximalwert der ersten Personen zu ermitteln, die die ersten Zeitschlitze kaufen . $k$ $0\le i \le k$ $0\le j \le n$

algorithms optimization np-hard scheduling user11550
quelle

Antworten:

Gegeben ein 3CNF mit Klauseln für Variablen . Angenommen , sowohl und in der Formel erscheinen für höchstens mal jeweils. $\phi_1,\ldots,\phi_k$ $x_1,\ldots,x_n$ $x_i$ $\overline{x_i}$ $k_i$

Wir entwerfen einen farbigen DAG dessen Eckpunkte aus drei Teilen bestehen: $G$

"Zuordnung" Eckpunkten und , , . Farbe mit der "Farbe" und mit . $v_i(j)$ $\bar{v}_i(j)$ $1\leq i\leq n$ $1\leq j\leq k_i$ $v_i(j)$ $x_i(j)$ $\bar{v}_i(j)$ $\overline{x_i}(j)$
"Klausel" -Scheitelpunkte , , . Farb mit der Farbe (oder ) , wenn (oder , resp.) Ist die $w_{i'}(j')$ $1\leq i'\leq k$ $j'=1,2,3$ $w_{i'}(j')$ $x_i(j)$ $\overline{x_i}(j)$ $\overline{x_i}$ $x_i$ $j'$ -te Literal von Klausel , und es ist die -te Klausel, die dieses Literal enthält. $\phi_{i'}$ $j$
"Schneide" Eckpunkte . Färben Sie sie mit anderen Farben als oben. $s=s_0,s_1,\ldots,s_n, s_{n+1},\ldots s_{n+k}=t$

Die Kanten umfassen:

, , ; $s_{i-1}v_i(1)$ $v_i(j)v_i(j+1)$ $v_i(k_i)s_i$
, , ; $s_{i-1}\bar{v}_i(1)$ $\bar{v}_i(j)\bar{v}_i(j+1)$ $\bar{v}_i(k_i)s_i$
und , . $s_{n+i'-1}w_{i'}(j')$ $w_{i'}(j')s_{n+i'}$

Zum Beispiel aus dem 3CNF Das folgende Diagramm aufgebaut ist (die Kantenrichtung von links nach rechts) ist. $(x_1 \vee x_2 \vee \overline{x_3})\wedge(x_1 \vee \overline{x_2}\vee x_3)$

Nun ist es nicht schwer zu erkennen, dass der ursprüngliche 3CNF genau dann zufriedenstellend ist, wenn es in einen - - Pfad mit verschiedenen Scheitelfarben gibt . $s$ $t$ $G$

(Übrigens ist es ein Nebenprodukt, dass das Vorhandensein von - path mit verschiedenen Scheitelfarben in farbiger DAG . Ich habe in rechnerischer Hinsicht nicht viele Literatur zu diesem Problem gefunden. Wenn Sie wissen, bitte Kommentar!) $s$ $t$ $\textsf{NP-hard}$

Wie ist also die Beziehung zwischen dem Problem von und OP? Intuitiv werden wir eine Matrix entwerfen , so dass jede Farbe einer Zeile (die eine Person ist) und die Kanten aufeinanderfolgenden Spalten (Zeitschlitzen) zugeordnet werden. Eine maximale Einteilung, die in der Matrix grundsätzlich von links nach rechts verläuft, entspricht daher einem - - Pfad. $G$ $h$ $s$ $t$

Unsere Matrix hat Spalten mit Indizes ab . In der folgenden constrcution ein sind zwei Werte erfüllen . Die Verhältnisse können große Potenzen von und . Sei $h$ $2n+1+\sum_i 2k_i+k$ $0$ $X$ $Y$ $1\ll X\ll Y$ $X/1, Y/X$ $k$ $n$ . $K_i=2i+2\sum_{j=1}^i k_i$

Für jeden , , lassen (falls die Koordinate existiert, siehe unten). $s_i$ $0\leq i\leq n$ $h(s_i,K_i)=h(s_i,K_i-k_i-1)=h(s_i,K_i+k_{i+1}+1)=Y$
Für jedes sei ; Für jede sei . $x_i(j)$ $h(x_i(j),K_{i-1}+j)=X$ $\overline{x_i}(j)$ $h(\overline{x_i}(j),K_{i-1}+k_i+1+j)=X$
Für jedes , und ein Literal in der Klausel sei . $\phi_{i'}$ $1\leq i'\leq k$ $x$ $\phi_{i'}$ $h(x,K_n+i')=1$
Alle anderen Einträge sind 0.

Für das obige Beispieldiagramm lautet die entsprechende Matrix beispielsweise

Nun behaupten wir: Der ursprüngliche 3CNF ist genau dann erfüllbar, wenn der Maximalwert . $(2n+1)Y+\sum_i k_iX+k$

Berücksichtigen Sie die Planung, die den Maximalwert erreicht. Da es in genau Spalten gibt, die enthalten , sollten alle abgedeckt werden. Nehmen wir für die Spalte die zwei Möglichkeiten von , an, dass die Planung sie zuweist . Da Spalte zu zugeordnet werden muss, müssen wir durch die Aufeinanderfolge die Spalten zu verlieren $(2n+1)$ $h$ $Y$ $K_i+k_i+1$ $Y$ $s_i$ $K_i$ $s_i$ $K_i+1$ . Die gleichen Dinge passieren, wenn die Planung die Spalte zu . $K_i+k_i$ $K_i+k_i+1$ $s_{i+1}$

Um den Wert , müssen wir daher alle übrigen verfügbaren in der Matrix auswählen , was einer Zuweisung für Variablen entspricht. Der Restwert von ist also nur dann erreichbar, wenn die Zuweisung alle Klauseln erfüllt. $\sum_i k_iX$ $X$ $k$

Zusammenfassend lässt sich sagen, dass die Entscheidung über den Maximalwert einer gesetzlichen Terminplanung in fällt . Vielleicht ist dies der Grund, warum alle unsere vorherigen Versuche, einen Algorithmus zu finden, fehlgeschlagen sind. $\textsf{NP-hard}$

Willard Zhan
quelle

Aber wenn ich in der Beispielmatrix

und

wähle, komme ich immer noch zum Ziel. Was mache ich falsch? Außerdem sollte das

eine Spalte rechts und das

eine Spalte links sein

\bar{x_{1}}

$\overline{x_1}$

\bar{x_{2}}

$\overline{x_2}$

x_{3}

${x_3}$

X

$X$

\bar{x_{1}} (1)

$\overline{x_1}(1)$

X

$X$

\bar{x_{1}} (2)

$\overline{x_1}(2)$

rotia

@rotia Ja, und das bedeutet, dass Sie auf der linken Seite

auswählen müssen, um

zu haben . Das entspricht also einer zufriedenstellenden Zuordnung

x_{1}, x_{2}, \bar{x_{3}}

$x_1,x_2,\overline{x_3}$

4 X

$4X$

x_{1} = x_{2} = 1, x_{3} = 0

$x_1=x_2=1,x_3=0$

Willard Zhan

Können Sie erklären, was "Angenommen,

größer als eins in den beiden Auftrittszahlen der Literale

und

." meint? Wie oft erscheint ein Literal? Entspricht das der Position, an der es in den Klauseln / Formeln vorkommt, oder wie oft es in der Formel vorkommt? Ist

ein Literal oder eine Zahl?

k_{i}

$k_i$

x_{i}

$x_i$

\bar{x_{i}}

$\overline{x_i}$

k_{i}

$k_i$

@ DW

ist eine Zahl. Mein Ausdruck war in der Tat nicht ganz klar; Ich habe es bearbeitet.

k_{i}

$k_i$

Willard Zhan

@ WillardZhan Ja. Aber wenn ich diese Variablen auswähle, kann ich zu einem Wert gelangen, der größer ist als der in der Formel. Zum Beispiel setze ich

und

, gemäß der Formel sollte ich nur auf 450 Punkte kommen (vorausgesetzt

ist die Anzahl der Klauseln). Aber wenn ich

wähle

ich 452 Punkte, indem ich die vier rechts

Y = 60

$Y = 60$

X = 7

$X = 7$

k

$k$

x_{1}, x_{2}, \bar{x_{3}}

$x_1,x_2,\overline{x_3}$

auswähle

Diese Lösung hat Probleme und wird in Kürze gelöscht. Siehe templatetypedefs Kommentar.

Sie können dies in polynomialer Zeit mit minimalem Kostenfluss lösen . Im Folgenden haben alle Kanten die Einheitenkapazität.

Erstellen Sie einen Quellscheitelpunkt und einen Zielscheitelpunkt . Wir senden Durchflusseinheiten von nach . $s$ $t$ $k$ $s$ $t$
Erstellen Sie Eckpunkte , um die Zeitpunkte zwischen Schlitzen und einer gerichteten Kante für jeweils mit den Kosten 0 darzustellen . $n+1$ $v_0, \dots, v_n$ $v_jv_{j+1}$ $0 \le j < n$
Erstellen Sie für jede Person Folgendes:
- Ein Unterquellenscheitelpunkt und ein Untersenkenscheitelpunkt . $s_i$ $t_i$
- Für jedes , eine Kante von bis mit Kosten (die wir nehmen zu 0 , wenn ). $0 \le j < n$ $s_i$ $v_j$ $\Sigma_{k=1}^j{h(i,k)}$ $j=0$
- Für jede ist eine Kante von zu mit Kosten . $1 \le j \le n$ $v_j$ $t_i$ $-\Sigma_{k=1}^j{h(i,k)}$
- Eine Kante mit Kosten 0. $ss_i$
- Eine Kante mit Kosten 0. $t_it$

Ein Mindestkostenfluss in diesem Netzwerk hat Gesamtkosten in Höhe des Negativs des bestmöglichen Gewinns. (Diese Kosten sind negativ, aber das ist kein Problem.) Es gibt eine optimale integrale Lösung, bei der jede Person, für die eine einzelne Kante habe, mit einem Fluss von 1 verlässt und eine einzelne Kante bei mit einem Fluss von 1 ankommt und alle anderen Kanten trifft auf entweder oder 0 Fluss haben. Lassen Sie diese Fluss-1-Kanten für Person sein und : dann $i$ $s_i$ $t_i$ $s_i$ $t_i$ $i$ $s_iv_j$ $v_kt_i$ $k \ge j$ , da die einzigen Pfade unter Vertices diejenigen sind, die den Index erhöhen. Wenn , dann wird der Person kein Zeitschlitz zugewiesen; andernfalls wird der Person der Block von Zeitschlitzen zugewiesen . $v$ $k = j$ $i$ $i$ $j+1, \dots, k$

Intuitiv "bekommt" jede Person 1 Durchflusseinheit von und wählt eine Startzeit (Flanke) und eine Endzeit (Flanke); Diese Start- und Endkanten sind die einzigen Kanten mit Kosten ungleich Null im Netzwerk, und wir können den Wert eines Blocks als Differenz zweier Präfixsummen darstellen. Die Einheitenkapazitäten an den Kanten zwischen den Vertices verhindern, dass 2 Personen den gleichen Zeitschlitz verwenden. $s$ $j+1, \dots, k$ $v$

Interessanterweise funktioniert diese Formulierung auch dann, wenn die Werte negativ sein können. $h(i, j)$

j_random_hacker
quelle

Könnte dieses fehlschlagen , wenn irgendeine Person

eine Route von der Quelle nimmt an einem anderen Person der Spüle und umgekehrt?

i

$i$

Templatetypedef

@ templatetypedef: Ich glaube, du hast recht; Ich werde diese Antwort in Kürze löschen. Was ist stattdessen mit dieser Konstruktion: Wir haben die gleichen Eckpunkte und Kanten wie zuvor, aber jetzt versuchen wir, eine einzelne Flusseinheit durch eine "Pipeline" von Personen (geordnet nach Erhöhung des

Werts) zu "fädeln", indem wir alle Kanten

löschen mit Ausnahme von

und allen Kanten

Ausnahme von

und Hinzufügen einer Kante

mit großen negativen Kosten

für jede

i

$i$

s s_{i}

$ss_i$

s s_{1}

$ss_1$

t_{i} t

$t_it$

t_{k} t

$t_kt$

t_{i} s_{i + 1}

$t_is_{i+1}$

- M

$-M$

1 \leq i < k

$1 \le i < k$ . Die

zwingen die einzelne Durchflusseinheit, alle

dieser "Pipeline" -Kanten in jeder optimalen Lösung zu besuchen .

- M

$-M$

k - 1

$k-1$

j_random_hacker

@j_random_hacker dann erzwingen Sie eine Bestellung der

Personen.

k

$k$

Chao Xu

@ChaoXu: Ich glaube nicht: in jeder Zuordnung von Blöcken zu den Menschen, die Zuordnung kann aufgeführt werden , um von Person zu erhöhen. (Beachten Sie, dass nichts verbietet, dass einer Person

ein Block zugewiesen wird, der mit

endet , wobei

der erste Block ist, der der Person

zugewiesen wird .) Ich habe jedoch das Gefühl, ein enger Verwandter des Problems zu sein, das meine erste betroffen hat Versuch betrifft auch dieses ...

i^{'} > i

$i' > i$

j^{'} < j

$j' < j$

j

$j$

i

$i$

j_random_hacker

@j_random_hacker Die Kosten von

würden erfordern, dass

die

te Person in der optimalen Lösung ist.

s_{i} v_{j}

$s_iv_j$

s_{i}

$s_i$

i

$i$

Chao Xu