Pscore - Mi 11.01.06 15:14
Titel: Wegoptimirungsalgorithmus

---

Hallo,
ich suche verschiedene Arten von Wegoptimirungsalgorithmen.
Können auch in Wortform sein, muss kein Quellcode sein.
Wäre ganz cool wenn mir einer Namen nennen könnte oder sogar beschreiben wie das funktioniert.
Danke!
Jens


Moderiert von raziel: Topic aus Delphi Language (Object-Pascal) / CLX verschoben am Mi 11.01.2006 um 14:32

Horst_H - Mi 11.01.06 16:04

---

Hallo,

das Problem des Handlungsreisende TSP {travelling salesman}
oder hier was total unbrauchbares:
http://nero.informatik.uni-wuerzburg.de/~tutschku/pub/abstr/tr146.html
was zum lesen und weiterfuehrend:
http://de.wikipedia.org/wiki/Algorithmus_von_Dijkstra

Gruss Horst

k-weddige - Mi 11.01.06 16:49

---

Irgendwann hab ich mal was von einer Methode gelesen, die sich an der Wegfindung von Ameisen orientiert.
Such mal nach "Ameisen", "Algoithmus", "Ant*", usw.

Konstantin

delfiphan - Mi 11.01.06 19:25

---

Es gibt nicht einfach *den* Algorithmus für jeden Fall. Könntest du also deine Problemstellung etwas genauer erkläutern?

digi_c - Do 12.01.06 09:27

---

Der mit den Ameisen wurde mal in der c't vorgestellt und funktioniert so wie Ameisen auch den Optimalen Weg finden. Der Pfad der am meisten passiert wird(da ja der kürzeste und somit können in einem Zeitabschnitt mehr Ameisen langgehen) hat die höheste Geruchskonzentration durch Ameisen.

http://www.educeth.ch/informatik/puzzles/routing/index.html Die Seite ist wirklich Top muss ich sagen in jedem belang zu Algorithmen!

Pscore - Do 12.01.06 15:59

---

Also der Algorithmus soll hinterher so die funktion haben wie z.b map24.de den kürzesten weg in einem netz von verbindungen zu finden.

Ich habe schon überlegt die mit backtracking zu lösen, aber die ist sehr sehr rechenaufwendig, wenn es viele verbindungspunkte gibt, also schnell sollte der algorithmus auch sein, ich hätte so an einen näherungsalgorithmus gedacht.

Horst_H - Do 12.01.06 16:34

---

Hallo,

wie oben angegeben
http://de.wikipedia.org/wiki/A*-Algorithmus

Gruss Horst

digi_c - Fr 13.01.06 09:28

---

Schau mal meinen Link oben an da gibt es alles was du brauchst...

delfiphan - Mi 18.01.06 21:59

---

Shortest Path: Siehe Dijkstras Algorithmus wenn du feste Knotenpunkte und Routen hast.
A* ist iirc eher für spezielle Anwendungen wie wenn du z.B. eine ganze Landkarte (Bitmap) hast und einen Pfad verfolgen musst und dabei eine Kostfunktion global minimieren möchtest.

Edit: Wie ich auf Wikipedia grad lese ist A* offenbar auch für Graphen geeignet. Am besten liest du mal selbst nach ;)

ademus - Mi 15.03.06 10:35

---

Ist zwar schon etwas spät für eine Antwort, aber vielleicht nützt es trotzdem noch jemandem.
Ich habe vor einiger Zeil mit einem A* Algorithmus experimentiert. Die Ergebnisse stehen hier zur Verfügung:
http://www.entwurfsforschung.de/Strukturfor/delphi/delphiF.htm#Pathfind

Beste Grüße ademus

Delete - Mi 15.03.06 11:19

---

A* habe ich auch noch im Angebot: http://www.michael-puff.de/Developer/Delphi/Sonstiges/AStar.zip ;)