[PYTHON] Ich konnte die Zaunreparatur von Arimoto nicht leicht verstehen, daher werde ich sie im Detail verfolgen.

Begriffsdefinitionen

** Arimoto **

Fence Repair

Das Problem ist, die gierige Methode zu verwenden, aber ich konnte nicht verstehen, warum sie gierig wurde, also habe ich zunächst versucht, sie zu überprüfen.

Problemstellung

Bauer John versucht, $ N $ Bretter aus einem sehr langen Brett herauszuschneiden, um den Zaun zu reparieren. Die Länge der Tafel, die Sie schneiden möchten, beträgt $ L_1, L_2, \ dots, L_N $, und die Länge der ursprünglichen Tafel ist nur die Summe dieser. Beim Schneiden eines Bretts kostet es so viel wie die Länge des Brettes. Angenommen, Sie möchten ein 5,8,8 $ 3 $ Board aus einem 21 $ langen Board herausschneiden. Das Schneiden eines $ 21 $ langen Boards in $ 13 $ und $ 8 $ lange Boards kostet $ 21 $. Das Schneiden dieses $ 13 $ Boards in $ 5 $ und $ 8 $ Boards kostet $ 13 $. Es kostet insgesamt 34 $. Wie viel kostet es mindestens, alle Bretter auszuschneiden?

Einschränkungen

Bei vielen Problemen kann es häufig auf eine Art Diagrammstruktur verallgemeinert werden, unabhängig davon, ob es sich um einen Baum handelt oder nicht. Das in dieser Problemstellung gezeigte Beispiel kann wie folgt als dichotomisierter Baum ausgedrückt werden. fence-repair_01.png Die Kosten bei jeder Trennung sind der Wert des übergeordneten Knotens, sodass die Gesamtkosten die Summe aller Werte der Nicht-Blattknoten sind. Im obigen Beispiel beträgt die Summe der Nicht-Blattknoten (weiß) $ 13 + 21 = 34 $, was den Gesamtkosten der Problemstellung entspricht.

Der Zweck besteht darin, die Gesamtkosten zu diesem Zeitpunkt zu minimieren.

Antwortrichtlinie

Kommentarpolitik des Ameisenbuches

--Entfernen Sie $ 2 $ der angegebenen Bretter in aufsteigender Reihenfolge und fügen Sie die zusammengeführten Bretter an ihrer Stelle hinzu.

Als ich es las, schien es richtig zu sein, aber ich war nicht wirklich überzeugt. Ich denke, dass der Zweck darin besteht, eine Änderung in der Idee des Denkens von unten nach oben zu vermitteln, da die Bedingungen von oben nach unten schwer zu lösen sind, aber ich verstehe dies nicht, wenn später ein schwierigeres Problem erklärt wird. Ich fühlte mich festgefahren, also beschloss ich, es weiter zu verfolgen.

Feste Bedingungen und variable Faktoren

Zu sehen, was behoben ist (Prämisse) und welche Art von Operation Schwankungen verursacht, ist die grundlegende Richtlinie zur Lösung eines Problems. Diesmal ist es ein Problem, das im Kapitel über Gier vorgestellt wurde. Es ist also klar, dass es immer Operationen gibt, die die Gesamtkosten senken. In der tatsächlichen Lösungssituation ist es notwendig, den Algorithmus einschließlich der Beurteilung auszuwählen.

In dieser Frage werden nun die Längen aller Bretter angegeben, wenn das Schneiden abgeschlossen ist, sodass die Anzahl der Knoten, die schließlich zu Blättern werden, festgelegt wird. Mit anderen Worten, die Baumstruktur ändert sich in Abhängigkeit von der Reihenfolge, in der die Blätter kombiniert werden.

Überprüfung variabler Faktoren

Selbst wenn Sie versuchen zu verstehen, wie es sich ändert, selbst wenn Sie in einem komplizierten Fall plötzlich darüber nachdenken, wird es fehlschlagen. Der große Mathematiker Carte sagte auch, "teile die Schwierigkeiten" </ b>.

Die Aufteilung in wahnsinnig einfache Fälle und das Denken ist ein wichtiges Schema zur Lösung eines Problems. Was ist der einfachste Fall? Lass uns zusammen denken.

Fall von N = 1

Natürlich ist der Fall von $ N = 1 $ der einfachste. Mit anderen Worten, die Originalplatte wird nicht geschnitten. Damit gibt es keine Schwankungen oder Scheiße, und die Kosten betragen immer $ 0 $. Erhöhen wir $ N $.

N = 2 Fall

Dies ist der Fall, wenn die Anzahl der Unterbrechungen $ 1 $ beträgt. Auch hier gibt es keine Variation, wenn die Länge der Platte nach dem Schneiden festgelegt ist. Lassen Sie uns $ N $ weiter erhöhen.

N = 3 Fall

Tut mir leid, dass ich dich warten ließ. Variationen kommen schließlich aus $ N = 3 $ heraus. Lassen Sie uns der Einfachheit halber zunächst die Länge der Platte nach dem Schneiden, die $ 3 $ beträgt, als $ A \ leqq B \ leqq C $ angeben. Dies wäre eine Annahme, die die Allgemeinheit nicht verlieren würde.

Nun, der Weg, hier zu schneiden, ist ein $ 3 $ -Muster.

  • (A+B+C) \rightarrow (A+B),C \rightarrow A,B,C
  • (A+B+C) \rightarrow A,(B+C) \rightarrow A,B,C
  • (A+B+C) \rightarrow B,(C+A) \rightarrow A,B,C

Es ist schwer zu verstehen, selbst wenn ich es in Buchstaben schreibe, also habe ich ein Diagramm gemacht. fence-repair_02.png Nur der Unterschied im roten Teil der Abbildung wirkt sich auf die Gesamtkosten aus. Die Position der anderen Teile ist unterschiedlich, aber der Summenwert ändert sich nicht. Mit anderen Worten, die Minimierung der Gesamtkosten entspricht in diesem Fall der Auswahl des kleinsten von $ (A + B), (B + C), (C + A) $.

Wenn Sie genau prüfen, ob es genügend Variationen gibt, wählen Sie $ 2 $ aus $ 3 $, dh $ {} _3 \ mathrm {C} _2 = {} _3 \ mathrm {C} _1 = 3 $, und es handelt sich um ein $ 3 $ -Muster. Es kann nur geben. Welches Muster das kleinste ist, ist natürlich $ (A + B) $, was $ 2 $ ist, ausgewählt aus dem kleinsten Wert.

Zusammenfassend kann man bei $ N = 3 $ ausschneiden, indem man $ 2 $ aus dem kleinsten auswählt. Betrachten Sie anhand dieser Tatsache den Fall von $ N = 4 $.

N = 4 Fall

Mit $ N = 3 $ konnten wir das Muster eingrenzen, das die Gesamtkosten minimiert. Aus meta-Sicht scheint es, da es sich um eine gierige Methode handelt, möglich zu sein, das Muster danach mit einem allmählichen Gefühl einzugrenzen.

Nun hat der Fall von $ N = 4 $ $ 4 $ Boards. Wenn Sie den Fall im ersten Schnitt teilen, wird das Muster geteilt, je nachdem, ob Sie das Brett $ ABCD $ um $ 1 + 3 $ oder $ 2 + 2 $ schneiden. fence-repair_03.png

1 + 3 Muster

Das Schnittmuster mit $ 1 + 3 $ ist eine Erweiterung des Falls von $ N = 3 $ zur Wurzelseite. Nach dem ersten Schneiden von $ 1 $ hat es die gleiche Form wie $ N = 3 $, und das Board $ ABC $ ändert sich nur in $ \ {ABC, ABD, ACD, BCD \} $.

Mit anderen Worten, es gibt insgesamt $ 4 \ mal 3 = 12 $ Muster, aber in Wirklichkeit kommt es auf das $ 4 $ Muster an, von dem eines zuerst geschnitten werden muss. Hier beträgt die Verallgemeinerung der Gesamtkosten des Falls von $ N = 3 $ $ 2A + 2B + C $. (Die Auswahl der kleineren $ 2 $ aus den $ 3 $ entspricht der Auswahl der größten)

Wenn Sie dagegen $ D $ hinzufügen, also $ A \ leqq B \ leqq C \ leqq D $, ist der Fall $ N = 4 $. Das folgende $ 4 $ -Muster wird verwendet, um die Gesamtkosten zusammenzufassen.

  • $ 3A + 3B + 2C + D $: Schneiden Sie zuerst $ D $
  • $ 3A + 3B + 2D + C $: Schneiden Sie zuerst $ C $
  • $ 3A + 3C + 2D + B $: Schneiden Sie zuerst $ B $
  • $ 3B + 3C + 2D + A $: Schneiden Sie zuerst $ A $

Lassen Sie uns jetzt hier anhalten und das $ 2 + 2 $ -Muster betrachten.

2 + 2 Muster

Wenn Sie einen Moment darüber nachdenken, können Sie sehen, dass die Gesamtkosten unabhängig von der Kombination 2-mal (A + B + C + D) $ betragen.

Vergleichen Sie miteinander

Durch die Aufteilung der bisherigen Fälle haben wir festgestellt, dass die Muster, die als der Fall von $ N = 4 $ betrachtet werden müssen, auf insgesamt $ 5 eingegrenzt sind, einschließlich des zuvor erwähnten $ 4 $ -Musters.

Subtrahieren wir nun $ 2 \ times (A + B + C + D) $ von allen Fällen, um die Größenbeziehung von $ 5 $ zu vergleichen.

  • $ ; ; ; ; ; ; 0 ; ; ; ; ; ; $: Zuerst in $ 2 + 2 $ Blätter schneiden
  • $ A + B-D $: Schneiden Sie zuerst $ D $
  • $ A + B-C $: Zuerst $ C $ schneiden
  • $ A + C-B $: Schneiden Sie zuerst $ B $
  • $ B + C-A $: Schneiden Sie zuerst $ A $

Was ist der Wert, der die niedrigsten Kosten sein kann? In Anbetracht von $ A \ leqq B \ leqq C \ leqq D $ können wir Folgendes sehen.

  • $ ; ; ; ; ; ; 0 ; ; ; ; ; ; $: Minimum, wenn $ A + BD $ positiv ist FONT>
  • $ A + B-D $: Minimum in negativen Fällen </ FONT>
  • $ A + B-C $: Kann negativ sein, ist aber kein Kandidat, da das Muster um $ 1 $ durch Subtrahieren der größeren Zahl $ D $ kleiner ist
  • $ A + C-B \ geqq 0 $: Kein Kandidat, da es aufgrund der Größenbeziehung immer $ 0 $ oder mehr ist
  • $ B + C-A \ geqq 0 $: Kein Kandidat, da es aufgrund der Größenbeziehung immer $ 0 $ oder mehr ist

Mit anderen Worten, der minimale Fall ändert sich in Abhängigkeit vom Beurteilungsergebnis von $ A + B \ leqq D $. </ b>

Kehren Sie zur Erklärung des Ameisenbuchs zurück

Schauen Sie sich $ A + B \ leqq D $ genauer an. Dies entspricht im Wesentlichen dem Hinzufügen des zusammengeführten Ergebnisses von $ A + B $ und dem erneuten Sortieren.

Dies liegt daran, dass $ C $ zum Zeitpunkt von $ C \ leqq D $ auf keinen Fall der Maximalwert sein kann. Die Auswahl von $ 2 $ aus dem kleineren der $ 3 $ entspricht der Auswahl des Maximums von $ 1 $. Sie benötigen keine $ C $ -Informationen, die nicht maximiert werden können.

Lassen Sie uns dies verständlicher visualisieren. Betrachten Sie im Fall von $ N = 4 $ das Problem, $ 2 $ von der kleinsten Seite auszuwählen und $ A + B $ als $ M $ zusammenzuführen.

Wie ich bereits erwähnt habe, gibt es unten nur $ 2 $ Fälle. $ M $ ist der größte Fall oder $ D $ ist der größte Fall. fence-repair_04.png

Korrekt. Selbst wenn Sie verschiedene Dinge von oben nach unten kneten und vom kleinsten zusammenführen und ersetzen, endet der Fall von $ N = 4 $ im Fall von $ N = 3 $. Wenn Sie $ A + B $ zur Bestätigung erneut an $ M $ zurückgeben, erfolgt dies in Form einer Fallklassifizierung, die von oben nach unten wie folgt erläutert wurde. fence-repair_05.png

Von unten nach oben zurückerobern

Schauen wir uns nun die Kosten für jedes Blatt an. Es ist leicht zu erkennen, dass die Gesamtkosten des $ 1 $ -Blatts das Produkt aus dem Wert und der Tiefe des Blattknotens sind. Versuchen Sie, das Blatt $ A $ in der vorherigen Abbildung bis zur Wurzel zu verfolgen. Sie können sehen, dass alle Hauptstraßen von $ 1 $, die zur Wurzel führen, $ A $ enthalten und andere Routen nicht $ A $ enthalten.

Und da es schwierig ist, gleichzeitig über die $ 2 $ -Achse von Wert und Tiefe nachzudenken, denken Sie aus der Perspektive derselben Tiefe. Selbst wenn nicht bekannt ist, um welche Baumstruktur es sich handelt, sind die Kosten bei gleicher Tiefe umso geringer, je kleiner der Wert ist. Dies bedeutet, dass es immer gierig ist, sich mit dem kleinsten Paar zu füllen, wenn man bedenkt, dass die Blätter in der Reihenfolge vom tiefsten gefüllt sind. Dies liegt wiederum daran, dass "je kleiner der Wert ist, desto geringer sind die Kosten, wenn die Tiefe gleich ist".

Wenn Sie versuchen, dies von oben nach unten zu tun, müssen Sie mehrere Auswahlen in einer Tiefe von $ 1 $ treffen, wodurch plötzlich ein Fall entsteht. Wie Sie sehen können, ist $ N = 4 $ problematisch genug, was bedeutet, dass der maximale Fall von $ N = 20000 $ praktisch unmöglich ist.

Gewonnene Erkenntnisse

  • Die Schwierigkeit ist geteilt --Versuchen Sie aus der entgegengesetzten Richtung
  • Wenn Sie mehrere Achsen haben, versuchen Sie, eine davon zu reparieren.

Den tatsächlichen Antwortcode finden Sie im Programming Contest Challenge Book.

Beiseite

Wettbewerbsprofis starteten im Monat $ 8 $ von $ 2020 $. Normalerweise poste ich Artikel auf Personal Blog.

Recommended Posts