optimale Rundreise < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:41 Do 02.07.2009 | | Autor: | tynia |
Hallo. Habe nur eine kurze Verständnisfrage.
Also wenn ich eine optimale Rundreise in einem nicht vollständigen Graphen finden soll, muss ich dieses Problem doch erstmal auf einen vollständigen Graphen übertragen und dort dann die kürzesten Wege bestimmen. Dass bedeutet doch, wenn ich in dem ursprünglichen Graphen zwischen 2 Knoten keine direkte Verbindung habe, schaffe ich sie mir in meinem neuen Graphen durch den Umweg über einen anderen Knoten.
So jetzt finde ich mit einem Eröffnungsverfahren, z.B. Bester Nachfolger, eine Lösung und muss versuchen diese zu verbessern. Wenn ich damit fertig bin, habe ich doch meine optimale Lösung. Diese muss ich dann doch wieder übertragen auf meinen ürsprünglichen Graphen.
Ist es dann möglich, dass ein Knoten mehrfach durchlaufen wird?
Danke schonmal.
LG
|
|
| |
|
> Hallo. Habe nur eine kurze Verständnisfrage.
>
> Also wenn ich eine optimale Rundreise in einem nicht
> vollständigen Graphen finden soll, muss ich dieses Problem
> doch erstmal auf einen vollständigen Graphen übertragen
> und dort dann die kürzesten Wege bestimmen. Dass bedeutet
> doch, wenn ich in dem ursprünglichen Graphen zwischen 2
> Knoten keine direkte Verbindung habe, schaffe ich sie mir
> in meinem neuen Graphen durch den Umweg über einen anderen
> Knoten.
>
> So jetzt finde ich mit einem Eröffnungsverfahren, z.B.
> Bester Nachfolger, eine Lösung und muss versuchen diese zu
> verbessern. Wenn ich damit fertig bin, habe ich doch meine
> optimale Lösung. Diese muss ich dann doch wieder
> übertragen auf meinen ursprünglichen Graphen.
>
> Ist es dann möglich, dass ein Knoten mehrfach durchlaufen
> wird?
>
> Danke schonmal.
>
> LG
Hallo tynia,
Was ist mit "optimaler Rundreise" genau gemeint ?
Was ist gegeben ? (Knoten, Kanten, Kantenlängen, ...?)
und was für Nebenbedingungen sollen erfüllt werden ?
Gruß Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:02 Do 02.07.2009 | | Autor: | tynia |
Also, die Aufgabe lautet folgendermaßen:
ermittel im folgenden bewerteten Graphen eine kurze Rundreise
[Dateianhang nicht öffentlich]
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
|
| |
|
> Also, die Aufgabe lautet folgendermaßen:
>
> ermittel im folgenden bewerteten Graphen
> eine kurze Rundreise
>
> [Dateianhang nicht öffentlich]
Hallo tynia,
O.K. - und mit "Rundreise" ist wohl ein Weg
gemeint, der von einem beliebigen Knoten
ausgeht, alle Knoten mindestens einmal
trifft und schliesslich zum Ausgangsknoten
zurückführt. Die Gesamtlänge des zurückge-
legten Weges soll minimal sein. Dabei nehme
ich an, dass es nicht verboten ist, einzelne
Knoten oder Kanten mehr als einmal zu
benützen. Das könnte sich ja eventuell
durchaus lohnen, um die gesamte Reise-
strecke möglichst kurz zu halten.
Mit diesen Präzisierungen haben wir ein
klar formuliertes Problem.
LG Al-Chwarizmi
|
|
|
| |
|
> Also, die Aufgabe lautet folgendermaßen:
>
> ermittel im folgenden bewerteten Graphen eine kurze
> Rundreise
>
> [Dateianhang nicht öffentlich]
(Kantenlängen z.B. in km)
Hallo,
mit etwas Probieren - ohne ausgetüftelte
Methoden anzuwenden, komme ich bei
diesem Graph etwa auf die folgende
Rundreise, bei der jeder Knoten genau
einmal durchlaufen wird:
124657831
Es gibt allerdings eine um 4 km kürzere
Rundreise, wenn man nicht darauf beharrt,
dass jeder Knoten nur einmal besucht
werden darf !
Es kommt wirklich auf die exakte Frage-
stellung an. Man könnte ja z.B. auch nach
der kürzestmöglichen Rundreise fragen,
bei welcher jede Kante mindestens einmal
durchfahren wird.
LG Al-Chw.
|
|
|
| |
|
> Hallo. Habe nur eine kurze Verständnisfrage.
>
> Also wenn ich eine optimale Rundreise in einem nicht
> vollständigen Graphen finden soll, muss ich dieses Problem
> doch erstmal auf einen vollständigen Graphen übertragen
> und dort dann die kürzesten Wege bestimmen. Dass bedeutet
> doch, wenn ich in dem ursprünglichen Graphen zwischen 2
> Knoten keine direkte Verbindung habe, schaffe ich sie mir
> in meinem neuen Graphen durch den Umweg über einen anderen
> Knoten.
>
> So jetzt finde ich mit einem Eröffnungsverfahren, z.B.
> Bester Nachfolger, eine Lösung und muss versuchen diese zu
> verbessern. Wenn ich damit fertig bin, habe ich doch meine
> optimale Lösung. Diese muss ich dann doch wieder
> übertragen auf meinen ürsprünglichen Graphen.
>
> Ist es dann möglich, dass ein Knoten mehrfach durchlaufen
> wird?
Guten Tag tynia,
ich glaube jetzt habe ich deine Frage verstanden.
Ich habe mir ein einfaches Beispiel ausgedacht:
In einem Tal liegen, 20 km voneinander entfernt,
die Städte A und B. Von A aus erreicht man über
eine Strasse von 8 km Länge den Ort D, der oberhalb
von A in einem Seitental liegt. Ebenso führt von B
aus eine 5 km lange Nebenstrasse zum Ort C am
Berghang darüber. Ausserdem gibt es noch eine
Bergstrasse, welche C mit D verbindet und 45 km
lang ist.
Um den Graph vollständig zu machen, führt
man noch als "fiktive Kanten" folgende Verbin-
dungen ein:
AC=AB+BC (25 km)
BD=BA+AD (28 km)
Die kürzeste "Rundreise", welche alle 4 Orte
besucht, ist aber offensichtlich der Weg ADABCBA,
bei dem A und B mehr als einmal durchlaufen
wird. Es gäbe zwar die Rundtour ABCDA, welche
keinen Knoten zweimal durchläuft, aber sie ist
um 12 km länger als ABABCBA, weil sie die
"Touristentour" mit Bergfahrt ist und nicht
die "Expressroute" des DHL ...
Deine Frage ist also wohl mit "Ja" zu beant-
worten. Es kommt aber auf die genaue
Formulierung an. Ein DHL-Kurierdienst hat
eben z.B. andere Ziele als ein Gast, der einen
Ferientag in diesem Tal verbringen will ...
Zu dieser Art Probleme habe ich eine gute
Übersicht gefunden:
http://viadrina.euv-frankfurt-o.de/~ibl/docs/uebungen/InternationaleLogistik/uebung3.pdf
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:10 Fr 03.07.2009 | | Autor: | tynia |
Hallo. Danke für deine Antwort.
Ich habe mir das genauso gedacht wie du. Wenn nach einer kurzen Rundreise gefragt wird, kann man wohl die Knoten mehrfach durchlaufen. Wenn die Rundreise optimal sein soll oder hamiltonsch, dann darf jeder Knoten nur einmal durchlaufen werden.
LG
|
|
|
|
