Wegfindung im Graphen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 22:28 So 01.12.2013 | | Autor: | Parano.Oya |
| Aufgabe | Gegeben ist ein beliebiger schlichter, ungerichteter, gewichteter Graph G.
Dabei ist G zusammenhängend und weder ein Baum noch ein Kreis.
Mit dem Algorithmus von Dijkstra kann der kürzeste Weg vom Startpunkt zum Zielpunkt errechnet werden. Zu finden sind nun, falls existent, alle Alternativwege des Graphen G. |
Guten Abend an die Community,
um es kurz zu fassen: Die Aufgabenstellung bezieht sich auf eine spätere Implementierung in einem Programm unter C++. Die Implementierung ist für mich nun keine großartige Hürde. Die Aufgabe selbst ist schon zum größten Teil erfüllt. Dies ist im Übrigen keine Hausaufgabe oder so ein Spaß.
Das wohl wichtigste Problem ist wohl die Überlegung des Ganzen...
Aber eins nach dem anderen. Wir haben einen beliebigen Graphen G mit den obigen Eigenschaften. Ich arbeite als angehender Informatiker nun, was die Darstellung der Graphen betrifft, mit einer Adjazenz-Matrix. Aus der Adjazenz-Matrix erstelle ich eine Binärmatrix. Anhand der Binärmatrix ist eindeutig zu erkennen, wie hoch der Grad des Startpunktes und des Zielpunktes ist.
Mein Ziel ist es nun alle Alternativwege, falls existent, im Graphen G zu finden. Ich bin daher wie folgt vorgegangen: In jedem Schritt entferne ich eine Kante vom Startpunkt, sofern der Grad vom SP > 1 ist, errechne mittels dem Algorithmus von Dijkstra den kürzesten Pfad und im Folgeschritt entferne ich die nächste Kante, wobei die vorherige entfernte Kante wieder hinzugefügt wird. Der ganze Spaß geht so lange, bis ich am Ende der Matrix angekommen bin.
Ich habe hier mal einen Pseudocode:
#Zeige mir alle Wege an
if degSP > 1 then # Grad vom Startpunkt ist größer als 1
tmp = 0 # tmp-Wert für Graph(i,j)
used = false # Vermerk, ob Kante entfernt wurde
diagonal = 0 # Vermerk, ob aktuelle Position in Diagonale liegt
for i = 0 to n-1 do:
if i != sp then # Nicht in richtiger Zeile?
i = i+1 # ab in die nächste Zeile
end
for j = 0 to n-1 do:
if j == diagonal then # Falls Spalte j in der Diagnale liegt
diagonal = "INFINITY - 1" # Diagonalvermerk aktivieren
else # Ansonsten nicht...
# Verhinderung einer Schleife bzw. Schlinge
Ausgabe Matrix(/*graph*/bin) # zur Kontrolle
/* Wiederherstellung vorheriger entfernter Kante;
* Nur möglich, wenn vorherige entfernte Kante
* wirklich existierte!
*
* Erweiterung: Wenn vorherige Spalte die
* Diagonale ist, muss überprüft
* werden, ob Spalte vor Diagonale
* 0 ist und diese eine Kante hatte
*
* bin(i,j-1) == 0: vorherige Spalte der Binärmatrix
* muss 0 sein
*
* bin(i,j-1) != diagonal: vorherige Spalte darf nicht
* in der Diagonale liegen
*
* used == true: Vermerk, dass eine Kante
* entfernt wurde
*
*/
/* Wenn Spalte j-1, falls existent, 0 ist, überprüfe,
* ob diese in der Diagonale liegt und diese den
* Vermerk gesetzt bekam. Dann ist in dieser Spalte eine
* Kante entfernt worden. Diese wird wieder hinzugefügt
* und der Vermerk zurückgesetzt.
*
* Sonst muss die Spalte j-1 in der Diagonale liegen.
* In diesem Fall muss geprüft werden, ob in der
* Spalte j-2, falls existent, eine 0 steht und dort
* ein Vermerk gesetzt wurde. Dann ist hier eine entfernte
* Kante wieder hinzuzufügen und der Vermerk zurückzusetzen.
*
* Ansonsten ist die Spalte j-1 schon immer 0 gewesen.
* In dem Fall ist j-1 in der Diagonale bzw. wurde
* keine Kante entfernt und Vermerk wurde nie gesetzt.
* Demnach darf keine Kante hinzugefügt werden.
*/
if (bin(i,j-1) == 0) then # Vorherige Spalte 0?
if (bin(i,j-1) != diagonal) and (used == true) then # Vorgerige Spalte keine Diagonale und Vermerk gesetzt?
bin(i,j-1) = 1 # Kante wieder herstellen
graph(i,j-1) = tmp # Wert aus tmp wieder in Matrix speichern
used = false # Vermerk zurücksetzen
else if (bin(i,j-2) == 0) and (used == true) then # Spalte vor Diagonale 0 und Vermerk gesetzt?
bin(i,j-2) = 1 # diese Kante nun wieder herstellen
graph(i,j-2) = tmp # Wert wieder herstellen
used = false # Vermerk zurücksetzen
end
end
/* Entfernen der aktuellen Kante */
if (bin(i,j) == 1) then # Kante vorhanden?
bin(i,j) = 0 # Kante entfernen
tmp = graph(i,j) # Wert sichern
graph(i,j) = INFINITY # "unendlich"
used = true # Vermerk aktivieren
end
/* Es wurde nun in der Theorie eine Kante in der
* Spalte j entfernt und in der vorherigen Spalte
* j-1 eine Kante wieder hinzugefügt, sofern in der
* vorherigen Spalte j-1 der Wert 0 vorhanden war
*/
Berechnung Pfad mit Dijkstra(graph) # Wegfindung des aktuellen Graphen
Ausgabe Pfad(graph) # Ausgabe des Pfades
end
end
end
end
#Ende der Funktion
Nun zu meiner Frage: Da ich schon seit einigen Wochen mich mit dieser Problematik auseinandersetze, aber immer noch nicht den richtigen Zündfunken habe, frage ich nun die Community. Entweder ist etwas oder einiges an meiner Überlegung falsch oder ich habe es noch nicht richtig implementiert.
Könnt ihr dies nachvollziehen, worum es bei der Überlegung und des Pseudocodes, auch wenn das hier bedauerlicherweise nicht besonders schön dargestellt wird, geht oder hat einer von euch da draußen eine oder mehrere Lösung(en) parat?
Also am besten den Pseudocode mal kopieren und in einem beliebigen Editor mittels Tab-Einrückungen näher begutachten 
Ach, bevor ich es vergesse: Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt: ![[]](/images/popup.gif) hier.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:48 So 01.12.2013 | | Autor: | reverend |
Hallo Parano.Oya, ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
da hast Du im anderen Forum ja schon eine ziemlich umfangreiche Diskussion losgestoßen. Ich fürchte, dass wir Dir zum Ganzen auch nicht mehr helfen können als die Mitglieder dort. Mit Einzelfragen kannst Du aber natürlich gern zurückkommen.
Aufgrund dieser Einschätzung habe ich Deine Frage mal inaktiv gestellt. Ich hoffe, das ist ok.
Außerdem werde ich Deine Anfrage kurz editieren, da der Link nicht funktioniert.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 05:51 Mi 04.12.2013 | | Autor: | Parano.Oya |
Heureka! Ich glaub, ich habe die Lösung gefunden! Wenn man nicht daran denkt, dann kommt die Lösung :D
Meine Überlegung war schon richtig, nur gab es EINEN Faktor, den ich nicht richtig begutachtet hatte. Für diejenigen, die (irgendwann) auf das ähnliche oder gleiche "Problem" stoßen sollten, habe ich hier den Tipp, dass der Wert 'diagonal' innerhalb der 2. for-Schleife nicht wirklich als Vergleich herangezogen werden sollte, sondern dass für die Dimension der Matrix eine gleichgroße Markierer-Matrix herangezogen werden sollte, sodass nur in der Koordinate[i][j] es eine Diagonale geben kann. In allen anderen Koordinaten der selben Zeile gibt es dann logischer Weise keine Diagonale.
|
|
|
|
