Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » Kürzester Weg, einen Graph aufzudröseln
Druckversion
Druckversion
Autor
Universität/Hochschule J Kürzester Weg, einen Graph aufzudröseln
Carmageddon
Senior Letzter Besuch: im letzten Monat
Dabei seit: 22.12.2009
Mitteilungen: 663
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2021-03-03


Hallo Leute,

ich habe mal eine Frage - genauer gesagt, bin ich auf der Suche nach einen effizienten (Optimierungs-) Algorithmus um folgendes Problem zu lösen.

Ich bin bei Graphentheorie relativ unbedarft, es könnte also gut sein, dass es für dieses Problem bereits einen super schnellen Algorithmus gibt. Das wäre natürlich super!

Also, ich habe einen gerichteten Graphen, der von einem Node S zu einem Node E geht. Er ist schleifenfrei.

Hier ist ein Minimal-Beispiel, von so einem Graphen.



Graph 1:



Nun suche ich die "billigste" Lösung, diesen Graphen aufzudröseln in folgendem Sinne:

Ich fange mit der "Spitze" des Graphen an - das wäre E. Nun entferne ich E aus dem Graphen und betrache alle Punkte die keinen Nachfolger haben. Das wäre 4 und 3. Nun habe ich zwei Möglichkeiten weiter zu machen: Ich entferne erst die 4 oder die 3. So hangel ich mich durch den Graphen bis alle Nodes (bis auf S) abgearbeitet sind.

Konkret gibt das folgenden Graph. Ich verwende Graph-Viz um die Graphen zu erstellen, d.h. die Nodes sollten eindeutige Namen haben. Die Zahl hinter dem # ist also einfach nur eine fortlaufende Nummer und kann ignoriert werden.

Grob gesagt: Ich entferne immer eine lose Spitze und hangel mich dann rekursiv bis zu S vor. Das ganze sieht dann so aus


Graph 2



Jede Kante hat natürlich ein Gewicht, das habe ich der Übersicht halber nicht angegeben. Wenn man einen Namen braucht, können wir sie $w_{ij}$ nennen.

Gesucht ist jetzt der kürzeste Weg durch diesen rekursiv erstellten Graphen Graph 2 von E zu S - dieser stellt für mich die gesuchte optimale Variante für Graph 1 da.

Gut so viel zur Erklärung. Natürlich kann man sagen: Stelle doch einfach den rekursiven Graphen auf und berechne den kürzesten Weg. Ja klar, so mache ich es auch im Moment. Allerdings kann dieser Graph sehr schnell sehr groß werden. (im schlimmsten Fall gibt es n! verschiedene Möglichkeiten, bei n Knoten....)

Und tatsächlich brauche ich auch nicht DEN billigsten Weg durch Graph 2, sondern mir würde eine gute Näherung langen.
Am liebsten würde ich den Graph 2 gar nicht aufstellen, da dies extrem viel Zeit frisst im Moment.

Kennt jemand einen Algorithmus (entweder aus der Optimierung oder aus der Graphentheorie), der mich hier unterstützen könnte?

Ich hoffe, ich konnte mein Problem etwas verdeutlichen.

lg


-----------------
Zitat: "Es gibt einen Beweis aus der Physik: Er ist kurz, er ist elegant... und falsch"



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2754
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2021-03-03


Für kreisfreie, gerichtete Graphen ohne hilfreiche Zusatzinformationen bietet sich Dijkstra an.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Carmageddon
Senior Letzter Besuch: im letzten Monat
Dabei seit: 22.12.2009
Mitteilungen: 663
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2021-03-03


2021-03-03 17:09 - DerEinfaeltige in Beitrag No. 1 schreibt:
Für kreisfreie, gerichtete Graphen ohne hilfreiche Zusatzinformationen bietet sich Dijkstra an.

Hmm, das Problem ist nur: Im Graph 1 habe ich z.B. keine Verbindung von 1 zu 3 - im Graph 2 hingegen schon.
Ich wüsste spontan nicht, wie man diese Information herbekommt, denn diese ergibt sich ja nicht aus dem Graphen selber, sondern aus der Rekursion.


-----------------
Zitat: "Es gibt einen Beweis aus der Physik: Er ist kurz, er ist elegant... und falsch"



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2754
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2021-03-03


Vielleicht erklärst du noch einmal, was das eigentliche Ziel ist oder zumindest, wie der Graph 2 entsteht, also wie du die Kanten berechnest.




-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Carmageddon
Senior Letzter Besuch: im letzten Monat
Dabei seit: 22.12.2009
Mitteilungen: 663
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2021-03-03


2021-03-03 19:21 - DerEinfaeltige in Beitrag No. 3 schreibt:
Vielleicht erklärst du noch einmal, was das eigentliche Ziel ist oder zumindest, wie der Graph 2 entsteht, also wie du die Kanten berechnest.



Graph 1:


Hinter dem Graphen kann man sich z.B. Gegenstände in einer Box vorstellen, welche sich gegenseitig blockieren. Ist z.B. 1 mit 2 verbunden, bedeutet dies, dass Gegenstand 1 von 2 blockiert wird.

Konkret hier wird z.b. 1 und 2 von 4 blockiert.

Jeder Gegenstand hat gewisse Kosten um verräumt zu werden. Natürlich kann ich nur Gegenstände nehmen, welche von keinem anderen verdeckt werden. Im Graphen bedeutet dies: Ich kann nur Knoten "abarbeiten" welche keinen Nachfolger haben. Den Punkt "S" und "E" kann man mal ignorieren, sie symbolisieren nur den Boden der Box und die Luft oben drüber, wenn man so möchte.

Zusätzlich gibt es noch "Wegkosten". D.h. wenn ich 3 nehme und dann 4, habe ich noch zusätzliche Kosten, welche von Knoten 3 und 4 abhängen. Knoten 3 und 2 könnten wieder andere Wegkosten haben. Ziel ist es eine möglichst kostenkünstige Sequenz zu finden, die Gegenstände zu verräumen.


So entsteht auch der folgende Graph.

Graph 2:


Ich erzeuge alle möglichen zulässigen Kombinationen die Gegenstände zu verräumen und nehme dann die günstigste.

Jeder Weg von E zu S im obigen Graph liefert mir eine mögliche zulässige Sequenz die Gegenstände zu verräumen.

Ich hoffe nun macht auch mein Kommentar von oben Sinn: Im Graph 1 werden keine möglichen "Bewegungskosten" berücksichtigt, da z.b. 1 gar nicht mit 3 verbunden ist, sie aber durchaus nacheinander aus der Box genommen werden können.


Da die Boxen durchaus recht viele Gegenstände beinhalten können wird mein Graph mit allen möglichen Kombinationen sehr groß und das ganze dauert dann ein bisschen zu berechnen. Es funktioniert natürlich, aber ich dachte ich frage hier mal, ob man die optimale Sequenz direkt aus Graph 1 berechnen kann (ohne den großen Grapen 2 aufzustellen) - ich wüsste aber nicht welchen Algorithmus man nehmen könnte.

Eventuell sollte ich mich auch komplett von Graphen trennen und versuchen das Ganze als Optimierungsproblem zu formulieren.
Die Nebenbedingungen (was wird wann von was blockiert) könnten allerdings etwas tricky werden - deswegen habe ich erstmal den Graphen-Ansatz gewählt.


-----------------
Zitat: "Es gibt einen Beweis aus der Physik: Er ist kurz, er ist elegant... und falsch"



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6771
Herkunft: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2021-03-03


Hallo Carmageddon,

habe ich das richtig verstanden? Wenn ich erst 3, dann 4 und dann 1 wegnehme, kann das andere Kosten verursachen, als wenn ich erst 4, dann 1 und dann 3 wegnehme?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Carmageddon
Senior Letzter Besuch: im letzten Monat
Dabei seit: 22.12.2009
Mitteilungen: 663
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2021-03-03


2021-03-03 20:50 - StrgAltEntf in Beitrag No. 5 schreibt:
Hallo Carmageddon,

habe ich das richtig verstanden? Wenn ich erst 3, dann 4 und dann 1 wegnehme, kann das andere Kosten verursachen, als wenn ich erst 4, dann 1 und dann 3 wegnehme?

Exakt!

Zum Beispiel wenn die Box an verschiedenen Stellen ausgeladen wird. Beispiel: wir haben 4 Plätze, die einfach im Abstand von einem Meter in einer Reihe aufgestellt werden.  (1  -  2  -  3  -  4)

1 muss in Platz 1, 2 in Platz 2 usw.

3 nach 4 nach 1 macht 4 m Laufstrecke
4 nach 1 nach 3 macht 5 m Laufstrecke

Edit: Achso: Die Laufstrecke zwischen zwei Stellplätzen wäre hier zusammen mit den Kosten, die ich brauche um den Gegenstand aus der Box zu nehmen und zu verräumen die Gewichte der Kante im Graph 2.

Nehmen wir mal an, jeder Gegenstand braucht gleich lang zum Herrausnehmen, so wäre der Weg 4->1->3 teurer als 3->4->1


-----------------
Zitat: "Es gibt einen Beweis aus der Physik: Er ist kurz, er ist elegant... und falsch"



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6771
Herkunft: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2021-03-04


Hallo noch mal,

wenn man für Graph 1 = (V, A) folgendes wählt:

V = {S, E, 1, 2, ..., n}, A = {(S.i): i = 1,...,n} U {(i,E): i = 1,...,n}

dann liegt ja das klassische TSP vor, was ja bekanntlich nicht einfach zu lösen ist. Für einen komplizerteren Graph 1 wird es vermutlich nur in Ausnamefällen einfacher. Z. B. wenn

A = {(S,1), (1,2), (2,3), ..., (n-1,n), (n,E)}



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Carmageddon
Senior Letzter Besuch: im letzten Monat
Dabei seit: 22.12.2009
Mitteilungen: 663
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2021-03-04


2021-03-04 10:48 - StrgAltEntf in Beitrag No. 7 schreibt:
Hallo noch mal,

wenn man für Graph 1 folgendes wählt:

V = {S, E, 1, 2, ..., n}, E = {(S.i): i = 1,...,n} U {(i,E): i = 1,...,n}

dann liegt ja das klassische TSP vor, was ja bekanntlich nicht einfach zu lösen ist. Für einen komplizerteren Graph 1 wird es vermutlich nur in Ausnamefällen einfacher. Z. B. wenn

E = {(S,1), (1,2), (2,3), ..., (n-1,n), (n,E)}


Ja das habe ich befürchtet...

Eigentlich wollte ich mich um TSP drücken - bzw. um die Variante die ich hier vorliegen habe, aber wahrscheinlich werde ich da nicht drum rum kommen. Im Moment verwende ich ein paar Einschränkungen um mir das Leben einfach zu machen und um schneller zu werden.



Trotzdem Dank euch. 🙂


-----------------
Zitat: "Es gibt einen Beweis aus der Physik: Er ist kurz, er ist elegant... und falsch"



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Carmageddon hat die Antworten auf ihre/seine Frage gesehen.
Carmageddon hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]