Binäre Suche über die Antwort in Python

Problem

Wie großen Lieferwagen mieten

Der Kurierdienst liefert die Pakete entlang einer Route aus: der Reihe nach, in der Reihenfolge, in der sie am Weg liegen. Der Lieferwagen fährt einmal am Tag und lädt die Pakete eins nach dem anderen, bis das nächste nicht mehr passt. Das wartet bis morgen. Die acht Pakete wiegen 6, 9, 4, 7, 3, 8, 5 und 2 kg und müssen innerhalb von 3 Tagen bei den Kunden sein.

Je größer der Lieferwagen, desto höher die Tagesmiete. Du suchst die kleinste Kapazität, die die Pakete rechtzeitig hinbringt. Die erste Lösung, die einem einfällt: nacheinander jede Kapazität ausprobieren, vom schwersten Paket aufwärts.

def days(weights, capacity):
    days = 1
    load = 0
    for weight in weights:
        if load + weight > capacity:
            days += 1
            load = 0
        load += weight
    return days

weights = [6, 9, 4, 7, 3, 8, 5, 2]
capacity = max(weights)
tries = 1
while days(weights, capacity) > 3:
    capacity += 1
    tries += 1
print(f"Versuche: {tries}")
print(f"Kapazität: {capacity} kg")

Versuche: 7
Kapazität: 15 kg

Bei acht Paketen sind das 7 Versuche. Aber das Lager in der Stadt hat 1000 Pakete am Tag (von 1 bis 30 kg) an 5 Arbeitstagen. Eine nach der anderen laden die Prüfungen 3.089.000 Pakete, bevor sie die Antwort erreichen, und bei doppelt so vielen Paketen wächst die Arbeit etwa auf das Vierfache. Das misst du weiter unten.

Die Idee

Sortiert ist die Antwort

Die Pakete sind nicht sortiert. Etwas anderes ist es. Frag jede Kapazität „reicht sie?“ und reihe die Antworten auf:

weights = [6, 9, 4, 7, 3, 8, 5, 2]
for capacity in range(9, 19):
    d = days(weights, capacity)
    answer = "ja" if d <= 3 else "nein"
    print(f"{capacity:2} kg: {d} Tage, {answer}")

 9 kg: 7 Tage, nein
10 kg: 6 Tage, nein
11 kg: 5 Tage, nein
12 kg: 5 Tage, nein
13 kg: 5 Tage, nein
14 kg: 5 Tage, nein
15 kg: 3 Tage, ja
16 kg: 3 Tage, ja
17 kg: 3 Tage, ja
18 kg: 3 Tage, ja

Die Antworten sind „nein“, „nein“, … und dann nur noch „ja“. Sobald die Kapazität X reicht, reicht auch jede größere: Ein größerer Lieferwagen kann genau dieselben Ladungen fahren. Eine solche Prüfung heißt monoton: Ab einer Stelle ändert sich die Antwort nicht mehr.

Und in einer Reihe „nein… nein, ja… ja“ findest du das erste „ja“ mit binärer Suche, genauso wie den ersten Preis ≥ 20 € in der vorigen Lektion: Du probierst die Mitte und wirfst die Hälfte weg. Das ist binäre Suche über die Antwort: Du durchsuchst kein Array, sondern den Bereich der möglichen Antworten.

Der Bereich ist klar. Die Kapazität ist mindestens das schwerste Paket, sonst passt es nie hinein. Und sie muss nicht größer sein als die Summe aller Pakete: Dann fährt alles an einem Tag.

Sieh es dir an

Die Proben entlang der Reihe

def min_capacity(weights, max_days):
    lo = max(weights)
    hi = sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if days(weights, mid) <= max_days:
            hi = mid
        else:
            lo = mid + 1
    return lo

weights = [6, 9, 4, 7, 3, 8, 5, 2]
print(f"Die kleinste Kapazität: {min_capacity(weights, 3)} kg")

Die kleinste Kapazität: 15 kg

def days(weights, capacity):
    days = 1
    load = 0
    for weight in weights:
        if load + weight > capacity:
            days += 1
            load = 0
        load += weight
    return days


def min_capacity(weights, max_days):
    lo = max(weights)
    hi = sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if days(weights, mid) <= max_days:
            hi = mid
        else:
            lo = mid + 1
    return lo

Schritt für Schritt, in Worten

8 Pakete, höchstens 3 Tage. Die Kapazität beträgt mindestens 9 kg (das schwerste Paket) und höchstens 44 kg (alles an einem Tag). Die Antwort ist einer dieser 36 Werte.
mid = 26 kg: Der Lieferwagen lädt der Reihe nach, 2 Tage. 2 ≤ 3: ja. Jede Kapazität über 26 ist ebenfalls ein „ja“, deshalb hi = 26.
mid = 17 kg: Der Lieferwagen lädt der Reihe nach, 3 Tage. 3 ≤ 3: ja. Jede Kapazität über 17 ist ebenfalls ein „ja“, deshalb hi = 17.
mid = 13 kg: 5 Tage, mehr als 3: nein. Jede Kapazität unter 13 ist ebenfalls ein „nein“, deshalb lo = 14.
mid = 15 kg: Der Lieferwagen lädt der Reihe nach, 3 Tage. 3 ≤ 3: ja. Jede Kapazität über 15 ist ebenfalls ein „ja“, deshalb hi = 15.
mid = 14 kg: 5 Tage, mehr als 3: nein. Jede Kapazität unter 14 ist ebenfalls ein „nein“, deshalb lo = 15.
lo und hi treffen sich bei 15 kg: das erste „ja“ in der Reihe. 5 Prüfungen statt die Kapazitäten einzeln durchzuprobieren.

Das ist die untere Schranke aus der vorigen Lektion. Nur steht statt prices[mid] < target eine Frage, die eine ganze Funktion beantwortet: days(weights, mid) <= max_days. Lautet die Antwort „ja“, kann mid das kleinste „ja“ sein und bleibt: hi = mid. Lautet sie „nein“, fallen mid und alles darunter weg: lo = mid + 1.

Die Prüfung days geht alle n Pakete durch, und es gibt etwa log₂ des Gesamtgewichts Proben. Insgesamt O(n log S), wobei S die Summe ist. Nacheinander wären es bis zu S Proben mit je n Paketen.

Probier es aus

Sage die Antwort voraus

Dieselben acht Pakete, aber jetzt für 8 Tage. Was gibt das Programm aus?

weights = [6, 9, 4, 7, 3, 8, 5, 2]
print(f"Die kleinste Kapazität: {min_capacity(weights, 8)} kg")

Antwort

Die kleinste Kapazität: 9 kg

Die kleinste Kapazität: 2 kg

Die kleinste Kapazität: 6 kg

Probier es aus

Ergänze

Die Prüfung sagt „ja“: Mit der Kapazität mid kommen die Pakete rechtzeitig an. Was passiert mit hi?

def min_capacity(weights, max_days):
    lo = max(weights)
    hi = sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if days(weights, mid) <= max_days:
            hi = 
        else:
            lo = mid + 1
    return lo

Probier es aus

Finde den Fehler

Die Pakete müssen innerhalb von 6 Tagen ankommen. Die Suche sagt 9 kg, aber mit 9 kg brauchen sie 7 Tage:

weights = [6, 9, 4, 7, 3, 8, 5, 2]
print(f"Die kleinste Kapazität: {min_capacity(weights, 6)} kg")
print(days(weights, min_capacity(weights, 6)), "Tage")

Die kleinste Kapazität: 9 kg
7 Tage

Wähle die Zeile mit dem Fehler.

Die Idee

Wie du so eine Aufgabe erkennst

Es gibt drei Zeichen:

Du suchst das kleinste (oder größte) X, für das etwas möglich ist;
für ein gegebenes X ist die Prüfung billig: ein Durchlauf, wie days;
die Prüfung ist monoton: Sobald X funktioniert, funktioniert auch jedes größere X (oder jedes kleinere).

Dann suchst du keine Formel für X. Du suchst binär im Bereich der möglichen X, und die Prüfung sagt dir, in welche Richtung es geht.

Aufgaben derselben Art:

die kürzeste Zeit, in der drei Drucker mit unterschiedlicher Geschwindigkeit 500 Paketetiketten drucken. Für eine gegebene Zeit zählst du, wie viele Etiketten fertig werden, und mehr Zeit ergibt nie weniger;
die niedrigste Geschwindigkeit des Förderbands im Lager, bei der die Pakete einer Schicht in 8 Stunden durchkommen;
der größte Abstand zwischen den Packstationen entlang des Boulevards (die Aufgabe unten). Hier suchst du das größte „ja“.

Genauer, für Neugierige

Warum die Prüfung „so viel lädt, wie passt“. Nimmt der Lieferwagen heute weniger mit, als er kann, bleibt mehr für morgen. Vollladen schadet nie, also ist die Zahl der Tage, die days liefert, die kleinstmögliche für diese Kapazität.

Das größte „ja“. Lautet die Reihe „ja… ja, nein… nein“ und du willst das letzte „ja“, schreibst du bei „ja“ lo = mid und bei „nein“ hi = mid - 1. Dann muss die Mitte aufrunden: (lo + hi + 1) // 2. Sonst ist die Mitte bei benachbarten lo und hi gleich lo, lo = mid bewegt nichts, und die Schleife endet nie. Dieselbe Grenze wie in der Lektion zur binären Suche, nur von der anderen Seite.

Eine Antwort mit Bruchteil. Ist X etwa eine Geschwindigkeit in Metern pro Sekunde, besteht der Bereich aus reellen Zahlen, und lo und hi werden nie gleich. Dann läuft die Schleife eine feste Anzahl von Malen, zum Beispiel 60: Jedes Mal halbiert sich der Bereich, und nach 60 Halbierungen ist er kleiner als jede Genauigkeit, die dich interessiert.

Sieh es dir an

Miss: nacheinander gegen binär

Pakete von 1 bis 30 kg, 5 Tage. Die Operation ist ein Paket, das bei einer Prüfung geladen wird. Nacheinander wächst die Zahl der Proben mit n, und jede lädt n Pakete: O(n²). Binär macht etwa log₂ S Proben: O(n log n).

Jede Kapazität der Reihe nach O(n²)
Binäre Suche über die Kapazität O(n log n)

Algorithmus	n = 10	n = 100	n = 1.000	n = 10.000	n = 100.000
Jede Kapazität der Reihe nach	90	28.800	3.089.000	≈ 308.900.000	≈ 30.890.000.000
Binäre Suche über die Kapazität	70	1.100	14.000	180.000	2.100.000

Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

def min_capacity(weights, max_days):
    lo = max(weights)
    hi = sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if days(weights, mid) <= max_days:
            hi = mid
        else:
            lo = mid + 1
    return lo

Bei 1000 Paketen sind es 3.089.000 gegen 14.000. Über 1000 Paketen läuft „nacheinander“ nicht wirklich: Es würde Hunderte Millionen Pakete laden.

Übung

Die Packstationen am Boulevard

Löse die Aufgabe in deinem eigenen Editor.

So weit auseinander wie möglich. Am Boulevard gibt es sieben Stellen für Packstationen, bei 100, 400, 900, 1200, 2000, 2400 und 3100 m ab dem Start. Die Firma stellt 3 Packstationen auf und möchte, dass die zwei nächsten so weit auseinander liegen wie möglich, damit sie mehr von der Stadt abdecken. Was ist der größtmögliche kleinste Abstand?

Schreibe eine Prüfung can_place(spots, lockers, gap): Sie stellt eine Packstation an die erste Stelle und jede weitere an die erste Stelle, die mindestens gap Meter nach der vorigen liegt, und sagt, ob es für alle reicht. Suche binär den größten gap, für den die Prüfung „ja“ sagt.

Der größte kleinste Abstand: 1100 m

Weitere Aufgaben

Die Drucker. Drei Drucker drucken ein Etikett in 2, 3 und 7 Sekunden. In wie wenigen Sekunden drucken sie 500 Etiketten?
Die Kuriere. Jeder Kurier arbeitet höchstens 8 Stunden und nimmt die Bestellungen der Reihe nach. Die Bestellungen dauern 2, 3, 1, 4, 2, 5, 3 und 2 Stunden. Wie wenige Kuriere braucht man? Und wenn die Schicht 6 Stunden dauert?
Wie viele Proben. Füge min_capacity einen Probenzähler hinzu und vergleiche ihn mit der Zahl der Proben beim Nacheinander-Vorgehen für dieselben Pakete.

Test

Teste dich

1. Warum liefert die binäre Suche über die Kapazität die richtige Antwort?Weil Kapazitäten ganze Zahlen sindWeil, sobald die Kapazität X reicht, auch jede größere reicht: Die Antworten lauten „nein… nein, ja… ja“Weil die Pakete nach Gewicht sortiert sind

2. Die Probe sagt bei 26 kg „ja“. Was passiert mit hi?hi = 25: 26 wurde schon geprüfthi = 26: 26 kann die Antwort sein, wir suchen eine kleinerelo = 27

3. Zwischen welchen Werten wird die Kapazität gesucht?Von 0 bis 1000Vom schwersten Paket bis zur Summe aller PaketeVom leichtesten Paket bis zum schwersten

4. Welche Aufgabe löst man mit binärer Suche über die Antwort?Die nach Preis sortierten ProdukteDie kürzeste Zeit, in der drei Drucker 500 Bestellungen druckenDas billigste Produkt in einer Liste

Binäre Suche über die Antwort

Cookies