Die Mathe-Redaktion - 29.03.2020 20:03 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps für den MP

Werbung

Bücher zu Naturwissenschaft und Technik bei amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 650 Gäste und 24 Mitglieder online

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » Algorithmus von Ford und Knotenpotentiale
Druckversion
Druckversion
Autor
Universität/Hochschule J Algorithmus von Ford und Knotenpotentiale
fussball99
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 19.11.2011
Mitteilungen: 330
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-12-18


fed-Code einblenden



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6275
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-12-18


1) Im Text wird gesagt, was $y_v$ ist, ob man $y_v$ als "das Potential" bezeichnet steht da nicht.
Aber vermutlich ist das in deiner Vorlesung / deinem Buch so gemacht worden.
2) Wie soll man das beantworten? Vielleicht: "Weil es nicht sinnvoll ist."?
Das Wort "Potential" soll schon andeuten, dass es zweckmäßig ist, den _Unterschied_ zwischen den Potentialen zu betrachten.
Vielleicht wäre das bei der Darstellung $c_{vw}\geq y_w-y_v$ deutlicher.
Die Ungleichung wird jedenfalls in genau der Form benötigt, um später damit etwas bestimmtes zeigen zu können. Sie ist auch nur so richtig und nicht in irgendeiner anderen Form wie $y_v+y_w\leq c_{vw}$.
Welche "beiden" Kosten meinst Du eigentlich, außer $c_{vw}$?
3) Was ist denn für dich der Unterschied zwischen "Längen" und "Kosten"? Hier ist beides gleichbedeutend. Es kommt (leider) nicht so selten vor, dass man $c_{vw}$ als die "Kosten" der Kante v-w einführt und dann drei Sätze später von "Länge" der Kante spricht. Das liegt wohl daran, dass das Gehirn bei solchen anschaulichen Begriffen gerne auf bekannte Begriffe und Eigenschaften zurückgreift, ohne dass uns das bewusst wird.
Ich finde das Wort "Kosten" besser, weil es allgemeiner ist (beim Bergsteigen, aber auch beim Autofahren oder bei der Verlegung von Erdkabeln kommt es oft gar nicht so sehr auf die Länge einer Verbindungsstrecke an, sondern darauf, wie mühsam, zeitraubend oder teuer die Strecke ist.
Außerdem bezeichnte man mit "Länge" oft auch einfach die Anzahl der Kanten eines Weges.



  Profil  Quote  Link auf diesen Beitrag Link
fussball99
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 19.11.2011
Mitteilungen: 330
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2019-12-18


fed-Code einblenden



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6275
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-12-18


Hast Du einen Link auf den von Dir erwähnten Algorithmus?
Ich muss hier etwas spekulieren, was der Algorithmus genau tut.

Wahrscheinlich muss man etwas genauer unterscheiden zwischen:
a) dem Zustand am Ende des Algorithmuses
b) dem Zustand bei einem Zwischenschritt

Man startet vermutlich mit einer vorläufigen Belegung der Variablen $y_v$(*). Dann überprüft man, ob die Ungleichungen erfüllt sind. Ist das nicht der Fall, so kann/muss $y_w$ verringert werden. Dies kann dazu führen, dass weitere Ungleichungen nicht erfüllt sind (in denen $y_w$ links steht), was zu weiteren Reduktionen der Potentiale führt usw.
Sind letzten Endes alle Ungleichungen erfüllt und ist das Potential des Startknotens gleich 0, _dann_ geben die anderen Potentiale die Längen kürzester Wege wieder.

(*) Die Startbelegung muss dazu mindestens so groß sein, wie die Länge des kürzesten Weges. Typischerweise setzt man sie auf unendlich, außer im Startknoten, wo man das Potential auf 0 setzt.



  Profil  Quote  Link auf diesen Beitrag Link
fussball99
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 19.11.2011
Mitteilungen: 330
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2019-12-19





Das ist der Algorithmus (laut VL eine Vorstufe des Bellman-Ford-Algorithmus) für kürzeste Wege.

Wir reduzieren das Potential, solange die Ungleichung für bel. Kante (u,v) erfüllt ist und erhalten den kürzesten Weg vom Startpunkt r zum gewählten Knoten v.

Soweit ich das verstehe, ist p der Vorgängerknoten.



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6275
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-12-19


OK, das ist ja ziemlich genau das, was ich auch beschrieben habe.
Mir ist jetzt auch klar, warum der Algorithmus in der Form eher unbekannt ist, da im Schritt 3 ja völlig offen gelassen wird, wie man so ein Paar (v,w) möglichst effizient bestimmt und in welcher Reihenfolge die Aktualisierungen vorgenommen werden, damit man in möglichst wenigen Iterationsschritten ans Ziel kommt.
So wie der Algo da steht, hat er vermutlich exponentielle Laufzeit.

Also _am Ende_ gibt $y_v$ die Länge eines kürzesten Weges von $r$ nach $v$ an und am Ende erfüllt $y$ die Potentialeigenschaft und am Ende enthält $p_v$ den jeweiligen Vorgängerknoten auf einem kürzesten Weg von $r$ nach $v$.



  Profil  Quote  Link auf diesen Beitrag Link
fussball99
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 19.11.2011
Mitteilungen: 330
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2019-12-19


2019-12-19 16:58 - Kitaktus in Beitrag No. 5 schreibt:
OK, das ist ja ziemlich genau das, was ich auch beschrieben habe.
Mir ist jetzt auch klar, warum der Algorithmus in der Form eher unbekannt ist, da im Schritt 3 ja völlig offen gelassen wird, wie man so ein Paar (v,w) möglichst effizient bestimmt und in welcher Reihenfolge die Aktualisierungen vorgenommen werden, damit man in möglichst wenigen Iterationsschritten ans Ziel kommt.
So wie der Algo da steht, hat er vermutlich exponentielle Laufzeit.

Also _am Ende_ gibt $y_v$ die Länge eines kürzesten Weges von $r$ nach $v$ an und am Ende erfüllt $y$ die Potentialeigenschaft und am Ende enthält $p_v$ den jeweiligen Vorgängerknoten auf einem kürzesten Weg von $r$ nach $v$.

Genau so ist es. Er hat exponentielle Laufzeit und wird in der Praxis auch kaum berücksichtigt.

Danke dir!  😄



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5607
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-12-19


2019-12-19 17:47 - fussball99 in Beitrag No. 6 schreibt:
Genau so ist es. Er hat exponentielle Laufzeit

Hallo,

die \(c_{v,w}\) sind alle positiv, nehme ich an. Vielleicht habe ich den Algorithmus noch nicht ganz verstanden... Wenn immer eine Kante (v,w) zum Baum hinzugefügt wird, verringert sich die Summe aller \(y_w\). Und man läuft in keine "Sackgasse". Um solch eine Kante zu finden, muss man in Schritt 3 schlimmstenfalls immer wieder alle Kanten durchprobieren, aber das sind weniger als \(n^2\) Operationen, wenn n die Knotenzahl ist. Wie kann hier eine exponentielle Laufzeit entstehen?

Gruß
StrgAltEntf



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5607
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2019-12-19


Das habe ich noch gefunden, werde aber noch nicht ganz schlau draus:

(a) Prove that Ford’s generic shortest-path algorithm (while the graph contains a tense edge, relax it) can take exponential time in the worst case when implemented with a stack instead of a priority queue (like Dijkstra) or a queue (like Shimbel). Specifically, for every positive integer n, construct a weighted directed n-vertex graph \(G_n\), such that the stack-based shortest-path algorithm call R \(\Omega(2^n)\) times when \(G_n\) is the input graph. [Hint: Towers of Hanoi.]



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6275
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2019-12-20


Der Einfachheit halber lasse ich mal Mehrfachkanten zu.
Angenommen $G=(V,E)$ ist ein Graph mit n-1 Knoten, der mindestens $2^{n-1}$ Schritte braucht, um vom Startknoten $r_{n-1}$ aus die kürzesten Wege zu berechnen. Sei $L$ die Länge des längsten kürzesten Weges von $r_{n-1}$ aus.

Wir konstruieren nun einen Graph $G'=(V',E')$ mit $V'=V\cup\{r_n\}$, $E'=E\cup\{e_{n1},e_{n2}\}$, wobei $e_{n1}$ und $e_{n2}$ beide von $r_n$ nach $r_{n-1}$ verlaufen und $e_{n1}$ die Kosten $L$ und $e_{n2}$ die Kosten $0$ hat.
In der Reihenfolge, in der wir die Kanten abarbeiten stehe $e_{n1}$ ganz vorn und $e_{n2}$ ganz hinten.

Was passiert nun: Man wird erst $e_{n1}$ abarbeiten, dann wird man all die Schritte machen, die man in $G$ machen würde (mindestens $2^{n-1}$ Schritte), dann würde man $e_{n2}$ abarbeiten und feststellen, dass man all die Schritte in $G$ nochmal machen muss.
Im Vergleich zu $G$ hat sich der Aufwand damit mehr als verdoppelt.



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5607
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2019-12-21


Danke Kitaktus,

ja, das sieht so aus, dass man das zu einem Beispiel mit einem einfachen Graphen (ohne Multikanten) ausbauen kann.

Das mit den Türmen von Hanoi (siehe #8) konnte ich noch nicht zuende überlegen.

Das Drei-Türme-Probem mit n Scheiben könnte man in einen Graphen übersetzen, bei dem ein Zustand (Knoten) aus einer Partition (A,B,C) von {1,...,n} besteht. Davon gibt es \(3^n\) viele. \((\{1,...,n\},\emptyset,\emptyset)\) ist der Startzustand.

Ein Zustand (A,B,C) mit \(A\neq\emptyset\) und \(a=\min A\) kann dann in einen Zustand \((A\setminus\{a\},B\cup\{a\},C)\) überführt werden, falls \(a<b\) für alle \(b\in B\). (Analog für Umschichtungen anderer Türme.) Jede Umschichtung hat die Kosten 1.

Beachte, dass die Größe des Graphen bereits exponentiell in n ist.



  Profil  Quote  Link auf diesen Beitrag Link
fussball99
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 19.11.2011
Mitteilungen: 330
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, vom Themenstarter, eingetragen 2020-02-26


2019-12-19 16:58 - Kitaktus in Beitrag No. 5 schreibt:
OK, das ist ja ziemlich genau das, was ich auch beschrieben habe.
Mir ist jetzt auch klar, warum der Algorithmus in der Form eher unbekannt ist, da im Schritt 3 ja völlig offen gelassen wird, wie man so ein Paar (v,w) möglichst effizient bestimmt und in welcher Reihenfolge die Aktualisierungen vorgenommen werden, damit man in möglichst wenigen Iterationsschritten ans Ziel kommt.
So wie der Algo da steht, hat er vermutlich exponentielle Laufzeit.

Also _am Ende_ gibt $y_v$ die Länge eines kürzesten Weges von $r$ nach $v$ an und am Ende erfüllt $y$ die Potentialeigenschaft und am Ende enthält $p_v$ den jeweiligen Vorgängerknoten auf einem kürzesten Weg von $r$ nach $v$.


Hallo Kitaktus,

muss diesen Thread nochmal hervorrufen. In der Zwischenzeit habe ich den Bellman-Ford gelernt, der ja bekannterweise negative Kreise erkennt, falls sich im n-ten Iterationsschritt die Potentiale (Länge kürzester Wege) noch einmal ändern. Falls keine Änderung eintritt, gibt stoppt der Algo und gibt die einzelnen kürzesten Wege für alle Knoten aus.


Jetzt zu meiner Frage: Eigentlich macht der Bellman-Ford doch genau das Gleiche, wie der Algo in Beitrag No. 4 oder? Mir ist leider nicht genau klar, was der gravierende Unterschied ist.

Du hattest geschrieben, dass die Auswahl der Kante und Reihenfolge in Schritt 3 nicht klar definiert ist, aber das ist bei Bellman-Ford doch auch nicht klar definiert oder?

Man prüft doch einfach alle Kanten nacheinander, ob die Potential-Bedingung weiterhin erfüllt ist.

Vielleicht kannst du mir den Unterschied kurz erklären... Danke!




  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6275
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2020-02-26


So wie ich die Algorithmen verstehe, besteht der Unterschied in Folgendem:
Bei Ford ist nicht (genügend / passend) eingeschränkt, wann welche Kante ausgewertet wird. Man kann sehr lange rumrödeln, ehe man eine bestimmte Kanten überhaupt zum ersten mal ansieht.
Bei Bellmann-Ford schaut man jede Kante in jedem Durchlauf genau einmal an.
Dadurch kennt man nach der ersten Runde (also nach m Auswertungen, m = Kantenanzahl) alle kürzesten Verbindungen, die aus genau einer Kante bestehen, nach der zweiten Runde alle kürzesten Verbindungen aus zwei Kanten usw.



  Profil  Quote  Link auf diesen Beitrag Link
fussball99
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 19.11.2011
Mitteilungen: 330
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, vom Themenstarter, eingetragen 2020-02-29


Dankeschön!🤗



  Profil  Quote  Link auf diesen Beitrag Link
fussball99 hat die Antworten auf ihre/seine Frage gesehen.
fussball99 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-2020 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]