Ich brauche Hilfe beim Finden der allgemeinen Idee für einen Algorithmus, um das folgende Problem zu lösen. Das Problem wurde mir in einem Auftrag gegeben. Es sieht so aus, als ob es durch eine gierige Methode lösbar sein sollte, aber ich kann keine einfache Lösung finden. Hier ist die Problembeschreibung:
Sie erhalten eine Folge von N Zahlen a_1 ... a_n , so dass 0 = a_1 < a_2 < ... < a_n . Sie müssen höchstens M dieser Zahlen so eliminieren, dass die minimale Differenz a_i+1 - a_i zwischen zwei aufeinanderfolgenden Zahlen maximiert wird.
Sie können das erste und letzte Element a_0 und a_n nicht entfernen. Außerdem müssen Sie so wenige Zahlen wie möglich eliminieren: Wenn Sie M - 1 eliminieren, erhalten Sie die kürzeste Entfernung als D und eliminieren M immer noch die gleiche minimale Differenz. Sie dürfen diese letzte Zahl nicht eliminieren.
Ich bitte nicht um eine vollständige Lösung für dieses Problem. Nur einige Richtlinien, wie der Algorithmus aussehen könnte.
Bearbeiten: Einige Testbeispiele. Beachten Sie, dass es mehrere gültige Lösungen geben kann.
%Vor% %Vor%[EDIT: Ich habe ursprünglich behauptet, ElKaminas Antwort sei falsch gewesen, aber ich habe mich selbst davon überzeugt Es ist nicht nur korrekt, es ist praktisch das gleiche wie meine (später) Antwort :-P immer noch ein bisschen kurz für meinen Geschmack!]
Hier ist eine exakte O (NM ^ 2) -time, O (NM) -Raum dynamische Programmierung Algorithmus, der in Millisekunden die richtige Antwort auf alle OP-Beispiele bekommt. Die Grundideen sind:
Im folgenden bedeutet x [i] die i-te Zahl in der Liste, wobei die Indexierung von 0 beginnt.
Es sei f (i, j) die optimale (größte minimale) Intervallgröße, die aus dem Suffix der Nummernliste beginnend bei Position 0 & lt; = i & lt; N, indem diese (d. H. Die i-te) Nummer beibehalten wird und genau j der späteren (nicht notwendigerweise aufeinanderfolgenden) Nummern gelöscht wird. Die folgende Rekursion zeigt, wie dies berechnet werden kann:
%Vor% Das min(j, N-i-2) ist dort statt nur j, um Löschungen "nach dem Ende" zu verhindern. Die einzigen grundlegenden Fälle, die wir brauchen, sind:
Genauer gesagt wird zur Berechnung von f (i, j) eine Schleife über alle möglichen Zahlen (einschließlich Null) aufeinanderfolgender Löschungen beginnend bei der Position i + 1 durchgeführt, wobei in jedem Fall das Minimum von (a) berechnet wird Intervall, das durch diesen Block von Löschungen gebildet wird, und (b) die optimale Lösung für das Teilproblem, das auf der ersten nicht gelöschten Zahl rechts von diesem Block beginnt. Es ist wichtig anzugeben, dass die erste Zahl in einem Block (x [i]) nicht gelöscht wird, so dass das Intervall des vorherigen (übergeordneten) Unterprojekts immer "capped" ist. Das ist ein schwieriger Teil, der gebraucht wurde mir eine Weile, um herauszufinden.
Wenn Sie oben die einfache Rekursion kodieren, wird es funktionieren, aber es wird Zeit exponentiell in M und N nehmen. Durch memoising f (), garantieren wir, dass sein Körper maximal N * M mal (einmal pro unterschiedliche Parameterkombination) durchlaufen wird. Jedes Mal, wenn die Funktion ausgeführt wird, führt sie O (M) -Work-Scanning durch zunehmend lange Löschblöcke aus, und zwar für O (NM ^ 2) insgesamt.
Sie können keine größere Lücke erzeugen, indem Sie weniger Löschungen verwenden, so dass die größte minimale Intervallgröße gefunden werden kann, wenn Sie durch die M + 1 Ergebnisse f (0, M), f (0, M-1), .. ., f (0, 0) für die erste Zahl, die kleiner als eine vorherige Zahl ist: die vorherige Zahl ist die Antwort und das zweite Argument für f () ist die Mindestanzahl der erforderlichen Löschungen. Um eine optimale Lösung zu finden (dh eine Liste der bestimmten gelöschten Nummern), können Sie Entscheidungen in einem separaten Vorgänger-Array aufzeichnen, so dass p [i, j] den Wert von d gibt (der in die vorherigen Werte von i und j), die zu der optimalen Lösung für f (i, j) führten. (Vielleicht ist "Vorgänger" hier verwirrend: Er bezieht sich auf die Teilprobleme, die vor das aktuelle Teilproblem gelöst sind, obwohl diese Teilprobleme "nach" (rechts von) dem Suffix erscheinen, das das aktuelle Teilproblem darstellt.) Diese Links können dann verfolgt werden, um die gelöschten / gelöschten Entscheidungen wiederherzustellen.
Mit einem kniffligen Problem wie diesem kann es hilfreich sein, falsche Ansätze zu betrachten und genau zu sehen, wo sie schiefgelaufen sind ...: - / Ich dachte, ich hätte das Problem gelöst, aber ich hatte die Anforderung nicht bemerkt eine Lösung zurückgeben, die so wenig Löschungen wie möglich verwendet, und meine anfänglichen Versuche, dies zu beheben, haben nicht funktioniert.
Zunächst versuchte ich, f (i, j) als die optimale (größte minimale) Intervallgröße zu definieren, die aus dem Suffix der Nummernliste beginnend bei Position 0 & lt; = i & lt; N, indem diese (d. H. Die i-te) Nummer beibehalten und von 0 bis j der späteren (nicht notwendigerweise aufeinanderfolgenden) Nummern gelöscht wird. Aber das hat ein subtiles Problem verursacht: Es ist nicht unbedingt der Fall, dass Sie eine optimale Lösung von optimalen Lösungen zu Teilproblemen zusammenstellen können.Ich dachte zunächst, dass dies behoben werden könnte, indem die Funktion so geändert wird, dass ein Paar (Intervallgröße, minimale Anzahl von Löschungen zum Erreichen dieser Intervallgröße) zurückgegeben wird, und dass Abhängigkeiten zwischen Aktionen mit dem maximalen Mindestabstand aufgehoben werden Größe, indem Sie immer die Aktion wählen, die die Anzahl der Löschungen minimiert. Dies trifft jedoch im Allgemeinen nicht zu, da die optimale Lösung für das Teilproblem (dh für ein Suffix der Nummernliste) Deletionen ausgibt, die die minimale Intervallgröße in dieser Region so groß wie möglich machen, selbst wenn sich diese Löschungen als verschwendet herausstellen weil das Präfix der vollständigen Lösung das Gesamtminimum sowieso niedriger macht. Hier ist ein Gegenbeispiel mit einem f (), das zurückgibt (Intervallgröße, minimale Anzahl von Löschungen benötigt, um diese Größe zu erreichen) Paare:
%Vor%Ich habe nicht die Arbeit für das zweite Element des Paares gezeigt, das von f (0, 1) zurückgegeben wird, weil es schwer ist, knapp auszudrücken, aber offensichtlich wird es 1 sein, weil beide Alternativen 1 Löschung benötigen.
Verwenden Sie dynamische Programmierung.
Hinweis X (i, j) enthält einen minimalen Abstand mit ersten i Elementen und unter diesen ist j ausgewählt (d. h. nicht gelöscht).
Damit erhalten Sie eine genaue Lösung. Komplexität = O (MN ^ 2), denn für jeden i-Wert gibt es nur M gültige Werte von j, und jeder Aufruf an die Funktion muss O (M) -Arbeiten erledigen.
Seien Elemente A1, A2, ..., An
Die Formel für das Update lautet:
X (i + 1, j + 1) = Max (Min (A (i + 1) -Ak, Xkj) für k & lt; = i)
[Bearbeitet von j_random_hacker, um Informationen aus den Kommentaren hinzuzufügen]
Ich denke, ich habe die Lösung. Es funktioniert zumindest mit den beiden Samplesets. Es gibt nicht unbedingt die gleiche Menge wie die Antwort zurück, aber die Menge, die zurückgegeben wird, hat denselben minimalen Wert. Es ist auch iterativ und gierig, was schön ist, und es gibt Unmengen von Möglichkeiten, es zu optimieren. Sieht so aus als wäre MLog (N).
Wichtig ist, dass die Zahlen keine Rolle spielen - nur die Unterschiede zwischen ihnen. Wenn Sie eine Zahl entfernen, kombinieren Sie eigentlich nur zwei benachbarte Unterschiede. Mein Algorithmus wird sich dann auf die Unterschiede konzentrieren. Es ist eine einfache Sache, zu den Elementen zurückzukehren, die diese Unterschiede verursacht haben, und zu löschen, während Sie fortfahren.
Schritt 3 hat einen Punkt, den ich als willkürliche Entscheidung bezeichnet habe. Es sollte wahrscheinlich nicht sein, aber Sie kommen in genug Fälle, dass es eine Frage ist, wie viel Komplexität Sie hinzufügen möchten. Diese Willkür erlaubt es, mehrere verschiedene richtige Antworten zu geben. Wenn Sie zwei Nachbarn sehen, die den gleichen Wert haben, dann sage ich an dieser Stelle willkürlich eines. Im Idealfall sollten Sie das Nachbarnpaar überprüfen, das 2 entfernt ist, dann 3, usw., und das niedrigere bevorzugen. Ich bin mir nicht sicher, was ich tun soll, wenn man beim Expandieren auf eine Kante trifft. Um diesen Teil perfekt zu machen, müssen Sie möglicherweise diese Funktion rekursiv aufrufen und sehen, welche davon besser ist.
Entferne höchstens 8 von: 0 3 7 10 15 26 38 44 53 61 76 80 88 93 100
[3, 4, 3, 5, 11, 12, 6, 9, 8, 15, 4, 8, 5, 7] M = 8
Entferne die Dreien. Das Entfernen von Kanten kann nur in eine Richtung erfolgen:
[7, 3, 5, 11, 12, 6, 9, 8, 15, 4, 8, 5, 7] M = 7
[7, 8, 11, 12, 6, 9, 8, 15, 4, 8, 5, 7] M = 6
Als nächstes entfernen Sie die 4: [7, 8, 11, 12, 6, 9, 8, 15, 12, 5, 7] M = 5
Als nächstes entfernen Sie die 5: [7, 8, 11, 12, 6, 9, 8, 15, 12, 12] M = 4
Als nächstes entfernen Sie die 6: [7, 8, 11, 12, 15, 8, 15, 12, 12] M = 3
Als nächstes entfernen Sie die 7: [15, 11, 12, 15, 8, 15, 12, 12] M = 2
Als nächstes entferne die 8: [15, 11, 12, 15, 23, 12, 12] M = 1 // Note, willkürliche Entscheidung über die Richtung des Hinzufügens
Entfernen Sie zum Schluss die 11: [15, 23, 15, 23, 12, 12]
Beachten Sie, dass in der Antwort die kleinste Differenz 12 ist.
Entfernen Sie höchstens 7 von: 0 3 7 10 15 18 26 31 38 44 53 60 61 73 76 80 81 88 93 100
[3, 4, 3, 5, 3, 8, 5, 7, 6, 9, 7, 1, 12, 3, 4, 1, 7, 5, 7] M = 7
Entferne die 1en:
[3, 4, 3, 5, 3, 8, 5, 7, 6, 9, 8, 12, 3, 4, 1, 7, 5, 7] M = 6
[3, 4, 3, 5, 3, 8, 5, 7, 6, 9, 8, 12, 3, 5, 7, 5, 7] M = 5
Es sind noch 4 3 übrig, damit wir sie entfernen können:
[7, 3, 5, 3, 8, 5, 7, 6, 9, 8, 12, 3, 5, 7, 5, 7] M = 4
[7, 8, 3, 8, 5, 7, 6, 9, 8, 12, 3, 5, 7, 5, 7] M = 3
[7, 8, 11, 5, 7, 6, 9, 8, 12, 3, 5, 7, 5, 7] M = 2 // Beachte willkürliches Hinzufügen nach rechts
[7, 8, 11, 5, 7, 6, 9, 8, 12, 8, 5, 7, 5, 7] M = 1
Wir würden die 5 als nächstes entfernen, aber wir dürfen nur 1 entfernen und haben 3, also hören wir hier auf. Unser kleinster Unterschied ist 5 und entspricht der Lösung.
Hinweis : Aus der Idee heraus, dieselben X -Werte zu kombinieren, um dies zu vermeiden, für den Fall 1, 29, 30, 31, 59 von SauceMaster.
Ich hatte gehofft, dass ich keinen All-Combinations-Ansatz verwenden würde, aber nach einer Reihe von Versuchen schien es die einzige Möglichkeit zu sein, meine Ergebnisse mit denen von j_random_hacker zu vergleichen. (Einige der folgenden Kommentare beziehen sich auf frühere Versionen dieser Antwort.) Ich bin beeindruckt, wie prägnant der Algorithmus von j_random_hacker / ElKamina in Haskell ('jrhMaxDiff') ausgedrückt wird. Seine Funktion "compareAllCombos" sucht nach Unterschieden in den Ergebnissen unserer beiden Methoden:
%Vor%
Der Algorithmus:
Haskell-Code:
Tags und Links algorithm language-agnostic recurrence