Algorithmus (Routenberechnung)

[zUkUu]

Hi!

Ich versuche einen einfachen Routenplaner zu erstellen. Es gibt nur 11 Städte (A-K).
Nun brauche ich einen Algorythmus der möglichst SCHNELL ist und Perfomant ist, der den KÜRZESTEN und den SCHNELLSTEN weg berechnet.

Ich habe an den A*Algorithmus gedacht - finde aber nirgends Beispielcode dazu, welche meinen Anfordungen entspricht.

Vll habt ihr ja ein paar Tipps oder Besipiel Code.

so far

zUkUu

PS: Danke schonmal =)

 

[Kim Stebel]

dir ist schon klar, dass A* nicht den optimalen weg berechnet und auch üblicherweise nicht mit graphen als datenstruktur arbeitet?
und dass das problem NP-vollständig ist?

 

[zUkUu]

dir ist schon klar, dass A* nicht den optimalen weg berechnet und auch üblicherweise nicht mit graphen als datenstruktur arbeitet?
und dass das problem NP-vollständig ist?

Deswegen wende ich mich ja an euch

Würd halt gerne wissen welchen Algoithmus ihr nehmen würdet - und welcher der schnellste ist.

Wenns hilft hier meine Aufgabenstellung:

Es gibt 11 Dörfer mit Namen A-J. Jedes Dorf ist mit anderen Dörfern verbunden. Um be-stimmte Dörfer zu erreichen, gibt es meistens mehr als eine Verbindung. Die Verbindungsda-ten differieren, d.h. die maximale Geschwindigkeit mit der man eine Strecke befahren kann sowie die Länge einer Strecke.

Dazu soll ich noch das ganze als Grafik erstellen. Hat aber nix mit meinem Problem zu tun.

Wichtig ist erstmal die wahl des Algorithmus sowie die implimentiereung =)

so far

zUkUu

 

[Marco13]

finde aber nirgends Beispielcode dazu, welche meinen Anfordungen entspricht.

Das heißt wohl: "Compilierbar, so, dass du selbst nichts mehr machen mußt" ?! :wink:

dir ist schon klar, dass A* nicht den optimalen weg berechnet und auch üblicherweise nicht mit graphen als datenstruktur arbeitet?

:shock: Das stimmt beides nicht. Er arbeitet "üblicherweise" auf graphen, und findet den optimalen Weg, wenn man eine "pessimistische" Abschätzungsfunktion verwendet. Verwechselst du den vielleicht mit einem anderen?


EDIT: Mit "pessimistische" Abschätzungsfunktion meinte ich das, was hier
http://de.wikipedia.org/wiki/A*-Algorithmus
als "monotone Heuristik" bezeichnet wird.

 

[zUkUu]

finde aber nirgends Beispielcode dazu, welche meinen Anfordungen entspricht.

Das heißt wohl: "Compilierbar, so, dass du selbst nichts mehr machen mußt" ?! :wink:

Nicht direkt - wär natürlich nice xD aber erwartet doch keiner =)

Eher zum Algorithmus spezifisch was. Muss net alles sein, aber was worauf man aufbaun kann ^^

 

[Marco13]

Naja - der Algorithmus an sich arbeitet ja (falls da jetzt nicht noch Widerspruch von Kim Stebel kommt :wink: ) auf Graphen - hast du schon eine Graphen-Klasse? (Oder irgendwas sonst, worauf der Algorithmus arbeiten könnte?) Dann ist der Algorithmus selbst (mit der Hilfe von Wikipedia) ja nicht mehr sooo aufwändig. Aber vielleicht hast du ja noch konkretere Fragen.......

 

[zUkUu]

Hab mal Pseudo Code des Dijkstra-Algorithmus gefunden:
Werd mal versuchen den nachuzubaun. Hoffe wird ncith zu schwer

# N - number of nodes
# weight(i,j) - weight of the edge from node i to j ; equal to infinity if such an edge doesn't exist
# dist(i) - the shortest path from source node to i
# parent(i) - node that precedes i in a shortest path, used to reconstruct the shortest path

# initialize all values
For i = 1 to N
    dist(i) = infinity
    processed(i) = false
    parent(i) = null
End For
dist(source) = 0

While (not all nodes have been processed)
    If (distances to all unprocessed nodes are equal to infinity) Then
        no path from source to destination node exists
        Exit
    End If

    Let i be an unprocessed node for which dist(i) is the smallest among all unprocessed nodes.
    If i = destination Then Exit While    # shortest path from source to destination has been found
    Set processed(i) = true
    
    For Each unprocessed node j    # i.e. for which processed(j) = false
        If dist(i) + weight(i,j) < dist(j) Then
            # a shorter path from source node to j has been found ; update it
            dist(j) = dist(i) + weight(i,j)
            parent(j) = i
        End If
    End For
End While

# the length of the shortest path is thus dist(destination)

# path reconstruction is given below
Set i = destination
While i != source
    Append i to the beginning of the currently constructed path
    i = parent(i)
End While
Append source to the beginning of the path

Der sollte doch für mein Problem genau passend sein
Oder stoß ich da auf schwerigkeiten?

so long

 

[Marco13]

Nö, der ist auch OK.

BTW: Auf einer "echten" Landkarte kann man eine ziemlich triviale Heuristik für den A* angeben: Die Luftlinien-Entfernung. Damit könnte (vor allem bei GROSSEN Karten) der A* schneller sein, aber bei weniger als 10000 Knoten dürfte das noch egal sein...

 

[Gast]

Du noob!

 

[Gast]

@zukuu du bist mit noob gemeint

 

[Paddy]

Sehr kompliziertes Thema. Es ist jedoch möglich durch Graphen-Klassen den Algorithmus zu vereinfachen. Durch Wikipedia wirst du beim Algorithmus einige Hilfestellungen bekommen.

 

[Marco14]

Du noob!

Selber n00b!

 

[Marco13]

Wo wir's gerade von Noobs und nicht-noobs haben: :roll:

und dass das problem NP-vollständig ist?

...stimmt auch nicht :wink:

 

[Marco 13 1/2]

Hast Recht. Ist mir noch gar nicht aufgefallen...

 

[Harry85]

Hab mal Pseudo Code des Dijkstra-Algorithmus gefunden:
Werd mal versuchen den nachuzubaun. Hoffe wird ncith zu schwer

# N - number of nodes
# weight(i,j) - weight of the edge from node i to j ; equal to infinity if such an edge doesn't exist
# dist(i) - the shortest path from source node to i
# parent(i) - node that precedes i in a shortest path, used to reconstruct the shortest path

# initialize all values
For i = 1 to N
    dist(i) = infinity
    processed(i) = false
    parent(i) = null
End For
dist(source) = 0

While (not all nodes have been processed)
    If (distances to all unprocessed nodes are equal to infinity) Then
        no path from source to destination node exists
        Exit
    End If

    Let i be an unprocessed node for which dist(i) is the smallest among all unprocessed nodes.
    If i = destination Then Exit While    # shortest path from source to destination has been found
    Set processed(i) = true
    
    For Each unprocessed node j    # i.e. for which processed(j) = false
        If dist(i) + weight(i,j) < dist(j) Then
            # a shorter path from source node to j has been found ; update it
            dist(j) = dist(i) + weight(i,j)
            parent(j) = i
        End If
    End For
End While

# the length of the shortest path is thus dist(destination)

# path reconstruction is given below
Set i = destination
While i != source
    Append i to the beginning of the currently constructed path
    i = parent(i)
End While
Append source to the beginning of the path

Der sollte doch für mein Problem genau passend sein
Oder stoß ich da auf schwerigkeiten?

so long

ich hab den text gerade ausprobiert. kannste dir zwischen die balken nageln. ich hab zwar auch keine idee, aber ohne Graphen - Klasse wird das kompliziert.

 

[ThomasD.]

schwör mal?

 

[Michi89]

schwör mal?

Bist du dumm? Gelaubst du wirklich das trägt zum Thema bei. Ich denke eher, dass "zukuu" auf VERNÜNFTIGE antworten wartet!

 

[Marco13]

Was geht hier denn eigentlich ab? ???:L

 

[wuuuzaa]

mh...frag ich mich auch!?!