Hallo,
ich suche ein geeignetes Modell TSP mittels eines Baumes. Es sollte ähnlich wie beim Rucksackproblem(mittels Entscheidungsbaum(binärer Baum)) sein.
Bin da ein bisschen am Basteln, aber leider komme ich nicht voran. Leider weiss ich nicht, was genau was ich in dem Knoten speichern muss. Beim Rucksack speichert man den max. Wert den man den man erreichen kann und die max. Kapazizät, die zur Verfügung steht. Dann kann man mit den Schnitt-, Zulässigkeits- und Verzweigungsregeln eine optimale Lösung berechnen. Beim TSP arbeiten aber keine Parameter gegeneinander, so, dass es nie zu ungültigen Knoten kommt(höchstens zu schlechte Knoten).
Leider weiss ich nicht so genau, wie ich die untere Schranke berechnen soll. Mittels minimalen Spannbaum?
Wäre nett, wenn da einige Vorschläge kommen bgl. Berechnung der unteren Schranke und den Branch & Bound Regeln.
Felix