Informatik, Andor und Python – Teil 2

Wie schon im ersten Teil erzählt, habe ich für eine Freundin ein paar Informatik-lastige Rätsel basierend auf dem Spiel „Die Legenden von Andor“ gebaut, die man mit ein bisschen Python-Code lösen konnte. Das erste Rätsel hätte man auch noch im Kopf lösen können, jetzt wird es schwieriger!

Nachdem die Helden am Baum der Lieder (Feld 57) angekommen sind, wollen sie nun alle Bewohner Andors besuchen. Wenn man genau hinschaut, kann man auf insgesamt 15 Feldern etwas erkennen, was nach einer Behausung aussieht, nämlich auf den Feldern 57, 64, 71, 84, 40, 32, 28, 72, 18, 24, 19, 2, 6, 5 und 0. Der zweite Teil des Rätsels lautet also: Wie ist der kürzeste Pfad von Feld 57 zu allen anderen bewohnten Feldern?

Auch hier weiß der geneigte Informatiker schnell: Das ist das Traveling Salesman Problem (TSP), was NP-vollständig ist. Das wird also schwer 🙂 Kurze Überschlagsrechnung: Es gibt 15! = 1307674368000 ≈ 1012 Möglichkeiten zu den 15 Orten zu reisen, das kann man auch mit einem Computer nicht mehr ausprobieren 🙁

Für das TSP gibt es verschiedene Algorithmen, die in annehmbarer Zeit zu einer relativ guten Lösung kommen können. Bei unserem relativ einfachen Problem sollten sie die optimale Lösung finden. Coolerweise gibt es von Google als Teil der „Google OR-Tools“ eine Python-Bibliothek, mit der man TSP (und andere) Probleme lösen kann!

Diese Bibliothek braucht als Eingabe eine Matrix mit den Distanzen zwischen allen Knoten. Hier kommt wieder der Dijkstra-Algorithmus aus dem ersten Teil zum Einsatz: Damit berechnen wir paarweise zwischen allen Knoten den kürzesten Pfad. Diesen Wert benutzen wir dann als Distanzwert für den TSP-Solver. Das ist ja auch logisch: Der Solver arbeitet nur noch auf den 15 „bewohnten“ Feldern, und nicht mehr auf allen 83 Feldern der Karte. Zwischen zwei Feldern würde man immer den kürzesten Weg verwenden, so dass wir diesen Wert quasi vorberechnen können. Gesucht ist damit „nur“ noch die Reihenfolge der 15 Felder.

Bei der Berechnung der Matrix gibt es noch eine Besonderheit: Für unser Problem ist es egal, auf jedem Feld die Route endet. Beim klassischen TSP muss der Pfad dabei immer zu einem definierten End-Feld führen. Wie in der Dokumentation beschrieben, kann man das Problem lösen, indem man ein „virtuelles Feld“ einführt, dass zu jedem Knoten eine Distanz von 0 hat. Damit macht es keinen Unterschied, welches Feld als letztes besucht wird. Der Algorithmus erreicht das Endfeld immer ohne weitere Kosten. Mit diesen Überlegungen können wir nun die Distanz-Matrix berechnen:

fields_to_visit = [57, 64, 71, 84, 40, 32, 28, 72, 18, 24, 19, 2, 6, 5, 0]
print("Number of fields to visit: {}".format(len(fields_to_visit)))

def build_dist_matrix(graph, fields):
  data = []
  # add row for "virtual depot" (distance to zero to every node, so that we can end everywhere)
  data.append([0] * (len(fields)+1))
  for start in fields:
    row = []
    # add entry for virtual depot
    row.append(0)
    for end in fields:
      solution = dijkstar.find_path(graph, start, end)
      row.append(solution.total_cost)
    data.append(row)
  return data

dist_matrix = build_dist_matrix(graph, fields_to_visit)
print("Dist matrix:")
print(dist_matrix)

Die Distanz-Matrix sieht dann so aus:

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 2, 5, 11, 6, 5, 6, 7, 6, 9, 7, 7, 6, 8, 7]
[0, 2, 0, 3, 9, 4, 5, 5, 6, 6, 8, 7, 7, 6, 8, 7]
[0, 5, 3, 0, 11, 3, 4, 4, 5, 5, 7, 6, 7, 6, 8, 7]
[0, 11, 9, 11, 0, 12, 13, 13, 14, 14, 16, 15, 16, 15, 17, 16]
[0, 6, 4, 3, 12, 0, 3, 3, 4, 4, 6, 5, 6, 5, 7, 6]
[0, 5, 5, 4, 13, 3, 0, 2, 3, 3, 5, 4, 4, 3, 5, 4]
[0, 6, 5, 4, 13, 3, 2, 0, 1, 1, 3, 2, 3, 3, 5, 4]
[0, 7, 6, 5, 14, 4, 3, 1, 0, 1, 2, 1, 3, 3, 4, 4]
[0, 6, 6, 5, 14, 4, 3, 1, 1, 0, 3, 1, 2, 2, 4, 3]
[0, 9, 8, 7, 16, 6, 5, 3, 2, 3, 0, 2, 4, 4, 2, 3]
[0, 7, 7, 6, 15, 5, 4, 2, 1, 1, 2, 0, 2, 3, 3, 3]
[0, 7, 7, 7, 16, 6, 4, 3, 3, 2, 4, 2, 0, 1, 2, 1]
[0, 6, 6, 6, 15, 5, 3, 3, 3, 2, 4, 3, 1, 0, 2, 1]
[0, 8, 8, 8, 17, 7, 5, 5, 4, 4, 2, 3, 2, 2, 0, 1]
[0, 7, 7, 7, 16, 6, 4, 4, 4, 3, 3, 3, 1, 1, 1, 0]

Ein Feld fällt etwas aus der Reihe (84) da es sehr abseits liegt. Die erste Zeile und Spalte ist 0, denn das ist der Abstand zu unserem „virtuellen“ Endfeld. Außerdem ist die Matrix natürlich symmetrisch und die Diagonale hat den Wert 0. Man hätte die Berechnung also noch etwas optimieren können 🙂

Für den restlichen Code gibt es zum Glück jeden Menge Beispiele in der Doku, die ich relativ unverändert übernommen habe:

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

num_heros = 1

model = {
  'distance_matrix': dist_matrix,
  'num_vehicles': num_heros,
  'starts': [fields_to_visit.index(tree_field)+1] * num_heros, #we start at the tree
  'ends': [0] * num_heros #we end at the "virtual depot"
}

manager = pywrapcp.RoutingIndexManager(len(model['distance_matrix']), model['num_vehicles'], model['starts'], model['ends'])
routing = pywrapcp.RoutingModel(manager)

def distance_callback(from_index, to_index):
    """Returns the distance between the two nodes."""
    # Convert from routing variable Index to distance matrix NodeIndex.
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return model['distance_matrix'][from_node][to_node]

transit_callback_index = routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

Wie man vielleicht durch die Variable num_heros schon ahnt, kann man sich natürlich auch fragen, was passiert, wenn man mehr als einen Helden benutzt. Dazu aber später mehr. Erstmal suchen wir einen zusammenhängenden Pfad 🙂 An ein paar Stellen ist der Code aber schon für mehr als einen Akteur eingerichtet.

Der Beispiel-Code spricht immer von „Vehicles“ die unterwegs sind, weil das TSP eine große Rolle bei der Tourenplanung von Lieferfahrzeugen spielt. Die Variablennamen habe ich erst mal so übernommen. Dann lassen wir den Solver mal arbeiten:

solution = routing.SolveWithParameters(search_parameters)
if not solution:
  raise(Exception(("No solution :(")))

print("Found solution with score {}".format(solution.ObjectiveValue()))

Bei mir lieferte das Programm quasi sofort eine Antwort. Für so kleine Probleme lässt sich also auch das TSP noch locker lösen. Alles eine Frage des richtigen Algorithmus 🙂 2006 wurde auch pla85900 gelöst, ein TSP mit 85.900 Knoten, da sind unsere 15 Knoten also noch überschaubar…

Nun bleibt noch etwas Code, um aus der Lösung auch die korrekte Reihenfolge zu extrahieren. Der Code ist wieder vorbereitet für mehr als eine „Vehicle“, was ihn hier etwas unnötig komplex macht. Zusätzlich arbeitet der Solver nur mit den Indices der Matrix. Wir müssen diese also noch in die korrekten Andor-Feld-Nummer übersetzen, und dabei das „virtuelle Depot“ auf Index 0 ignorieren. Auch hier basiert der Code auf dem Demo-Code von Google.

def get_routes(manager, routing, solution):
  routes = []
  for vehicle_idx in range(routing.vehicles()):
    index = routing.Start(vehicle_idx)
    prev_index = -1
    route = []
    total_costs = 0
    while not routing.IsEnd(index):
      route.append(manager.IndexToNode(index))
      if prev_index != -1:
        total_costs += routing.GetArcCostForVehicle(prev_index, index, vehicle_idx)
      prev_index = index
      index = solution.Value(routing.NextVar(index))
    routes.append({'indices': route, 'total_costs': total_costs})
  return routes

routes = get_routes(manager, routing, solution)

def route_to_fields(route):
  fields = []
  for i in route['indices']:
    if i != 0: #omit virtual depot
      fields.append(fields_to_visit[i-1]) #-1 because index 0 is the virtual depot
  return fields

for route in routes:
  print(route_to_fields(route))

print("Number of hours of this route: {}".format(max([r['total_costs'] for r in routes])))

Damit erhalten wir dann die Lösung: Der kürzeste Pfad führt über die Felder 57, 32, 6, 2, 0, 5, 24, 72, 19, 18, 28, 40, 71, 64 und 84, und ist 36 Felder lang.

Auch wenn der Code jetzt vielleicht ein bisschen kompliziert aussieht: Der wirklich anspruchsvolle Code für den TSP-Solver steckt in der Google-Bibliothek. Dank der umfangreichen Beispiele war es auch recht einfach, mein Rätsel damit zu lösen. Coole Sache, Google!

XKCD 287: NP-Complete

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert