• Hey,
    hier wurde ja gefragt, wie man Wege finden kann, wenn man bestimmte Maps und ihre Verbindungen zu anderen Maps kennt.
    http://autoit.de/index.php?page=Thread&threadID=20124


    Ich habe das mal umgesetzt:


    [Blockierte Grafik: http://img163.imageshack.us/img163/483/unbenannt1yu.png]
    #include <Array.au3>


    Global $arr[1]
    Global $maps[9][6] = [["a", "b", "c"], _
    ["b", "a", "t"], _
    ["c", "a", "f"], _
    ["h", "t", "k", "l"], _
    ["l", "h"], _
    ["f", "t", "c"], _
    ["k", "h", "t"], _
    ["t", "f", "h", "k", "z", "b"], _
    ["z", "t"]]


    _ArrayDisplay($maps)
    _rekursivewegsuche("a", "k")
    $arr[0] = UBound($arr)
    _ArrayDisplay($arr, "Alle Wege von A nach K")


    Func _rekursivewegsuche($start, $ende, $bufferstr = '')
    Local $string = ''


    If StringInStr($bufferstr, $start) Then
    Return
    Else
    $string = $bufferstr & $start & ';'
    EndIf


    Local $index = ''
    $index = _getindex($start)
    For $i = 1 To UBound($maps, 2) - 1
    If $maps[$index][$i] = $ende Then
    _ArrayAdd($arr, $string & $ende)
    Else
    If $maps[$index][$i] = '' Then
    ExitLoop
    Else
    _rekursivewegsuche($maps[$index][$i], $ende, $string)
    EndIf
    EndIf
    Next
    EndFunc ;==>_rekursivewegsuche


    Func _getindex($map)
    Local $index = ''
    For $i = 0 To UBound($maps) - 1
    If $maps[$i][0] = $map Then
    Return $i
    EndIf
    Next
    EndFunc ;==>_getindex


    Die Umsetzung ist bestimmt nicht sehr Effizient...
    Kann wahrscheinlich auch keiner mehr brauchen, war aber ne coole Übung :).

  • Ist das nicht das berühmte Problem des Handelsreisenden?
    Sobald es mehr als nur ein paar Wegpunkte und Verbindungen sind, wird es praktisch unmöglich zu berechnen...

  • Soweit ich weiß wird das im Navi so berechnet:
    Du bist am Punkt T in deiner Skizze und willst zu A.
    Als erstes berechnest du alle Strecken von T zu anliegenden Punkten...
    Dann guckst du welcher Weg am kürzesten ist und berechnest dort auch alle anliegenden Strecken...
    Diesen Schritt machst du solange, bis einer der gefundenen anliegenden Punkten A ist... so hast du dann deinen kürzesten Weg...
    Bsp.:
    Bild 1: Wir wollen also von T zu A und im ersten Bild berechnen wir zuersteinmal alle möglichen Wege von T aus:
    T-Z, T-K, T-H, T-B (rot makiert)
    dann gucken wir welches der Kürzeste ist, in unserem Fall T-K (grün makiert)
    Bild 2: Nun überprüfen wir von K alle ausgehenden Wege also K-H (denn T-K haben wir bereits einmal gehabt, der ist deshalb auch blau makiert). Da T-K-H nun größer ist als T-Z, ist das unsernächster zu überprüfende Weg
    Bild 3: Von Z gehen keine Wege aus, also wird dieser Weg als abgeharkt angesehene und Blau makiert und wir überprüfen den nächst-kürzesten Weg, der ist T-H von dort aus geht einmal T-H-K, der allerdings bereits makier ist, weshalb wir ihn nicht nocheinmal makieren müssen. Nun ist also der Weg T-H-L der einzige den es hier noch gibt und der wird somit rot makiert...
    Bild 4: Ist unser letztes Bild, da nun T-B der kürzeste Weg ist, gucken wir welche Wege es von hier gibt: Es gibt nur T-A-B aber auch wenn es mehr geben würde, würde man diesen nehmen, da es der zuerst gefundene Weg ist und somit der kürzeste ist...
    autoit.de/wcf/attachment/10120/


    Hoffe mal ist klar wie ich das meine :)

  • Algorithmen zur Lösung des Problem des "travelling Salesman" wurden mitte der 80er von IBM in Verbindung mit einem öffentlichen Wettbewerb gesucht. Aus Spass hatte ich auch mitgemacht und war fasziniert von den Optimierungsmöglichkeiten. Auf einem 4,77Mhz-PC war ohne weiteres der kürzeste Weg zwischen 100-200 "Städten" zu berechnen.
    Logischerweise findet man den kürzesten Weg einfachst über Brute-Force, aber das interessante ist, daß man einen "nicht perfekten" Weg (der nur minimalst vom perfekten abweicht), in einem Bruchteil der Zeit berechnen kann.


    Dabei ist zu beachten, daß der Algorithmus auch vermeintlich "schlechtere" Wege einschlagen muß, um im Nachhinein doch ein Optimum zu erzielen.
    Grafisch war das immer eine Show (auf Monochrom Herculesgrafik^^), wenn der Computer kurz vor der vermeintlichen Lösung den Graphen nochmal "verkneuelt" hat, um danach noch um ein Millionstel Längeneinheit besseres Ergebnis zu liefern.
    Die 5 1/4´´-Diskette mit den Programmen hab ich leider nicht mehr gefunden....bestimmt zusammen mit den anderen "Computerantiquitäten" weggeschmissen....macht doch einen µIt draus^^


    A-Propos, "meinen" Algorithmus hatte ich später in einen HIRATA-Lötroboter integriert, der glücklicherweise auch in Basic programmiert werden konnte. So musste man nur die Position der Lötstellen "teachen", und der Controller hat im nachhinein die kürzeste Strecke zwischen den ca. 20-30 Lötstellen berechnet. Durch diese "Optimierung" konnten dann ein oder zwei Fernseher mehr pro Tag produziert werden (statt 400 dann 402).

  • Hi, das Travelling-Salesman-Problem ist auch sehr gut mit Genetischen Algorithmen Lösbar. Ich habe vor kurzem erst einen Genetischen Algorithmus für das Rundreiseproblem in C++ implementiert, die Ergebnisse sind erstaunlich, innerhalb von Sekunden kann man die Route durch hunderte Städte berechnen. Vielleiche möchte ja jemand einen auf Autoit Basis Programmieren? ;-)


    MfG Night

  • Hey,
    wäre ne coole µit-Idee.
    Aber dann müssen wir auch ne Gute Grundlage schaffen. Vielleicht wirklich ein kleines Navi...
    Vielleicht auch mit Kosten, auf der Strecke darf man nur 50 fahren, auf der anderen 100 oder so und dann das ganze grafisch noch umsetzen.


    Bei der Lösung die Freaky wollte würde sich ein besonders guter Algorithmus wohl kaum lohnen. Mir ging es auch nicht drum das ganze sehr effizient zu lösen. Freaky wollte halt eine Lösung zu dem Problem und Brute force ist hier wohl das einfachste.

  • *Leiche ausgrab*


    Hi, hab mal gewühlt und eins meiner Chaos-Scripte gefunden, Jauitois fragte gerade in der SB danach....
    Nur, um das Lösungs-Prinzip zu verdeutlichen!
    Die Messageboxen innerhalb der Funktionen sind auskommentiert, schaltet die jeweils 2-3 Zeilen ein, um zu sehen, wie der Algorithmus funktioniert.


    Habe noch einige mehr Optimierungsfunktionen (die letzte Version hat >50kB) , aber ggf gibts ja doch noch nen µ-It^^


    Übrigens habe ich mit diesem Script einige der Karten von HIER durchlaufen lassen....
    Wer übrigens etwas seltsam guckt, weil er nicht versteht, was das mit "Ameisen" zu tun hat....GidF.de :rofl: