Eigene Sortierlogik für Klassen: Beliebige Klasseninstanzen binär sortieren

Für Best-First Branch and Bound verfahren oder DP Ansätze

TL;DR

Binäre Suche (Link) ist signifikant schneller als stumpfes Suchen in Listen. In DP Ansätzen oder in Branch-and-Bound Implementierungen kann es vorkommen, dass wir immer den besten Knoten in einer Liste suchen. Da “Knoten” gelegentlich durch Klassen abgebildet werden, müssen Listen durchsucht werden in denen nicht nur Zahlen gespeichert werden, sondern komplexere Datenkonstrukte. Wie man ebendiese sortiert bzw. in bereits sortierte Listen einfügt, zeigt dieser Beitrag.

Ausgangslage

Nehmen wir an, wir wollten ein Lösungsverfahren für das Tourenplanungsproblem entwerfen. Wir entscheiden uns, die Tour Stück für Stück zu konstruieren und entwerfen hierfür einen mehrstufigen Ansatz.

• Auf jeder Stufe des Verfahrens fügen wir einen unbesuchten Ort an das Ende unserer Tour an
• Wir entscheiden uns die aktuelle Teillösung als Klasse zu implementieren, in der wir die folgenden Felder speichern
  • ort Der zunächst zu besuchende Ort
  • gesamtdauer Die bisherige Dauer der Tour (Lower Bound auf den Zielfunktionswert)
  • vorgaenger Ein Verweis auf eine Instanz der Klasse, die Informationen zum direkten Vorgänger von ort gespeichert hat.
  • anz_orte Die Anzahl Orte, die bis hierhin in der Tour gespeichert sind

class Knoten:
    def __init__(self, vorgaenger: Knoten, ort : int, gesamtdauer: int):
        self.ort = ort
        self.vorgaenger = None
        self.gesamtdauer = gesamtdauer
        anz_orte = 1
        if vorgaenger is not None:
            self.vorgaenger = vorgaenger
            self.anz_orte = vorgaenger.anz_orte + 1

Im Lösungsverfahren (das an dieser Stelle nicht weiter beschrieben werden soll) wird jetzt in jedem Schritt der aktuell “besten” Knoten aus einer Liste entnommen und die Tour so erweitert, dass ein bisher unbetrachteter Ort an die Tour angefügt wird. Hierfür wird also ein neuer Knoten erzeugt, und die entsprechenden Felder werden mit Werten belegt. Schematisch passiert das Folgende:

n = Knoten(None, 1, 0)
liste = [n]
while (noch nicht beste Lösung gefunden):

    # Identifiziere und entferne den besten Knoten in der Liste
    v = ... # Bester Knoten in der Liste

    naechster_ort = ... # Gemäß irgendeiner Logik
    gesamtdauer_tour = ... # Gemäß irgendeiner Logik
    n = Knoten(v, naechster_ort, gesamtdauer)

    # Füge n an die richtige Stelle in der Liste ein
    position = ... # Position von n in der Liste
    liste.insert(position, n)

Herausforderung

In einem naiven Ansatz könnten wir den besten Knoten in einer Liste finden, indem wir die ganze Liste durchsuchen. Hierfür wären jedesmal “n” Schritte nötig, wobei “n” die Anzahl Knoten in der Liste darstellt. Dies ist für große Listen unpraktikabel. Wir nutzen daher die binäre Suche und werden nachfolgend die Liste so sortieren (bzw. die Knoten so einfügen), dass

• Knoten mit der kleinsten Gesamtdauer am Ende der Liste liegen (Warum am Ende? Link).
• Unter allen Knoten mit der gleichen kleinsten Gesamtdauer, halten wir jene für “besser” bei denen die Teiltour aus mehr Orten besteht

Lösung

Wir können ein beliebiges Sortierkriterium implementieren, indem wir Pythons bisect verwenden. Damit die Sortierung nach unseren Wünschen erfolgt, müssen wir die Rang-Logik explizit definieren. Dies gelingt der Standardfunktion __lt___, um die wir die Klassen Knoten ergänzen. Diese Funktion wird dann von bisect aufgerufen, um Knoten miteinander zu vergleichen.

class Knoten:
    def __init__(self, vorgaenger: Knoten, ort : int, gesamtdauer: int):
        self.ort = ort
        self.vorgaenger = None
        self.gesamtdauer = gesamtdauer
        anz_orte = 1
        if vorgaenger is not None:
            self.vorgaenger = vorgaenger
            self.anz_orte = vorgaenger.anz_orte + 1
    
     def __lt__(self, other):
        # Sortierkriterium (Comparator)
        if self.gesamtdauer != other.gesamtdauer:
            return self.gesamtdauer > other.gesamtdauer  
        return self.anz_orte < other.anz_orte  

Nachfolgend gibt es ein kurzes Minimal-Working-Example (MWE):

import bisect 

# Beispielhafte Liste von Knoten-Instanzen
knoten_liste = [
    Knoten(Knoten(None,2,3), 3, 2), # 2 Orte
    Knoten(None, 1, 5),
    Knoten(None, 2, 3),
    Knoten(None, 4, 2),
]

sorted_knoten = []
for knoten in knoten_liste:
    # Wir bestimmen die Position
    position = bisect.bisect(sorted_knoten, knoten)
    # Und fügen den Knoten an die richtige Stelle
    sorted_knoten.insert(position, knoten)

# Überprüfen des Ergebnisses
for knoten in sorted_knoten:
    print(knoten)

Das Ergebnis ist wie erwartet das Folgende. es gibt zwei Knoten mit gesamtdauer = 2. Der Knoten, dessen Tour mehr Orte beinhaltet, wird weiter hinten in der Liste sortiert.

Knoten(ort=1, gesamtdauer=5, anz_orte=1)
Knoten(ort=2, gesamtdauer=3, anz_orte=1)
Knoten(ort=4, gesamtdauer=2, anz_orte=1)
Knoten(ort=3, gesamtdauer=2, anz_orte=2)

Umsetzung für das Verfahren

import bisect 

class Knoten:
    def __init__(self, vorgaenger: Knoten, ort : int, gesamtdauer: int):
        self.ort = ort
        self.vorgaenger = None
        self.gesamtdauer = gesamtdauer
        anz_orte = 1
        if vorgaenger is not None:
            self.vorgaenger = vorgaenger
            self.anz_orte = vorgaenger.anz_orte + 1
    
     def __lt__(self, other):
        # Sortierkriterium (Comparator)
        if self.gesamtdauer != other.gesamtdauer:
            return self.gesamtdauer > other.gesamtdauer  
        return self.anz_orte < other.anz_orte  


n = Knoten(None, 1, 0)
liste = [n]
while (noch nicht beste Lösung gefunden):

    # Identifiziere und entferne den besten (letzten) Knoten in der Liste
    v = liste.pop() 

    naechster_ort = ... # Gemäß irgendeiner Logik
    gesamtdauer_tour = ... # Gemäß irgendeiner Logik
    n = Knoten(v, naechster_ort, gesamtdauer)

    # Füge n an die richtige Stelle in der Liste ein
    position = bisect.bisect(liste, n)
    liste.insert(position, n)