Dynamischer Programmieralgorithmus für ungewichtete Intervallplanung?

Question

Ich fragte mich, ob jemand mir helfen könnte, über einen DP-Algorithmus für die ungewichtete Intervallplanung zu urteilen.

Ich habe 2 Arrays [t1, ..., tn] und [d1, ..., dn] gegeben, wobei ti die Startzeit von Job i und di die Dauer von Job i ist. Auch die Jobs sind nach Startzeit sortiert, also t1 < = t2 < = ... < = tn. Ich muss die Anzahl der Jobs maximieren, die ohne Überlappungen ausgeführt werden können. Ich versuche, einen DP-Algorithmus und Laufzeit für dieses Problem zu finden. Jede Hilfe würde sehr geschätzt werden!

Vielen Dank!

Answer 1

Es tut mir leid, ich habe jetzt keine Zeit mehr für dieses Problem. Hier ist eine Idee, ich denke, sie eignet sich gut für die dynamische Programmierung. [Eigentlich finde ich es DP ist, aber fast zwei Jahrzehnte sind vergangen, seit ich das letzte Mal solche Dinge studiert ...]

Angenommen T = {t1, t2, ..., tn} unterteilt sich wie folgt:

T = {t1, t2, ..., tn} = {t1, t2, ..., tk} U {tk+1, tk+2, ..., tn} 
    = T1(k) U T2(k) 

T2'(k) die Teilmenge von Let T2(k)nicht enthalten die Jobs überlappen T1(k).

Lassen Sie opt(X) den optimalen Wert für eine Teilmenge X von T sein. Dann

opt(T) = min(opt(T1(k)) + opt(T2'(k)) 

wo das Minimum an jeder möglichen k in {1, 2, ..., n}

Natürlich genommen müssen Sie opt() rekursiv berechnen und zu berücksichtigen Überschneidungen nehmen.

Hoffe, das hilft!

Answer 2

Es ist am einfachsten für mich, wenn ich denke, dass Sie erarbeiten, wie die Endzeit für jeden Job wäre und sortieren Sie die Aufträge in der Reihenfolge der zunehmenden Endzeit, obwohl Sie wahrscheinlich die gleiche Sache mit Startzeiten arbeiten können In die andere Richtung.

Betrachten Sie jeden Job in der Reihenfolge der zunehmenden Endzeit. Berechnen Sie für jeden Job die maximale Anzahl von Jobs, die Sie bis zu und einschließlich des Jobs bearbeiten können, wenn Sie sich für die Arbeit an diesem Job entscheiden. Um dies herauszufinden, sehen Sie sich die Antworten an, die Sie bereits berechnet haben und die Zeiten bis zur Startzeit dieses Jobs abdecken, und finden Sie denjenigen, der die maximale Anzahl von Jobs abdeckt. Das Beste, was Sie tun können, während Sie den Job bearbeiten, den Sie in Betracht ziehen, ist eine plus die maximale Anzahl.

Wenn Sie alle Aufträge berücksichtigt haben, ist die maximale Anzahl, die Sie abdecken können, die maximale Anzahl, die Sie bei der Prüfung eines Auftrags berechnet haben. Sie können herausfinden, welche Aufgaben ausgeführt werden, indem Sie den vorherigen Job speichern, den Sie identifiziert haben, wenn Sie die maximale Punktzahl für einen bestimmten Job berechnen und diese Zeiger dann mit dem maximalen Ergebnis vom Job zurückverfolgen.

Mit N Jobs, die Sie bei höchstens N zuvor berechneten Antworten zurückblicken zu berücksichtigen, wenn für jeden Auftrag die bestmögliche Punktzahl Ausarbeiten so dass ich denke, das ist O (N^2)