Frage von jannde, 105

Chinese Postman Problem?

Betrachtet wird das Gitternetz eines 8 mal 8 Felder großen Schachbrettes. Die 81 Gitterpunkte stellen Straßenkreuzungen dar. Die Kreuzungen sind über Kanten der Länge 1 mit den waagerecht beziehungsweise senkrecht direkt benachbarten Kreuzungen verbunden. Die so entstehenden waagerechten Straßen können in beide Richtungen durchfahren werden, die 1.,3.,5.,7. und 9. senkrechte Straße sind auf der gesamten Länge Einbahnstraßen von oben nach unten, die 2.,4.,6. und 8. von unten nach oben. Im bis hierhin definierten Graphen werden nun noch die 4 Felder im Zentrum des Schachbrettes inklusive der Straßenorientierung gemeinsam um 90° im Uhrzeigersinn gedreht. Die minimale Anzahl der in der optimalen Lösung des auf obigem Graphen definierten Chinese-Postman-Problems mehrfach besuchten Kanten beträgt dann?

22

23

24

Antwort
von yoshlas, 2

Hast du mal versucht es z.B. mit CPLEX zu lösen?Mein Idee wäre: binäre Variable x[t,d,a,b]=1 gdw zum Zeitpunkt t geht man in Richtung d zum Knoten (a,b) (Zeile,Spalte).t dann groß genug wählen, z.B. 200 und dafür sorgen, dass man nur auf dem Startpunkt auch stehen bleiben kann, um überschüssige Zeit zu verbrauchen. Dann führst du ne Variable v(e) ein, die für jede Kante e zählt, wie oft sie besucht wurde und minimierst über die Anzahl der v(e), die > 1 sind.




   Ich hatte es vorhin mal versucht zu implementieren, aber es kam immer ne Fehlermeldung dass bestimmte Variablen nicht definiert seien, die ich aber definiert hab, echt nervig -.- Aber ist an sich nicht so schwer, du musst halt nur an einiges denken: z.B. wie du nicht gehen darfst: auch vom Rand nicht aus dem Brett raus etc., dass du am gleichen Punkt ankommst wo du gestartet hast und, dass du alle Kanten min. ein mal besuchst^^

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten