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

    Ich habe das mal umgesetzt:

    [Blockierte Grafik: http://img163.imageshack.us/img163/483/unbenannt1yu.png]

    [autoit]

    #include <Array.au3>

    [/autoit][autoit][/autoit][autoit]

    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"]]

    [/autoit][autoit][/autoit][autoit]

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

    [/autoit][autoit][/autoit][autoit]

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

    [/autoit][autoit][/autoit][autoit]

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

    [/autoit][autoit][/autoit][autoit]

    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

    [/autoit][autoit][/autoit][autoit]

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

    [/autoit]

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

    2 Mal editiert, zuletzt von anno2008 (6. Juni 2010 um 23:15)

  • 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...

    Twitter: @L3viathan2142
    Benutze AutoIt persönlich nicht mehr, da ich keinen Windows-Rechner mehr besitze.

  • 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).

    ciao
    Andy


    "Schlechtes Benehmen halten die Leute doch nur deswegen für eine Art Vorrecht, weil keiner ihnen aufs Maul haut." Klaus Kinski
    "Hint: Write comments after each line. So you can (better) see what your program does and what it not does. And we can see what you're thinking what your program does and we can point to the missunderstandings." A-Jay

    Wie man Fragen richtig stellt... Tutorial: Wie man Script-Fehler findet und beseitigt...X-Y-Problem

    2 Mal editiert, zuletzt von Andy (7. Juni 2010 um 09:04)

  • 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.

    Spoiler anzeigen
    [autoit]

    #include <GDIPlus.au3>
    #include <Array.au3>
    #include <GUIConstantsEx.au3>
    ;Travelling Salesman Problem TSP

    [/autoit] [autoit][/autoit] [autoit]

    $anzahl = 80
    Dim $a[$anzahl] ;anzahl knoten
    Global $x[$anzahl] ;x-koordinate knoten
    Global $y[$anzahl] ;y-koordinate knoten
    Global $abstand[$anzahl][$anzahl] ;abstand Punkt_x zu Punkt_y
    Global $Ameisenmatrix[$anzahl][$anzahl]
    Global $ameisenbackup[$anzahl][$anzahl]
    Dim $kuerzester[$anzahl] ;kürzeste strecke zwischen Punkt_x und allen anderen Punkten
    Dim $nachfolger[$anzahl] ;nächster punkt, der mit dem geringsten Weg zu erreichen ist
    Dim $nachfolgerbackup[$anzahl] ; -1 an alle punkte
    Dim $nachfolgerminimum[$anzahl] ; bisher kleinste strecke
    ;dim $nachfolger_mini[$anzahl]
    ;Global $l ;länge der gesamten strecke

    [/autoit] [autoit][/autoit] [autoit]

    $max_x_gui = 500
    $max_y_gui = 500
    $new = 0 ;wenn 1, dann neue koordinaten, wenn 0, dann koordinaten aus datei
    $minimum = 2.3e22

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    $hgui = GUICreate("TSP", $max_x_gui + 20, $max_y_gui + 20, 1, 1)
    GUISetState()

    [/autoit] [autoit][/autoit] [autoit]

    ; Zeichnet eine Linie
    _GDIPlus_Startup()
    $hGraphic = _GDIPlus_GraphicsCreateFromHWND($hgui)
    $hPen = _GDIPlus_PenCreate()
    $hPen2 = _GDIPlus_PenCreate(0xFFFF0000) ;rot
    $hPen3 = _GDIPlus_PenCreate(0xFF0000FF) ;blau
    If $new Then
    FileDelete("TSP.dat") ;datei enthält die koordinaten
    ;koordinaten
    For $i = 0 To $anzahl - 1
    $x[$i] = Random(1, $max_x_gui, 1)
    $y[$i] = Random(1, $max_y_gui, 1)
    ;_GDIPlus_GraphicsDrawEllipse($hGraphic, $x[$i],$y[$i],5,5, $hPen)
    _GDIPlus_GraphicsDrawString($hGraphic, $i, $x[$i], $y[$i])
    FileWriteLine("TSP.dat", $x[$i] & "," & $y[$i] & @CRLF) ;koordinaten in datei schreiben
    Next
    Else ;koordinaten aus datei lesen
    For $i = 0 To $anzahl - 1
    $line = StringSplit(FileReadLine("TSP.dat", $i + 1), ",", 3)
    $x[$i] = $line[0]
    $y[$i] = $line[1]
    ;_GDIPlus_GraphicsDrawEllipse($hGraphic, $x[$i],$y[$i],5,5, $hPen)
    _GDIPlus_GraphicsDrawString($hGraphic, $i, $x[$i], $y[$i])
    Next

    [/autoit] [autoit][/autoit] [autoit]

    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    ;alle abstände punkt zu punkt festlegen
    For $p1 = 0 To $anzahl - 1
    ;$nachfolger[$p1]=$p1+1
    For $p2 = 0 To $anzahl - 1
    If $p2 = $p1 Then ContinueLoop
    $dx = $x[$p1] - $x[$p2] ;s=punkt z=nächster punkt
    $dy = $y[$p1] - $y[$p2]
    ;_GDIPlus_GraphicsDrawLine ($hGraphic,$x[$s],$y[$s] , $x[$z],$y[$z], $hPen)
    $abstand[$p1][$p2] = Int(Sqrt(($dx * $dx) + ($dy * $dy)))
    Next
    Next
    ;$nachfolger[$anzahl-1]=0
    ;_arraydisplay($nachfolger)

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    For $i = 0 To $anzahl - 1
    $nachfolgerbackup[$i] = -1 ;füllen, damit beim nachfolger prüfen die 0 nicht standard ist
    Next
    $step = 1
    ;If $anzahl>100 then $step=3
    ;If $anzahl>1000 then $step=5

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    ;verfahren Nearest-Neighbour-Heuristik
    For $e = 5 To $anzahl - 1 Step $step ;jeden punkt einmal als startpunkt wählen
    ; inkuerzestepunkteinbauen($e)
    randomneighbour($e)
    nearestneighbour($e)
    _GDIPlus_GraphicsClear($hGraphic, 0xFFFFFFFF)
    $lang = laenge()
    ;msgbox(0,$lang,0)
    ;ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $l = ' & $l & @crlf & '>Error code: ' & @error & @crlf) ;### Debug Console

    [/autoit] [autoit][/autoit] [autoit]

    If $new = 1 And $e = 0 And $anzahl < 10 Then
    $combi = _ArrayPermute($nachfolger, ",")
    _ArrayDisplay($combi)
    $pp = 2.3e12
    For $i = 1 To $combi[0]
    $q = laenge_perm($combi[$i])
    If $q < $pp Then
    ConsoleWrite($combi[$i] & " " & $q & @CRLF)
    $pp = $q ;kürzestes merken
    $k = $i ;combi merken
    EndIf
    Next

    [/autoit] [autoit][/autoit] [autoit]

    MsgBox(0, $pp, "minimum brute = " & $combi[$k])
    EndIf

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    $lang = tauschen($lang)

    [/autoit] [autoit][/autoit] [autoit]

    $lang1 = $lang
    ;msgbox(0,"kantentauschen los",$lang)
    While 1 ;so lange kanten tauschen und punkte einbauen, bis kürzeste strecke erreicht ist
    $lang = kantentauschen($lang)
    If $lang < $lang1 Then
    $lang1 = $lang
    WinSetTitle($hgui, "", "TSP L=" & $lang & " e=" & $e & " mini=" & $minimum)
    ; msgbox(0,"kürzere gefunden",$lang1)
    Else
    $lang = naherpunktinkanteeinbauen($lang)
    If $lang < $lang1 Then
    $lang1 = $lang
    Else
    ExitLoop
    EndIf
    EndIf
    WEnd
    ;ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $l = ' & $lang &" "&$e&" altes mini= "&$minimum&" "&$ltest& @crlf & '>Error code: ' & @error & @crlf) ;### Debug Console

    [/autoit] [autoit][/autoit] [autoit]

    If $lang < $minimum Then
    $minimum = $lang
    laenge()
    MsgBox(0, "neues minimum", $minimum, 1)
    Eintragenmatrix(1 / $lang / $lang) ;trägt jede Kante in eine von/nach-Matrix ein
    $nachfolgerminimum = $nachfolger
    Else
    Eintragenmatrix(1 / $lang / $lang) ;trägt jede Kante in eine von/nach-Matrix ein
    EndIf
    ;MsgBox(0, $l, "kürzeste Strecke gefunden!")
    Next
    MsgBox(0, $minimum, "kürzeste Strecke gefunden!")
    _ArrayDisplay($Ameisenmatrix)
    $ameisenbackup = $Ameisenmatrix
    ;kürzester ameisenweg
    $lamg1 = 2.2e22
    ;For $start = 0 To $anzahl - 1
    ;For $i = 0 To $anzahl - 1

    [/autoit] [autoit][/autoit] [autoit]

    For $v = 0 To $anzahl - 1
    $maximum = 0
    For $n = 0 To $anzahl - 1
    If $n = $v Then ContinueLoop
    $kante = $Ameisenmatrix[$v][$n]
    If $kante > $maximum Then
    $maximum = $kante
    $v_max = $v
    $n_max = $n
    ;$nachfolger[$v] = $n
    ;For $t = 0 To $anzahl - 1
    ;$Ameisenmatrix[$v][$n] = 0 ;spalte löschen
    ;Next
    ;
    ;$Ameisenmatrix[$n][$v]=0
    EndIf
    Next
    Next
    $nachfolger[$v_max] = $n_max
    $Ameisenmatrix[$v_max][$n_max] = 0
    ;Next

    [/autoit] [autoit][/autoit] [autoit]

    $lang = laenge()
    ; _ArrayDisplay($nachfolger)
    ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $lang = ' & $lang & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console
    If $lang < $lang1 Then
    ;MsgBox(0, $lang, "Ameisenweg kürzeste Strecke gefunden! bei startpunkt " & $i)
    $lang1 = $lang

    [/autoit] [autoit][/autoit] [autoit]

    EndIf
    $Ameisenmatrix = $ameisenbackup
    ;Next

    [/autoit] [autoit][/autoit] [autoit]

    MsgBox(0, $lang, "Ameisenweg kürzeste Strecke gefunden! bei startpunkt " & $i)
    $nachfolger = $nachfolgerminimum
    laenge()

    [/autoit] [autoit][/autoit] [autoit]

    ;_ArrayDisplay($Ameisenmatrix)

    [/autoit] [autoit][/autoit] [autoit]

    Func tauschen($lang)
    Local $p, $v, $w
    Do

    [/autoit] [autoit][/autoit] [autoit]

    For $zz = 0 To 1 ;sicherheitsrunden
    ; ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $zz = ' & $zz & @crlf & '>Error code: ' & @error & @crlf) ;### Debug Console
    $i = 0
    $flag = 0
    For $z = 0 To $anzahl - 1
    $i = $nachfolger[$i]
    $p = $i
    $v = $nachfolger[$p]
    $w = $nachfolger[$v]
    $k = $nachfolger[$w]
    $u = $nachfolger[$k]
    $t = tauschen2($p, $v, $w, $k, $lang) ;2 punkte tauschen und schauen, ob die strecke kürzer wird

    [/autoit] [autoit][/autoit] [autoit]

    If $t < $lang Then ;wenn die länge nach dem tauschen kleiner ist, dann

    [/autoit] [autoit][/autoit] [autoit]

    _GDIPlus_GraphicsDrawLine($hGraphic, $x[$p], $y[$p], $x[$v], $y[$v], $hPen3)
    _GDIPlus_GraphicsDrawLine($hGraphic, $x[$v], $y[$v], $x[$w], $y[$w], $hPen3)
    _GDIPlus_GraphicsDrawLine($hGraphic, $x[$w], $y[$w], $x[$k], $y[$k], $hPen3)

    [/autoit] [autoit][/autoit] [autoit]

    _GDIPlus_GraphicsDrawLine($hGraphic, $x[$p], $y[$p], $x[$w], $y[$w], $hPen2)
    _GDIPlus_GraphicsDrawLine($hGraphic, $x[$v] + 1, $y[$v] + 1, $x[$w] + 1, $y[$w] + 1, $hPen2)
    _GDIPlus_GraphicsDrawLine($hGraphic, $x[$v], $y[$v], $x[$k], $y[$k], $hPen2)
    ;~ MsgBox(0, "tauschen2", $p & " " & $w & " " & $v & " " & $k & " mit L= "&$t&@crlf& _
    ;~ "ist kleiner als " & @crlf& _
    ;~ $p & " " & $v & " " & $w & " " & $k & " mit L= "&$lang,1)
    _GDIPlus_GraphicsClear($hGraphic, 0xFFFFFFFF)
    ;$ltest=laenge()
    $lang = $t
    $flag = 1
    EndIf
    $p = $i
    $v = $nachfolger[$p]
    $w = $nachfolger[$v]
    $k = $nachfolger[$w]
    $u = $nachfolger[$k]

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    $t = tauschen3links($p, $v, $w, $k, $u, $lang) ;3 punkte tauschen und schauen, ob die strecke kürzer wird
    ;ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $t = ' & $t & @crlf & '>Error code: ' & @error & @crlf) ;### Debug Console
    If $t < $lang Then ;wenn die länge nach dem tauschen kleiner ist, dann
    ;vorher
    _GDIPlus_GraphicsDrawLine($hGraphic, $x[$p], $y[$p], $x[$v], $y[$v], $hPen3)
    _GDIPlus_GraphicsDrawLine($hGraphic, $x[$v], $y[$v], $x[$w], $y[$w], $hPen3)
    _GDIPlus_GraphicsDrawLine($hGraphic, $x[$w], $y[$w], $x[$k], $y[$k], $hPen3)
    _GDIPlus_GraphicsDrawLine($hGraphic, $x[$k], $y[$k], $x[$u], $y[$u], $hPen3)
    ;nachher

    [/autoit] [autoit][/autoit] [autoit]

    _GDIPlus_GraphicsDrawLine($hGraphic, $x[$p], $y[$p], $x[$w], $y[$w], $hPen2)
    _GDIPlus_GraphicsDrawLine($hGraphic, $x[$w] + 1, $y[$w] + 1, $x[$k] + 1, $y[$k] + 1, $hPen2)
    _GDIPlus_GraphicsDrawLine($hGraphic, $x[$k], $y[$k], $x[$v], $y[$v], $hPen2)
    _GDIPlus_GraphicsDrawLine($hGraphic, $x[$v], $y[$v], $x[$u], $y[$u], $hPen2)
    ;~ MsgBox(0, "tauschen2links", $p & " " & $w & " " & $k & " " & $v & " " & $u &" mit L= "&$t&@crlf& _
    ;~ "ist kleiner als " & @crlf& _
    ;~ $p & " " & $v & " " & $w & " " & $k & " " & $u &" mit L= "&$lang,1 )
    _GDIPlus_GraphicsClear($hGraphic, 0xFFFFFFFF)
    ;$ltest=laenge()

    [/autoit] [autoit][/autoit] [autoit]

    $lang = $t
    $flag = 1
    EndIf
    $p = $i
    $v = $nachfolger[$p]
    $w = $nachfolger[$v]
    $k = $nachfolger[$w]
    $u = $nachfolger[$k]
    $t = tauschen3rechts($p, $v, $w, $k, $u, $lang) ;3 punkte tauschen und schauen, ob die strecke kürzer wird
    If $t < $lang Then ;wenn die länge nach dem tauschen kleiner ist, dann
    ;vorher
    _GDIPlus_GraphicsDrawLine($hGraphic, $x[$p], $y[$p], $x[$v], $y[$v], $hPen3)
    _GDIPlus_GraphicsDrawLine($hGraphic, $x[$v], $y[$v], $x[$w], $y[$w], $hPen3)
    _GDIPlus_GraphicsDrawLine($hGraphic, $x[$w], $y[$w], $x[$k], $y[$k], $hPen3)
    _GDIPlus_GraphicsDrawLine($hGraphic, $x[$k], $y[$k], $x[$u], $y[$u], $hPen3)
    ;nachher

    [/autoit] [autoit][/autoit] [autoit]

    _GDIPlus_GraphicsDrawLine($hGraphic, $x[$p], $y[$p], $x[$k], $y[$k], $hPen2)
    _GDIPlus_GraphicsDrawLine($hGraphic, $x[$k], $y[$k], $x[$v], $y[$v], $hPen2)
    _GDIPlus_GraphicsDrawLine($hGraphic, $x[$v] + 1, $y[$v] + 1, $x[$w] + 1, $y[$w] + 1, $hPen2)
    _GDIPlus_GraphicsDrawLine($hGraphic, $x[$w], $y[$w], $x[$u], $y[$u], $hPen2)
    ;~ MsgBox(0, "tauschen3rechts", $p & " " & $k & " " & $v & " " & $w & " " & $u &" mit L= "&$t&@crlf& _
    ;~ "ist kleiner als " & @crlf& _
    ;~ $p & " " & $v & " " & $w & " " & $k &" " & $u &" mit L= "&$lang,1)
    _GDIPlus_GraphicsClear($hGraphic, 0xFFFFFFFF)
    ;$ltest=laenge()
    $lang = $t
    $flag = 1
    EndIf
    Next
    Next
    Until $flag = 0
    Return $lang
    EndFunc ;==>tauschen

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    ;erste Methode
    ;vom ersten Punkt an den jeweils nächsten Punkt mit dem kleinsten Abstand anfahren
    Func laenge()
    Local $l = 0
    _GDIPlus_GraphicsClear($hGraphic, 0xFFFFFFFF)
    For $s = 0 To $anzahl - 1
    Local $p = $abstand[$s][$nachfolger[$s]]
    $l += $p
    _GDIPlus_GraphicsDrawString($hGraphic, $s, $x[$s], $y[$s])
    _GDIPlus_GraphicsDrawLine($hGraphic, $x[$s], $y[$s], $x[$nachfolger[$s]], $y[$nachfolger[$s]], $hPen)
    Next
    WinSetTitle($hgui, "", "TSP L=" & $l & " e=" & $e & " mini=" & $minimum)
    Return $l
    EndFunc ;==>laenge

    [/autoit] [autoit][/autoit] [autoit]

    Func laenge_perm($array) ;länge aller permutationen
    Local $l = 0
    $liste = StringSplit($array, ",", 3)
    ReDim $liste[$anzahl + 1]
    $liste[$anzahl] = $liste[0]
    For $s = 0 To $anzahl - 1
    Local $p = $abstand[$liste[$s]][$liste[$s + 1]]
    $l += $p
    Next
    Return $l
    EndFunc ;==>laenge_perm

    [/autoit] [autoit][/autoit] [autoit]

    Func tauschen2($p, $v, $w, $k, $h) ;vertauscht die beiden nachfolger und berechnet die neue länge
    ;p = punktnr v=nachfolger von p w=nachfolger von v
    $l1 = $abstand[$p][$v]
    $l3 = $abstand[$w][$k]
    $l_vorher = $l1 + $l3
    $ln1 = $abstand[$p][$w]
    $ln3 = $abstand[$v][$k]
    $l_nachher = $ln1 + $ln3
    If $l_nachher < $l_vorher Then ;wenn getauschte länge kleiner, dann tauschen
    $nachfolger[$v] = $k
    $nachfolger[$w] = $v
    $nachfolger[$p] = $w
    $h = $h - $l_vorher + $l_nachher
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    Return $h
    EndFunc ;==>tauschen2

    [/autoit] [autoit][/autoit] [autoit]

    Func tauschen3links($p, $v, $w, $k, $u, $h) ;vertauscht die beiden nachfolger und berechnet die neue länge

    [/autoit] [autoit][/autoit] [autoit]

    ;p = punktnr v=nachfolger von p w=nachfolger von v
    $l1 = $abstand[$p][$v]
    $l2 = $abstand[$v][$w]
    $l3 = $abstand[$w][$k]
    $l4 = $abstand[$k][$u]
    $l_vorher = $l1 + $l2 + $l3 + $l4
    $ln1 = $abstand[$p][$w]
    $ln2 = $abstand[$w][$k]
    $ln3 = $abstand[$k][$v]
    $ln4 = $abstand[$v][$u]
    $l_nachher = $ln1 + $ln2 + $ln3 + $ln4
    If $l_nachher < $l_vorher Then ;wenn getauschte länge kleiner, dann tauschen
    $nachfolger[$v] = $u
    $nachfolger[$k] = $v
    $nachfolger[$w] = $k
    $nachfolger[$p] = $w
    $h = $h - $l_vorher + $l_nachher
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    Return $h
    EndFunc ;==>tauschen3links

    [/autoit] [autoit][/autoit] [autoit]

    Func tauschen3rechts($p, $v, $w, $k, $u, $h) ;vertauscht die beiden nachfolger und berechnet die neue länge
    $l1 = $abstand[$p][$v]
    $l2 = $abstand[$v][$w]
    $l3 = $abstand[$w][$k]
    $l4 = $abstand[$k][$u]
    $l_vorher = $l1 + $l2 + $l3 + $l4
    $ln1 = $abstand[$p][$k]
    $ln2 = $abstand[$k][$v]
    $ln3 = $abstand[$v][$w]
    $ln4 = $abstand[$w][$u]
    $l_nachher = $ln1 + $ln2 + $ln3 + $ln4
    If $l_nachher < $l_vorher Then ;wenn getauschte länge kleiner, dann tauschen
    $nachfolger[$w] = $u
    $nachfolger[$v] = $w
    $nachfolger[$k] = $v
    $nachfolger[$p] = $k
    $h = $h - ($l_vorher - $l_nachher)
    EndIf
    Return $h
    EndFunc ;==>tauschen3rechts

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    ; Die Schleife wiederholt sich, bis der Benutzer die Beenden-Aktion der GUI auslöst
    Do
    Until GUIGetMsg() = $GUI_EVENT_CLOSE

    [/autoit] [autoit][/autoit] [autoit]

    ; Ressourcen freigeben
    _GDIPlus_PenDispose($hPen)
    _GDIPlus_GraphicsDispose($hGraphic)
    _GDIPlus_Shutdown()

    [/autoit] [autoit][/autoit] [autoit]

    Func schnittpunkt($p1, $p2, $p3, $p4) ;schneiden sich die strecken, wird 1 zurückgegeben
    ; if $m1=$m2 then return 0 ;parallel

    [/autoit] [autoit][/autoit] [autoit]

    EndFunc ;==>schnittpunkt

    [/autoit] [autoit][/autoit] [autoit]

    Func kantentauschen($h) ;vertauscht die start- und endpunkte zweier kanten und berechnet die neue länge
    Local $aswap[$anzahl] ;hilfsarray zum tauschen der reihenfolge
    ; _arraydisplay($nachfolger)
    $v = 0

    [/autoit] [autoit][/autoit] [autoit]

    For $kante1 = 0 To $anzahl - 3
    ; ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $kante1 = ' & $kante1 & @crlf & '>Error code: ' & @error & @crlf) ;### Debug Console
    $p = $v
    $v = $nachfolger[$p]
    $w = $v
    ;msgbox(0,"aussenschleife",$p&" "&$v)
    For $kante2 = $kante1 + 2 To $anzahl - 1
    $w = $nachfolger[$w]
    $k = $nachfolger[$w]

    [/autoit] [autoit][/autoit] [autoit]

    $l_nachher = $abstand[$v][$k] + $abstand[$p][$w]
    $l_vorher = $abstand[$p][$v] + $abstand[$w][$k]

    [/autoit] [autoit][/autoit] [autoit]

    ;if $p=9 and $v=14 Then msgbox(0,$w&" "&$k,$l_vorher&" "&$l_nachher)
    If $l_nachher < $l_vorher Then ;wenn getauschte länge kleiner, dann tauschen
    $aswap[0] = $v
    For $i = 1 To $anzahl ;alle nachfolger speichern in array von v bis w
    $aswap[$i] = $nachfolger[$aswap[$i - 1]]
    If $aswap[$i] = $w Then ExitLoop
    Next
    $nachfolger[$v] = $k
    For $m = $i To 1 Step -1
    $nachfolger[$aswap[$m]] = $aswap[$m - 1]
    Next
    $nachfolger[$p] = $w
    ; _arraydisplay($nachfolger)
    $v1 = $v ;v und w umbenennen
    $v = $w
    $w = $v1
    ;laenge()
    $h = $h - ($l_vorher - $l_nachher)
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    Next
    Next

    [/autoit] [autoit][/autoit] [autoit]

    Return $h ;neue länge zurückgeben
    EndFunc ;==>kantentauschen

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    Func naherpunktinkanteeinbauen($h)
    ;return $h
    $v = 0

    [/autoit] [autoit][/autoit] [autoit]

    For $kante1 = 0 To $anzahl - 3
    ; ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $kante1 = ' & $kante1 & @crlf & '>Error code: ' & @error & @crlf) ;### Debug Console
    $p = $v
    $v = $nachfolger[$p]
    $w = $v
    ;msgbox(0,"aussenschleife",$p&" "&$v)
    For $kante2 = $kante1 + 2 To $anzahl - 2
    $w = $nachfolger[$w]
    $k = $nachfolger[$w]
    $u = $nachfolger[$k] ;wenn ein punkt näher an der kante liegt, dann diesen punkt in die kante einbauen
    If $abstand[$p][$k] + $abstand[$k][$v] + $abstand[$w][$u] < $abstand[$p][$v] + $abstand[$w][$k] + $abstand[$k][$u] Then
    laenge()
    _GDIPlus_GraphicsDrawEllipse($hGraphic, $x[$k], $y[$k], 20, 20, $hPen2)

    [/autoit] [autoit][/autoit] [autoit]

    ;msgbox(0,"naher punkt= "&$k,$p&"--->"&$v)
    $nachfolger[$p] = $k
    $nachfolger[$k] = $v
    $nachfolger[$w] = $u
    $p = $k
    $h = laenge()
    ;msgbox(0,"punkt eingebaut","nf von "&$k&" = "&$nachfolger[$k])
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    Next
    Next

    [/autoit] [autoit][/autoit] [autoit]

    Return $h
    EndFunc ;==>naherpunktinkanteeinbauen

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    Func eintragenmatrix($o)
    $von = 0
    For $i = 0 To $anzahl - 1
    $nach = $nachfolger[$von]
    ;if $von<$nach then
    $Ameisenmatrix[$von][$nach] += $o
    ;Else
    ;$Ameisenmatrix[$nach][$von] += $o
    ;endif
    ;$Ameisenmatrix[$nach][$von] += 1
    ;msgbox(0,"von "&$von,"nach "&$nach)
    ;_arraydisplay($Ameisenmatrix)
    $von = $nachfolger[$von]
    ;$Ameisenmatrix[$nach][$]+=1 ;ggf weglassen
    Next
    ; _ArrayDisplay($Ameisenmatrix)
    EndFunc ;==>eintragenmatrix

    [/autoit] [autoit][/autoit] [autoit]

    Func nearestneighbour($e)
    Dim $kuerzester[$anzahl] ;kürzeste strecke zwischen Punkt_x und allen anderen Punkten
    Dim $nachfolger[$anzahl] ;nächster punkt, der mit dem geringsten Weg zu erreichen ist
    $nachfolger = $nachfolgerbackup
    ;Global $l ;länge der gesamten strecke
    $nachfolger[$e] = $e
    $s = $e

    [/autoit] [autoit][/autoit] [autoit]

    ;Array auffüllen und mit der "gierigen" Methode (der näheste mögliche punkt) das nachfolger-array aufbauen
    For $t = 0 To $anzahl - 1 ;punkte nacheinander abarbeiten
    $s = $nachfolger[$s]
    ;MsgBox(262144,'Debug line ~' & @ScriptLineNumber,'Selection:' & @lf & '$s' & @lf & @lf & 'Return:' & @lf & $s) ;### Debug MSGBOX
    $nachfolger[$s] = $e ;erster punkt= letzter punkt
    ; _arraydisplay($nachfolger)
    $kuerzester[$s] = Int(Sqrt($max_x_gui ^ 2 + $max_y_gui ^ 2)) ;maximal mögliche Strecke = diagonale der gui
    For $z = 0 To $anzahl - 1 ;abstände vom punkt zu allen möglichen anderen punkten bestimmen
    If $z = $e Then ContinueLoop ;punkt kann nicht den abstand zu sich selbst bestimmen
    If $abstand[$s][$z] <= $kuerzester[$s] Then ;falls es einen kleineren abstand zw 2 punkten gibt, dann
    For $r = 0 To $anzahl - 1 ;alle bisherigen nachfolger prüfen
    If $nachfolger[$r] = $z Then ContinueLoop 2
    Next
    $kuerzester[$s] = $abstand[$s][$z] ;diesen abstand merken
    $nachfolger[$s] = $z ;punkt, welcher am nächsten zum untersuchten punkt liegt
    EndIf
    Next
    Next
    EndFunc ;==>nearestneighbour

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    Func randomneighbour($e) ;mit einem punkt starten, zufällig den nächsten bestimmen, die kürzeste strecke bestimmen, den nächsten zufälligen punkt einbauen usw
    $restanzahl = $anzahl
    Dim $rest[$anzahl] ;array für die punkte, die noch nicht abgearbeitet sind
    For $i = 0 To $anzahl - 1 ;restarray füllen mit allen punkten
    $rest[$i] = $i
    Next
    _ArrayDelete($rest, $e) ;$e aus dem array löschen
    ;_ArrayDisplay($rest)
    $t = $e
    While 1 ;solange, bis keine zahl übrig bleibt
    $restanzahl = UBound($rest) - 1 ;restliche anzahl
    If $restanzahl = 0 Then ExitLoop ;keine zahl mehr übrig
    $naechster = Random(0, $restanzahl, 1) ;nächste zahl
    ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $naechster = ' & $naechster & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console
    $nachfolger[$t] = $rest[$naechster] ;aus dem restarray herausholen
    $t = $rest[$naechster]
    ; _arraydisplay($nachfolger)
    For $i = 0 To $restanzahl
    If $rest[$i] = $t Then
    _ArrayDelete($rest, $i)
    ExitLoop
    EndIf
    Next
    ;_arraydisplay($rest)

    [/autoit] [autoit][/autoit] [autoit]

    WEnd
    $nachfolger[$t] = $rest[0]
    $nachfolger[$rest[0]] = $e
    ;msgbox(0,0,0)
    ;_arraydisplay($nachfolger)
    EndFunc ;==>randomneighbour

    [/autoit] [autoit][/autoit] [autoit]

    Func inkuerzestepunkteinbauen($e)
    ;while 1 ;so lange, bis alle punkte verbaut sind
    If $e < 6 Then ;5 punkte ermitteln und verbinden
    ;$restanzahl=$e
    Dim $rest[$anzahl] ;array für die punkte, die noch nicht abgearbeitet sind
    For $i = 0 To $anzahl - 1 ;restarray füllen mit allen punkten
    $rest[$i] = $i
    Next
    _ArrayDelete($rest, $e) ;$e aus dem array löschen
    ;_ArrayDisplay($rest)
    $t = $e
    While 1 ;solange, bis keine zahl übrig bleibt
    $restanzahl = UBound($rest) - 1 ;restliche anzahl
    If $restanzahl = 0 Then ExitLoop ;keine zahl mehr übrig
    $naechster = Random(0, $restanzahl, 1) ;nächste zahl
    ;ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $naechster = ' & $naechster & @crlf & '>Error code: ' & @error & @crlf) ;### Debug Console
    $nachfolger[$t] = $rest[$naechster] ;aus dem restarray herausholen
    $t = $rest[$naechster]
    ; _arraydisplay($nachfolger)
    For $i = 0 To $restanzahl
    If $rest[$i] = $t Then
    _ArrayDelete($rest, $i)
    ExitLoop
    EndIf
    Next
    ;_arraydisplay($rest)

    [/autoit] [autoit][/autoit] [autoit]

    WEnd
    $nachfolger[$t] = $rest[0]
    $nachfolger[$rest[0]] = $e
    EndIf
    $lang1 = laenge()
    $lang = tauschen($lang1)

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    MsgBox(0, 0, 0)
    ;_arraydisplay($nachfolger)
    EndFunc ;==>inkuerzestepunkteinbauen

    [/autoit]


    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:

    ciao
    Andy


    "Schlechtes Benehmen halten die Leute doch nur deswegen für eine Art Vorrecht, weil keiner ihnen aufs Maul haut." Klaus Kinski
    "Hint: Write comments after each line. So you can (better) see what your program does and what it not does. And we can see what you're thinking what your program does and we can point to the missunderstandings." A-Jay

    Wie man Fragen richtig stellt... Tutorial: Wie man Script-Fehler findet und beseitigt...X-Y-Problem

    2 Mal editiert, zuletzt von Andy (25. Februar 2011 um 20:44)