Longest path / max flow for single node algorithm

J

jmc

0
Guten Abend,

Ich stehe momentan vor dem Problem, dass ich einen Graph-Algorithmus benötige um den längsten Pfad von einem bestimmten Knoten aus zu bestimmen ohne bestimmtes Ziel. Weiss vieleicht jemand ob es bereits etwas in der Art gibt?

Also z.B
(PS 1 und 3 sind auch verbunden. wird im Forum nicht angezeigt.
PHP: 
1 ---------- 4 ------------ 6
| \\         /|              |
|  \\       / |              |
|   \\     /  |              |
|    \\   /   |              |
|     --/\\   |              |
|      /  \\  |              |
|     /    \\ |              |
|------------3              5
2
Beim Start bei 3 z.B. 3-1-2-4-6-5
Beim Start bei 2 z.B. 2-1-3-4-6-5
Beim Start bei 4 z.B. 4-1-2-3

Ich brauche jeweils nur einen Weg.
Herzlichen Dank im Voraus.
 
ein einfaches verfahen wäre mittels tiefensuche alle pfade vom gewählten knoten zu bestimmen, und den pfad zu speichern, falls im speicher kein längerer pfad steht ... die laufzeit komplexität ist entsprechend blöd ...


sei _P ein Pfad

suche(Graph G, Knoten K, Pfad P)
{
sei G2 eine Kopie von G ohne (K und alle Kanten von K)
wenn(Länge von P+K > Länge von _P) ==> _P=P+K
für jeden Nachbarn N von K in G ==> suche(G2,N,P+K)
}

diese rekursions vorschrift sollte in _P einen entsprechenden Pfad hinterlassen ... aber angesichts der uhrzeit kann sie auch irgendwas anderes tun ...:rolleyes:
 
Vielen Dank erstmals für die Antwort.
Danke erstmals für die Antwort!
Falls ich deine Version richtig verstanden habe ist das leider sogar noch schlimmer als meine aktuelle Version, eine Principal Variation Search.
Damit kann man durch Abschätzung (restliche Knoten) sogar noch einen grossen Teil überspringen.
Die Laufzeit ist allerdings auch da nicht sehr gut :p
Es geht jeweils um etwa 10'000+ Knoten.
Ich dachte nur es gäbe evl bereits etwas in der Art, mir ist jedoch leider nichts dergleichen bekannt unter all den vielen Graphenalgorithmen.
 
Ich habe die Erfahrung gemacht, dass "komplexe" Algorithmen samt Abschätzungen sich erst ab x Knoten lohnen und man bei geschickt gewählten Datenstrukturen mit simplen Algorithmen erstmal schneller sein kann.


Edit: ich sollte mal genauer lesen - Du brauchst ja noch den Pfad und nicht bloß die Entfernung :wall:
d.h der nachfolgende Text ist nur sehr bedingt hilfreich :(
Bsp:
Ich benutze sowas, um den durchschnittlichen kürzesten Pfad in einem ungerichteten Graphen zu bestimmen (Graph hat ~5000 Knoten, es werden 100-200 "herausgepickt", was imho eine akzeptable Annäherung darstellt):

Sprache: Python (auch "lauffähiger" Pseudocode genannt ;) )
der Graph wird als eine Adjazenzliste repräsentiert,
also eine Liste mit Nachbarknoten
wobei der Index der Liste die ID des Knoten ist und man über diesen Index aus der Liste direkt ein Set mit Nachbarknoten bekommt:
Code: 
    def min_path(graph, start, end):       
        queue = set(graph.nodes[start])
        visited = set([start])
        next = set()
        count = 0

        while end not in visited:
            if len(queue) == 0:
                raise(ValueError("(%s, %s) not connected!" % (start, end)))

            for node in queue:
                next.update(graph.nodes[node])

            count += 1    
            visited.update(queue)
            queue = next.difference(visited)
            next.clear()            

        return count
Und das ist schneller, als "Standarddijkstra" (100 Aufrufe unter 1 Sekunde auf meinem betagten Laptop bei 5000 Knoten und bei Knotengrad 2-4)

Auf Dein Problem reduziert sollte es so aussehen:
Graph = [set(node1, node2, usw), set(node1, node5) ...]

Code: 
   def max_path(graph, start):       
        queue = set(graph.nodes[start])
        visited = set([start])
        next = set()

        while len(queue)>0:
            for node in queue:
                next.update(graph.nodes[node])

            count += 1    
            visited.update(queue)
            queue = next.difference(visited)
            next.clear()            

        return count
wobei die "update/difference" die Operationen auf dem Set sind und mit Mengenoperationen übereinstimmen (update fügt dem Set neue Knoten hinzu, difference bildet die Differenz aus 2 Mengen(Sets)).

In Pseudocode heißt das:
Code: 
Queue = {Nachbarn_des_starknotens}
Visited = {startknoten}
Next = {}

while Queue not leere_menge:
  for knoten in Queue:
    fuege Nachbarn_des_knotens in next ein

  entfernung + 1
  Visited = Visited U Queue  # schon besuchte Knoten + die in der Queue waren
  Queue = Next \ Visited     # also Menge Next ohne Elemente von Visited
  Next = {}

return entfernung
Wichtig ist hier die genutze Datenstruktur Set, die solche Operationen sehr gut unterstützt.

PS: sollte auf jedenfall schneller sein, als Tiefensuche, da die Knoten nicht mehrfach betrachtet werden ;)

Edit: mir fällt gerade auf, dass das nur für Graphen mit ungewichteten Kanten bzw. Kantenlängen = 1 gilt
und zudem nur die Entfernung zurückliefern :|
 
wirklich gutes laufzeitverhalten wirst du vermutlich nicht realisieren können:

die allgemeine suche nach dem längsten pfad ist ein np vollständiges problem

single source longest path is ein teilproblem davon, aber ich sehe nicht wo dir die einschränkung des ausgangspunktes wirklich helfen kann die komplexität zu reduzieren
 
Nochmals vielen Dank für die Antworten!
Leider hilft das noch icht wirklich weiter.

Falls trotzdem noch jemand eine Idee hat noch ein paar Dinge, die ich evtl nicht klar oder gar nicht erwähnt habe (Ich bitte um Entschuldigung):
- Was ich suche ist einem Hamilton-Pfad sehr ähnlich jedoch muss es nicht sein, dass alle Knoten erreicht werden können.
- Jeder Knoten hat insgesamt max. 4 Nachbarn (aneinandergereihte Quadrate, 100x100 bis 1000+x1000+, die insgesamt wieder ein quadrat bilden)
- Jeder Pfad zwischen zwei Knoten ist gleich gewichtet.
- Die Pfade sind ungerichtet.
- Jeder Knoten darf nur genau einmal besucht werden.
- Die Quelle ("Startpunkt") ist gegeben.

Momentan benutze ich eine PVSuche. Zwischendurch berechne ich immer wieder einmal die Artikulationspunkte (zähle dabei gleich noch die Kinder auf ungeraden und geraden Diagonalen).
Meine Abschätzung lautet danach 2 * min{ungerade Felder bis zum 1. artikulationspunkt - Felder mit nur einer Kante, gerade Felder bis zum 1. Artikulationspunkt - Felder mit nur einer Kante} + grösster Artikulationspunkt (auch dort mit 2* das Minimum der Felder - Felder mit nur einer Kante wenn es unter den Kindern weitere Artikulationspunkte gibt werden die auch bereits mit Ausnahme des grössten abgezählt).
Danach richte ich die PVSuche nach dieser Richtung aus und erhalte dadurch ein einigermassen gutes Resultat in einigermassen guter Laufzeit ;)
 
mit PVS hab ich mich nie wirklich beschäftigt, und ich hab jetzt auch nicht wirklich die motivation mich da einzulesen, aber evtl hilft dir diese idee ein bischen weiter:

wenn ich dich zudem richtig verstehe, muss es nicht DER längste pfad sein, nur ein "angemessen" langer

wenn man sich die laufzeit komplexität ansieht, möchte man möglichst wenig knoten und kanten haben ...

wenn man den graphen in einen anderen graphen mit geringerer komplexität überführen kann, auf diesem rechnet, und das ergebnis auf den ursprungsgraphen übertragen kann (teile und hersche), wäre das von vorteil

ich denke da z.b. an das aufteilen in teilgraphen (eine art zusammenhangskomponenten) die über eine gewisse anzahl an berührungspunkten verbunden sind ... sieht man die teilgraphen nun als knoten, und jeden berührungspunkt als kante, hat man einen graphen geringerer komplexität, der immernoch zu einem großen teil die topologie wiederspiegelt...

findet man nun eine lösung für diesen graphen, kann diese lösung als wegweiser für die gesammtlösung dienen. man kann nun den wegweiser pfad als ansammlung von problemen der art single-source-single-target-longest-path auf den jeweiligen teilgraphen sehen, die sich zudem unabhänig voneinander lösen lassen... jedes der teilprobleme hat eine geringere komplexität als das gesammtproblem, und sie lassen sich alle paralell angehen, was mit hinsicht auf die laufzeit ggf relevant ist


wie gesagt ... nur eine idee ...
 
Eigentlich sollte es schon DER längste Pfad sein, aber bei 10k, 100k und mehr Knoten scheint das wie gesagt mehr oder weniger unmöglich zu sein mit dieser Variante ;)
Und die Näherung ist tatsächlich dadurch sogar sehr gut (durchschnittlich >98% bei 10k Durchgängen). Das kann z.B. übberprüft werden indem man in jeder getrennten kammer durch das erweitern erweitern von einer 2x1 Fläche mit einer 2x2 Fläche wobei immer 2 der 4 Flächen die bereits bestehende Fläche überlappen müssen.
Dadurch erhält man zusammen mit den längsten Pfaden auch die maximale Zahl, aber nicht den Weg. Dies ist auch relativ aufwendig, muss aber nur 1x berechnet werden zur Überprüfung.
Das mt einer Einteilung in Kammern habe ich auch bereits einmal versucht, aber es scheint extrem schwierig zu sein die Kammern gut zu wählen bzw. deren Übergänge. Ein einfaches Problembeispiel wäre:
- oberer und unterer Übergang einer Kammer
# Wand
S aktuelle Position
PHP: 
-


C#
1#
 #######################
 #S
-
 #
C#######################
2#



-
Um einen guten Pfad zu erhalten müsste man hierbei bei jedem 2. Schritt die Kammer wechseln.
Eine weiteres Problem wäre z.B. eine Kammer B mit einer Unterkammer C die nur von einer anderen Kammer A aus erreichbar ist. Wobei man dann aus C (innerhalb von B) wieder in die Kammer A zurückkehren müsste.
Ich habe deswegen keine gute Mgölichkeit gefunden das zu vereinfachen.
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben