Zaubär - Sa 30.11.02 19:32
Titel: Auto-Route Algorithmus

---

Hi,

zuerst mal eine kleine Einleitung. Sicher kennt ihr Programme, die nach gewissen Kriterien selber die Lösung finden.
Ein erstes Beispiel sind die sogenannten Auto-Router ind der Printplatten-Herstellung, welche nebenbei bemerkt schweineteuer sind.
Ein zweites Beispiel wären die Auto-Navigations und ähnliche Softwareprogramme bzw. Internetseiten. Bei denen kann man ja bekanntlich den Start- und Endpunkt eingben und sie suchen sich auf einer Landeskarte selbst den richtigen Weg.

Weiss jemand von euch nach welchem Prinzip so ein Algorithmus arbeitet??
Mein Ziel wäre es eine Datenbank mit verschiedenen Werte zu füllen und dann einen Algorithmus dazu, welcher nach Eingabe von ein paar Kriterien eine Pfannenfertige Lösung ausspuckt.

Cashels - Sa 30.11.02 20:07

---

Hallo,

ein recht guter Algorythmus ist der A*-Algorythmus. (Wenn man das denn Algorythmus nennen darf, denn eine mathematische Formel gibts nicht für diese Art von Problemen nicht). Vor einigen Monaten war mal in "Der Entwickler" Zeitschrift dieser A*-Alg. beschrieben, auch mit einigen Beispielen. Die Sourcecodes gibts zum Download bei [url]http://www.derentwickler.de[/url]

Gruss,
Tom

CenBells - So 01.12.02 20:02

---

hallo.

Was du suchst, ist eine der eierlegenden Wollmilchsäue der Informatik.
Das Problem worauf du hinaus willst, nennt sich "Travelling Salesman" - Problem und ist, wie der Name schon sagt ein Problem, was noch nicht in endlicher Zeit lösbar ist. Folglich gibt es dafür noch keine Formel, die allgemeingültig ist.

Gruß
Ken

Indeterminatus - Do 05.12.02 17:26

---

Eine andere Möglichkeit wäre die Implementation eines sog. "Neural Networks", das aus einem Netzwerk von Punkten besteht. Genauere Informationen über pathfinding-"Algorithmen" kannst Du Dir besorgen unter http://www.gamedev.net/ entweder im forum oder bei Articles/Resources. Ist zwar alles in Englisch, dürfte aber nicht weiter stören...

Udontknow - Fr 06.12.02 10:55

---

Hi,

Nun, das Travelling-Salesman-Problem ist da doch etwas anderes. Dort geht es um die Problematik, n Orte abzuklappern und möglichst wenig Weg beziehungsweise Zeit zu benötigen, zur Zeit benötigen Rechner mit steigender Anzahl n zuviel Zeit zur Lösung.

Die günstigste Route zwischen zwei Punkten zu finden, lässt sich mit ein wenig Rekursion lösen. Das Stichwort heisst "Back-Tracking". Ich hatte mal ein Tut im alten Forum unter EDE, aber das ist ja leider verloren gegangen. Vielleicht kann ich es ja bald noch einmal aufsetzen.

Cu,
Udontknow

Cashels - Fr 06.12.02 11:09

---

Hi,

das Travelling Salesman Problem faellt aber unter die gleiche Kategorie von mathematischen Problemen (NP-Klasse). Einen effektive Algorythmus wirds nicht geben, und der Rechenaufwand waechst faktoriell mit der Anzahl der Knoten rsp. Verbindungen. Um dennoch bei großer Anzahl von Knoten, man denke sich nur eine Deutschlandkarte mit allen Städten, wird mit Näherungsverfahren gearbeitet. Meist wird erst mal eine Route geschätzt, und diese wird dann lediglich nur noch optimiert.

Auch noch unter diese Klasse von Problemen faellen zum Bsp. das Suchen eines Weges aus einem Labyrinth oder das Umgehen von Hindernissen. Wer kennt sie nicht die guten alten Strategiespiele, wo sich dann die Truppen total verirrt haben auf dem Spielplan und in irgendeiner Ecke standen und nicht mehr weiter kamen. Das zeugt auch von uneffektiver Programmierung, und legt eigentlich nur deutlich klar, wie aufwaendig das Suchen des optimalen Weges eigentlich ist.

Gruss,
Tom