Zahlen mit minimalem Unterschied trennen

Gegeben ist eine positive ganze Zahl ganze Zahl und ganze Zahlen mit für jedes . Wie ist es zu entscheiden, ob es ganze Zahlen so dass für alle und für alle ?$n$$a_1,b_1,\dots,a_n,b_n$$a_i\leq b_i$$i$$c_1,\dots,c_n$$a_i\leq c_i\leq b_i$$i$$|c_i-c_j|\geq 2$$i,j$

Was beobachtet werden kann, ist, dass ein gieriger Algorithmus, bei dem wir annehmen, dass und gemäß dieser Reihenfolge wählen , nicht unbedingt funktioniert. Zum Beispiel können wir . Das Setzen von funktioniert nicht (es lässt keinen Platz für ), aber was funktioniert, ist das Setzen von und . Ist das Problem vielleicht NP-schwer?$a_1\leq\dots\leq a_n$$c_i$$a_1=1, b_1=4, a_2=b_2=2$$c_1=1$$c_2$$c_1=4$$c_2=2$

Wie in der vorherigen Antwort gezeigt, kann dieses Problem als Planungsproblem mit Release- und Fälligkeitsterminen modelliert werden. Schrages Heuristik funktioniert jedoch nur für den Fall (alle Verarbeitungszeiten sind ) oder wenn Release- und Fälligkeitstermine übereinstimmen (dh es gibt eine Reihenfolge, in der und ).$p_j=1$$1$$r_1\leq\cdots\leq r_n$$d_1\leq\cdots\leq d_n$

Für den Fall Polynomalgorithmen von Simons (1978) , Carlier (1981) und Garey et al. (1981) , laufend in der Zeit , bzw. .$p_j=p$$O(n^2\log n)$$O(n^2\log n)$$O(n\log n)$

Der Algorithmus von Garey et al. Plant Zeiteinheitenaufgaben, ermöglicht jedoch eine willkürliche Freigabe und Fälligkeitstermine. Das obige Problem kann auf diese Einstellung reduziert werden, indem alle Daten und Verarbeitungszeiten durch . Die Hauptidee des Algorithmus besteht darin, eine Reihe verbotener Regionen zu finden, in denen keine Aufgabe gestartet werden darf. Sie zeigen, dass Schrages Heuristik unter Berücksichtigung verbotener Regionen einen realisierbaren Zeitplan mit minimaler Makespan findet. Bei der Konstruktion der verbotenen Regionen kann ihr Algorithmus auch Unmöglichkeit erkennen.$p$

Um zu sehen, wie der Algorithmus funktioniert, schauen Sie sich zunächst ein einfacheres Problem an: Planen Sie Zeiteinheitenaufgaben zwischen einem Veröffentlichungsdatum und einer Frist verbotenen Regionen , wobei jede Region ist ein offenes Intervall. (Beachten Sie, dass wir uns hier nicht mit der Veröffentlichung und den Fälligkeitsterminen einzelner Aufgaben befassen.)$n$$r$$d$$F=\bigcup_i (a_i,b_i)$$(a_i,b_i)$

Dieses Problem kann durch Backscheduling gelöst werden : Definieren Sie eine Sentinel-Startzeit , und setzen Sie für die Startzeit auf die späteste Zeit spätestens das ist nicht verboten.$s_{n+1}=d$$i=n,n-1,\ldots,1$$s_i$$s_{i+1}-1$

Schreiben Sie für eine Anwendung von Backscheduling für die obigen Eingaben und definieren Sie den Rückgabewert als , das spätestmögliche Startdatum für die Planung der Aufgaben. Wenn nun gibt es keinen realisierbaren Zeitplan für die Aufgaben. Wenn$B(r,d,n,F)$$s_1$$n$$B(r,d,n,F)<r$$n$$r\leq B(r,d,n,F)<r+1$ Keine andere Aufgabe kann beginnen $(B(r,d,n,F)-1,r)$ da sonst gibt es wieder keinen realisierbaren zeitplan für die $n$ Aufgaben und damit $(B(r,d,n,F)-1,r)$ kann als verbotene Region deklariert werden.

Es stellt sich heraus, dass diese Logik ausreicht, um alle verbotenen Regionen zu finden, die für Schrages heuristische Arbeit erforderlich sind. Angenommen, die Aufgaben sind so angeordnet, dass$r_1\leq r_2\leq\cdots\leq r_n$ und schreibe $n(r,d)$ für die Anzahl der Aufgaben, die im geschlossenen Intervall freigegeben und fällig sind $[r,d]$.

1. einstellen $F=\emptyset$
2. für Aufgaben $i=n,n-1,\ldots,1$::
3.   $c=\min \{ B(r_i,d_j,n(r_i,d_j),F) \mid \forall j: d_j\geq d_i\}$
4.   wenn : "kein realisierbarer Zeitplan" zurückgeben$c<r_i$
5.   sonst wenn : setze$r_i\leq c<r_i+1$$F=F\cup\{(c-1,r_i)\}$

Eine einfache Implementierung wie oben würde Zeit . Garey et al. zeigen (neben Korrektheit), die die Zeiten von Backscheduling erhalten durch Aktualisierung, Füge- verbotene Bereiche überlappen, und macht „verboten“ Abfragen Zeit gebracht werden kann , und durch die Verwendung noch bessere Datenstrukturen zu .$O(n^4)$$O(1)$$O(n^2)$$O(n\log n)$

Ihr Problem ist als nicht präventive Einzelmaschinenplanung mit Veröffentlichungszeiten und -fristen mit Aufgaben gleicher Länge bekannt und kann mithilfe der gierigen Heuristik von Schrage effizient gelöst werden.

Lassen Sie uns das Problem zunächst formeller beschreiben. Wir erhalten eine Folge von Zeitintervallen und eine Folge von Auftragslängen . Wir möchten jeden Job innerhalb seines Intervalls planen, damit sich keine zwei Jobs überschneiden.$[r_i,d_i]$$p_i$

In unserem Fall ist , und . Die Startzeit jedes Jobs erfüllt somit , und zwei Jobs stehen in Konflikt, wenn sich überschneidet , was der gleiche ist wie . (Ohne Verlust der Allgemeinheit werden alle Jobs zu ganzzahligen Zeiten geplant.)$r_i = a_i$$d_i = b_i + 2$$p_i = 2$$c_i$$a_i \leq c_i \leq b_i$$(c_i,c_i+2)$$(c_j,c_j+2)$$|c_i - c_j| < 2$

Schrages Heuristik ist eine übliche Heuristik, die in einigen Fällen optimal ist, jedoch nicht unbedingt diese. In der Literatur gibt es jedoch andere Algorithmen, die dieses Problem effizient lösen.

Sei A der kleinste der $a_i$. Dann gibt es zwei Möglichkeiten für die erste$c_i$ Um das auszuwählen, kann es offensichtlich nicht verbessert werden: Erstens, finde das i so, dass $a_i = A$ und $b_i$ ist so klein wie möglich, dann lassen $c_i = a_i$. Zwei, wähle j so, dass$a_j = A+1$, $b_j<b_i$, und $b_j$ so klein wie möglich, dann lassen $c_j=b_j$(Dies ist möglicherweise nicht möglich). Entfernen Sie dann dieses Element aus der Liste der Intervalle und aktualisieren Sie alle$a_i$ um zwei größer sein als die $c_i$ das wurde ausgewählt, und überprüfen Sie, dass nein $b_i$es ist zu klein. Tiefensuche und Rückverfolgung finden eine Lösung.

Es besteht eine gute Chance, dass dies schnell geht, da die erste Wahl als Heuristik nicht schlecht ist.

Wenn es genau k Intervalle mit gibt $a_i < A$ für einige A, und wir finden k Werte $c_i <= A-2$ dann diese $c_i$sind optimal und das Zurückverfolgen für diese k Elemente kann nicht helfen und wird niemals benötigt. Auf der anderen Seite, wenn es zu viele Werte gibt$b_i$ zu nahe beieinander, um zu beweisen, dass es keine Lösung gibt.

Schließlich kann das Problem von klein auf angegangen werden $a_i$oder gleich gut vom größten $b_i$.