Wie man einen gierigen Algorithmus benutzt, um die nicht abnehmende Sequenz zu finden, die der gegebenen am nächsten ist?

20

Sie erhalten n ganze Zahlen alle zwischen und . Unter jedem ganzzahligen sollten Sie eine ganze Zahl schreiben zwischen und mit der Anforderung , dass die ‚s eine nicht abnehmende Folge bilden. Definieren Sie die Abweichung einer solchen Folge als . Entwerfen Sie einen Algorithmus, der die mit der minimalen Abweichung in Laufzeit O findet (n \ sqrt [4] {l}) .a1,,an0laibi0lbibmax(|a1b1|,,|anbn|)biO(nl4)

Ich habe ehrlich gesagt keine Ahnung, wie ich überhaupt anfangen soll, diese Frage zu lösen. Es sieht für mich wie eine dynamische Programmierfrage aus, aber der Professor sagte, dass dies mit einem gierigen Algorithmus gelöst werden sollte. Es wäre sehr dankbar, wenn mich jemand mit einem kleinen Hinweis in die richtige Richtung weisen könnte.

Aden Dong
quelle

Antworten:

9

Beginnen wir mit folgender Beobachtung:

Sei max das Maximum der Folge a1,...,an und sei min das Minimum. Wenn a1=max , ist die Auswahl von b1=b2=...=bn=(max+min)/2 optimal.

Warum ist das so? Nun, da die Sequenz mit dem Maximum beginnt, wählen wir entweder b1 groß und erleiden eine große Abweichung vom Minimum der Sequenz (da jedes nachfolgende bi größer oder gleich b1 ), oder wir wählen b1 klein und leiden unter Abweichung bis max . Der Durchschnitt minimiert die maximale Abweichung.

Wir können nun versuchen, diese Beobachtung auf die allgemeinen Folgen a_1, ..., a_n zu verallgemeinern a1,...,an. Zum Beispiel können wir jede Sequenz in Teilsequenzen aufteilen, so dass jede mit dem Maximum der jeweiligen Teilsequenz beginnt.

Beispiel: wird in , und .( 2 ) ( 6 , 4 , 1 , 5 , 2 ) ( 8 , 7 , 5 , 1 )(2,6,4,1,5,2,8,7,5,1)(2)(6,4,1,5,2)(8,7,5,1)

Angesichts dieser Aufteilung können wir nun jede dieser Teilsequenzen separat lösen und eine Zuweisung der , was jedoch die nicht abnehmende Bedingung verletzen könnte. Dies kann behoben werden, ohne an Optimalität zu verlieren.bi

Beachten Sie, dass die letzte Teilfolge des maximalen enthält immer der gesamten Sequenz (sonst gäbe es eine andere Teilfolge danach). Sei die Werte, die wir den zugewiesen haben . Um nun in eine Nichtverringerung zu erreichen wir bei von hinten und arbeiten uns nach vorne vor. Wenn größer als , setzen wir einfach . Wenn es kleiner ist, behalten wir es. Dann vergleichen wir mit und so weiter. Beachten Sie, dass Sie jedes auf den Wert von senken.w 1 , w 2 , . . . , W k k w 1 , . . . , W k w k w k - 1 w k w k - 1 : = w k w k - 2 w k - 1 w i w i + 1 w i w i + 1maxw1,w2,...,wkkw1,...,wkwkwk1wkwk1:=wkwk2wk1wiwi+1Erhöht niemals die Abweichung, da der Maximalwert in der mit zugewiesenen immer niedriger ist als der Maximalwert in der mit zugewiesenen Teilfolge .wiwi+1

Dieser Algorithmus sollte meiner Meinung nach korrekt sein. In Bezug auf die Laufzeit besteht der Schlüsselschritt darin, die ansteigenden Maxima für die Teilfolgen zu berechnen, was in . Ich bin mir nicht sicher, wo beitrage.lO(n)l

Syzygy
quelle
2

Ich werde hier laut nachdenken und nur die von Ihnen gegebenen Hinweise durcharbeiten. Gehen wir zum ursprünglichen Hinweis, dass ist, was Sie zuerst versuchen sollten. Ich kann mir einen gierigen Algorithmus vorstellen, der diese Zeit hat.O(nl)

Der Teil der Zeit Komplexität bedeutet , dass Sie eine Liste der Zählung jedes Auftreten von jedem Wert halten kann . Das heißt, erstellen Sie einfach eine Menge die die Anzahl der einzelnen in der Menge verfolgt. Sie können die Initalisierungsliste erstellen, indem Sie die Eingabesequenz einmal scannen.0 .. l Count = C 0 , , C l ll0..lCount=C0,,Cll

Sie können diese Liste in scannen , um den Maximal- und Minimalwert zu erhalten. Wenn Sie die gesamte Liste von mit diesem Mittelpunkt füllen würden, wäre Ihre Varianz einfach die Differenz zwischen diesem Wert und dem max / min-Wert. Dies ist im Grunde Ihr Worst-Case-Szenario, nennen wir es .b b wO(l)bbw

Arbeiten Sie sich also von links nach vor. Sie können dieses Element aus löschen und die min / max von in . Jetzt können wir gierig sein. Wir wählen nicht da dies die verbleibende gesamte Liste nach oben zwingt (um die nicht abnehmende Anforderung zu erfüllen) und somit die Varianz erhöht. Der Mindestwert, den wir wählen können, ist . Wenn im akzeptablen Bereich liegt, wählen wir ihn aus, wenn er unter dem Bereich liegt, verwenden Sie das Minimum. Dies minimiert die Varianz bei bei bekannten Einschränkungen. Zähle b [ i + 1 ] b [ n ] O ( l ) b i > b w b [ i - 1 ] a i b ibiCountb[i+1]b[n]O(l)bi>bwb[i1]aibi

Dies ist nur eine Idee, vielleicht habe ich Glück und sie weist Sie in die richtige Richtung. Dieser Algorithmus funktioniert möglicherweise nicht (für meine wenigen einfachen Tests), entspricht jedoch den angegebenen Hinweisen, sodass er möglicherweise hilfreich ist. Wenn es richtig ist, ist es leicht zu erkennen, dass der -Teil mit Sicherheit auf abgelegt werden kann .O ( log l )O(l)O(logl)

edA-qa mort-ora-y
quelle
2

Hier ist die Lösung des Professors, die er "Reduktion" nennt: Versuchen Sie, für jedes von 0 bis l eine Lösung zu konstruieren, wenn wir wissen, dass die Abweichung kleiner oder gleich i ist . Das erste i, für das eine Lösung gefunden werden kann, ist die minimale Abweichung. Wir können eine Lösung finden, wenn die Abweichung in der O ( n ) -Zeit gegeben ist. Die Laufzeit ist also O ( n l ) . Anstelle der linearen Suche können wir dann die binäre Suche verwenden, um die kleinste Abweichung zu bestimmen, für die eine Lösung möglich ist. Dies reduziert die Laufzeit auf O ( n log li0liiO(n)O(nl) , die die Anforderung von O ( n 4 erfülltO(nlogl).O(nl4)

Aden Dong
quelle
4
Also das war ein Trick ... Aber ich bin mehr fasziniert von dem "Wir können eine Lösung finden, wenn die Abweichung in O (n) Zeit gegeben ist" .. wie ist dasnichtder interessante Teil? O(nl4)
jmad
@jmad Wenn ist , nimm für jedes j b j als den niedrigsten Wert, der mindestens so groß ist wie alle vorherigen b k und der nicht mehr als i von a j entfernt ist . Wenn wir einen solchen Wert nicht finden können, was bedeutet das? Dies bedeutet, dass ein vorheriges b t größer als i als a j ist . Ein vorheriges a t ist also mehr als 2 i größer als a j . Dieser Wert von i war also nicht möglich. Wenn Sie durch die n bekommenijbjbkiajbtiajat2iajinWerte, ohne wie folgt hängen zu bleiben, haben Sie eine Lösung für ohne Rückverfolgung in der Zeit O ( n ) gefunden . iO(n)
JWG
O (n log l) wäre ein starker Hinweis darauf, dass Sie eine binäre Suche im Bereich von 0 bis 1 durchführen müssen.
gnasher729
0

Ich denke, das sollte in O (n) machbar sein.

Nehmen Sie das ähnliche Problem: Wenn , 1 ≤ i ≤ n und d ≥ 0 sind, finden Sie b i in nicht absteigender Reihenfolge, so dass | a i - b i | d für alle i, oder zeigen Sie, dass es nicht möglich ist. Dies kann in O (n) erfolgen, und mit der binären Suche wird das ursprüngliche Problem in O (n log l) gelöst.aibi|aibi|d

biaid,bjaj+d<ai2d+d=aidbi

Aber wenn a_i - a_j ≤ 2d für alle i ≤ j, dann denke ich, wird immer eine Lösung gefunden werden. Also müssen wir nur m = max (a_i - a_j) für alle i ≤ j finden und d = floor ((m + 1) / 2) wählen. Dieses Maximum kann in O (n) gefunden werden.

gnasher729
quelle
aiaj2dijbibi