Schnellste Autobahnstrecke

Moderator: Algorithmische Modellierung

Benutzeravatar
Malou
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 19. Jun 2016 17:54

Schnellste Autobahnstrecke

Beitrag von Malou » 17. Aug 2017 10:12

Guten Tag,

Hiermit möchte ich eine Frage bezüglich "case study 5: fastest highway route" stellen.

Und zwar: ist die Bedingung, dass nur eine Kante aus jeden Knoten gehen soll nicht redundant?
Meine Überlegung lautet wie folgt: Ich gehe davon aus, dass es nur positive Distanzwerte gibt. Wir suchen ja den kürzesten Pfad, wollen also die Summe der im Pfad enthaltenen Kanten minimieren. Wenn ich in einem Knoten die Wahl hab, zwei ausgehende Kanten a und b in meinem Pfad hinzufügen oder nur eine davon werde ich immer die Wahl treffen, nur eine davon auszuwählen. Weil a (oder b) ist immer kleiner gleich a + b. Deshalb braucht man die Bedingung nicht, oder?

Vielen Dank für die Antwort,

LG

Malou

steffen.maus
Neuling
Neuling
Beiträge: 10
Registriert: 8. Jun 2012 15:54

Re: Schnellste Autobahnstrecke

Beitrag von steffen.maus » 24. Aug 2017 14:40

Du meinst diese Zeile?

forall ( i in N ) sum ( j in N ) is_used[i,j] <= 1;

Ich würd mich anschließen und sagen, dass die bereits durch das minimize (und die nur positiven Kantenlängen) erfüllt wird...

Eventuelle Außnahme:
Es könnte Kanten der Länge 0 geben (ich denke dabei an das Umsteige-Beispiel bei Bahnhöfen oder das Modellieren von unerlaubten Abbiegemöglichkeiten bei Kreuzungen). Dadurch würdest du dann auch Lösungen erhalten, die keinen linearen Pfad ergeben, sondern an manchen stellen zusätzliche Sackgassen aufweisen.

Also doch lieber drinnen lassen die Bedingung ;)

Antworten

Zurück zu „Algorithmische Modellierung“