Rundreiseproblem lösen mit Spaltensummenverfahren

Question

Aufgabenstellung: P1 P2 P3 P4 P5 P6 P1 0 4 4 2 8 3 P2 4 0 5 7 6 5 P3 4 5 0 5 9 3 P4 2 7 5 0 10 4 P5 8 6 9 10 0 7 P6 3 5 3 4 7 0 Sum 21 27 26 28 40 22 Ziel ist es, die optimale Rundreise zu finden, mithilfe des "Spaltensummenverfahrens" Man soll dabei bei P1 STARTEN und bei P1 ENDEN. Im Skript steht jedoch man startet bei den 3 größten Spaltensummen. Das währen ja in der Aufgabe P2, P4 und P5. Aber P1 ist ja vorgegben, also würde ich nun die Rundreise mit P1-P5-P1 starten. In der Lösung steht jetzt als Start 1-6-3-1. Das kann ich nicht wirklich nachvollziehen. Wie kommt man da drauf?

Answer 1

Wenn du die größten Spaltensummen nimmst sollten das ja zumindest P2, P4 und P5 sein.

Offensichtlich hat der Prof hier mit den 3 niedrigsten Spaltensummen angefangen P1, P6 und P3.

Ich kenne das Verfahren der Spaltensummen nicht. Aber Du könntest ja einmal mit den größten und einmal mit den kleinsten Spaltensummen anfangen und schauen welches Ergebnis nachher besser ist.

Wie das weiter geht weißt du wenn du die 3 Orte hast?

Comments

Was mir halt unklar ist wieso P6 und P3?

P1 ist ja als Start und Ende vorgegeben. Wieso nimmt man jetzt noch 2 Werte? Weil man ja laut Skript mit 3 Orten anfängt. und mit 1-6-3-1 hat man 4.

Komischerweise findet man zu diesem Verfahren auch rein gar nichts im Internet, muss wohl eine Erfindung vom Prof sein.

der Rest der Aufgabe ist dann recht einfach und verständlich

---

Bei 1-6-3-1 hast du 3 Orte, nämlich 1, 6 und 3. Die 1 steht am anfang weil wir dort beginnen und am Ende weil wir auch dort wieder Enden.

Das macht man weil man ja nicht unbedingt einen Kreis zeichnen möchte. 

Du findest etwas bei Google Books über das Verfahren.

https://www.google.de/search?q=rundreiseproblem+spaltensummen

Der Link ist noch mit auf der ersten Seite.

---

Danke das hilft schonmal.

Wenn ich mir das Beispiel im Buch so anschaue, klaube ich das die Lösung von der Aufgabe oben falsch ist. Ansonsten macht das ja keinen Sinn.

In einer anderen Aufgabe hat er auch mit den größten angefangen.

So werde ich es dann auch in der Klausur machen, also nach der Anleitung im Buch und in meinem Skript, mit den größten anfangen.

---

Wie gesagt kann man es ja mal auf 2 Arten probieren. Mal schauen wie die Ergebnisse sind. Gerade bei Hausaufgaben kann man ja mal Experimentieren wofür später in der Arbeit keine Zeit da ist.