# Algorithmus (Routenberechnung)



## zUkUu (9. Okt 2007)

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 (9. Okt 2007)

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 (9. Okt 2007)

Kim Stebel hat gesagt.:
			
		

> 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 (9. Okt 2007)

zUkUu hat gesagt.:
			
		

> finde aber nirgends Beispielcode dazu, welche meinen Anfordungen entspricht.


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



			
				Kim Stebel hat gesagt.:
			
		

> 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 (9. Okt 2007)

Marco13 hat gesagt.:
			
		

> zUkUu hat gesagt.:
> 
> 
> 
> ...



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 (9. Okt 2007)

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 (9. Okt 2007)

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 (9. Okt 2007)

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 (9. Okt 2007)

Du noob!


----------



## Gast (9. Okt 2007)

@zukuu du bist mit noob gemeint


----------



## Paddy (9. Okt 2007)

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 (9. Okt 2007)

Gast hat gesagt.:
			
		

> Du noob!



Selber n00b!


----------



## Marco13 (9. Okt 2007)

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


			
				Kim Stebel hat gesagt.:
			
		

> und dass das problem NP-vollständig ist?


...stimmt auch nicht :wink:


----------



## Marco 13 1/2 (9. Okt 2007)

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


----------



## Harry85 (9. Okt 2007)

zUkUu hat gesagt.:
			
		

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



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. (10. Okt 2007)

schwör mal?


----------



## Michi89 (10. Okt 2007)

ThomasD. hat gesagt.:
			
		

> 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 (10. Okt 2007)

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


----------



## wuuuzaa (10. Okt 2007)

mh...frag ich mich auch!?!


----------

