Problem bei Array bzw. Routen

    Hallo
    ich möchte gerne die kürzeste route berechnen lassen.

    Die verschiedenen Knotenpunkte und die Längen der Wege habe ich.

    nun wollte ich alle möglichen Kombinationen von (z. B. den Wegpunkten A,B,C,D,E) berechnen lassen und dann die Strings oder Arrays (ich weiß net welches format ich da nehme...) mit stringsplit in die Einzelteile zerlegen.

    [autoit]

    $Teile = StringSplit ("z. B. C,A,B","")

    [/autoit]


    nun muss ich aber die Strecken einbinden und da ist es dann vorbei. dachte an soetwas:

    [autoit]

    If $Teile[1] = M Then
    $Laenge = $Laenge + 19
    # weiter für alle möglichen string Teile
    EndIf

    [/autoit]


    die 19 wäre dann hier die Strecke.

    es würde so ja auch gehen aber es wäre extrem viel schreibarbeit und dann auch sehr spezifisch.

    Hat jemand verstanden was ich will?
    Falls ja wäre ich für Hilfe sehr dankbar.

    Einmal editiert, zuletzt von Gandalf (14. Februar 2013 um 18:45)

    :( die habe ich leider selber nicht.

    Ich erkläre es nocheinmal etwas anders.
    ich habe eine Zeichenfolge die ich auseinander nehme. Die Zeichen die ich dann habe sind immer in anderen Reihenfolgen.
    jedes dieser Zeichen (immer Buchstaben) hat einen zzweiten zugeordneten wert (immer eine Zahl).

    ich will nun den gesamten Zahlen wert der Buchstaben folge errechnen lassen

    z. B.
    A=5
    B=8
    C=10

    dann ist CB = 18
    oder ACB= 23

    die Reihenfolge ist total egal, da die werte ja eh addiert werden.

    ich hoffe das es so etwas besser um schrieben ist. :S

    Und wo ist das Problem?
    Du speicherst einfach alle Möglichkeiten ab und dann vergleichst du und suchst dir die kürzeste Strecke heraus.
    Ist doch ganz easy ...

    Musst nur aufpassen das du wirklich alle Kombinationen vergleichst :D

    2 Mal editiert, zuletzt von Yjuq (12. Februar 2013 um 21:37)

    Alle Möglichkeiten berechnen bekomme ich hin.

    Dann teile ich es.

    Aber dann ist es ein array.
    Klar kann ich (siehe post 1) es vergleichen aber das muss doch einfacher gehen als ih versucht habe. Oder?

    Also die gesplitteten Teile nehmen und deren Zahlen Werte addieren.
    Aber das bekomme ich halt nicht hin.
    Kann mir das einer erklären/zeigen?

    Sobald die Anzahl der Knoten/Strecken steigt wirst du dich mit deinem verfahren dumm und dämlich rechnen... ^^
    Abhilfe schaffen geeignete Algorithmen, wie sie zum Beispiel hier schön erklärt werden. ;)

    LG
    Christoph :)

    Ich denke du suchst http://de.wikipedia.org/wiki/A*-Algorithmus Und da du dies ja nicht für ein Spiel sondern für die Stauumfahrung deiner Aussendienstmitarbeiter benötigst kannst du mir den sicherlich vorhandenen Link zu einer Entfernungstabelle aller dt. Städte zu ihren auf direktem Weg erreichbaren Nachbarn einstellen. Ungefähr so wie in http://upload.wikimedia.org/wikipedia/comm…ermany0.svg.png dargestellt nur in Tabellenform und für ganz Deutschland, das such ich schon länger :D

    mfg autoBert

    Ok Danke erstmal

    Wäre ja schon wenn ich außendienst mitarbeiter hätte :D

    Nein ist leider nicht für der artige zwecke.

    Lediglich ein eine auf gabe des informatik kurses der das allerdings mit java macht.
    Wollte das nur einmal auch mit autoit probiren.

    Das es irgendwann viel rechnen ist, ist mir klar.

    Kann man das denn irgendwie deutlich kürzen?
    Also an der stelle wo ist den String zerlegt habe und nun die strecke berechnen will?

    Hi,
    so wie ich das sehe, beschreibst du das TSP (Travelling Salesmen Problem). Bis zu einer Handvoll Punkte ist die optimale d.h. kürzeste Strecke per Bruteforce zu lösen, alles andere würde den Aufwand für eine "Hausarbeit" bei weitem sprengen.

    Zitat von Wikipedia

    ....Bei der einfachsten Variante, dem symmetrischen TSP mit Städten, gibt es verschiedene Rundreisen, das sind bei 15 Städten über 43 Milliarden und bei 18 Städten bereits über 177 Billionen. Wie schnell die Rechenzeit mit wachsender Anzahl von Städten wächst, zeigt das folgende Beispiel: hat man einen Rechner, der die Lösung für 30 Städte in einer Stunde berechnet, dann braucht dieser für zwei zusätzliche Städte annähernd die tausendfache Zeit; das sind mehr als 40 Tage....

    Der Bruteforce Lösungsansatz:
    Berechne die Strecken zwischen allen Punkten.
    Addiere die einzelnen Strecken zum Gesamtweg zwischen Anfang und Ende, wenn jeder Punkt nur einmal angefahren wird.
    Die kürzeste Strecke ist die Lösung....

    Beispiel auf die schnelle...

    Spoiler anzeigen
    [autoit]

    #include <Array.au3>
    #include <GDIPlus.au3>

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

    $max = 7 ;maximale Anzahl Punkte
    $max_x = 500
    $max_y = 500

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

    _GDIPlus_Startup()

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

    $hgui = GUICreate("TSP-Brute", $max_x, $max_y)
    GUISetState()

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

    $hGraphic = _GDIPlus_GraphicsCreateFromHWND($hgui)
    $hPen = _GDIPlus_PenCreate()

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

    Local $aArray[$max - 1] ;permutationen
    For $i = 0 To $max - 2
    $aArray[$i] = $i + 1
    Next

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

    Local $aNewArray = _ArrayPermute($aArray, ",") ;Using Default Parameters
    ;_ArrayDisplay($aNewArray, "Array Permuted")
    For $i = 1 To $aNewArray[0] ;anfangs- und endpunkt anfügen
    $aNewArray[$i] = "0," & $aNewArray[$i] & ",0"
    Next

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

    _ArrayDisplay($aNewArray)

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

    Dim $x[$max + 1], $y[$max + 1] ;koordinaten

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

    For $i = 0 To $max ;zufällige koordinaten
    $x[$i] = Random(1, $max_x, 1)
    $y[$i] = Random(1, $max_y, 1)
    Next

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

    $kuerzeste_strecke = 1e22

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

    For $i = 1 To $aNewArray[0] ;alle permutationen durchgehen
    $s = StringSplit($aNewArray[$i], ",") ;permutationen aufteilen
    ;_arraydisplay($s)
    $gesamtlaenge = 0
    For $c = 2 To $s[0] ;einzelteile
    $Strecke_zw_zwei_Punkten = Sqrt(($x[$s[$c - 1]] - $x[$s[$c]]) ^ 2 + ($y[$s[$c - 1]] - $y[$s[$c]]) ^ 2)
    _GDIPlus_GraphicsDrawLine($hGraphic, $x[$s[$c - 1]], $y[$s[$c - 1]], $x[$s[$c]], $y[$s[$c]], $hPen)
    ;~ sleep(100)
    $gesamtlaenge = $gesamtlaenge + $Strecke_zw_zwei_Punkten
    Next
    _GDIPlus_GraphicsClear($hGraphic, 0xFFF0F0F0)
    If $kuerzeste_strecke > $gesamtlaenge Then
    $kuerzeste_strecke = $gesamtlaenge
    ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $kuerzeste_strecke = ' & $kuerzeste_strecke & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console
    $kuerzeste_strecke_array = $i
    EndIf
    Next

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

    MsgBox(0, $aNewArray[$kuerzeste_strecke_array], $kuerzeste_strecke)

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

    ;kürzeste Strecke zeichnen
    $hPen = _GDIPlus_PenCreate(0xFFFF00FF, 2)
    $s = StringSplit($aNewArray[$kuerzeste_strecke_array], ",") ;permutationen aufteilen
    For $c = 2 To $s[0] ;einzelteile
    ;ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $c = ' & $c & @crlf & '>Error code: ' & @error & @crlf) ;### Debug Console
    $Strecke_zw_zwei_Punkten = Sqrt(($x[$s[$c - 1]] - $x[$s[$c]]) ^ 2 + ($y[$s[$c - 1]] - $y[$s[$c]]) ^ 2)
    _GDIPlus_GraphicsDrawLine($hGraphic, $x[$s[$c - 1]], $y[$s[$c - 1]], $x[$s[$c]], $y[$s[$c]], $hPen)
    ; $gesamtlaenge = $gesamtlaenge + $Strecke_zw_zwei_Punkten
    Next

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

    While GUIGetMsg() <> -3
    WEnd

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

    Hi,

    Zitat

    was ich nicht verstehe: Warum ist die kürzeste Strecke immer eine andere?


    Na, weil die Koordinaten der "Städte" bei jedem neuen Durchlauf zufällig erzeugt werden^^

    Zitat

    und wie kann ich in dein Programm einbinden das er nicht irgendwelche werte für die Punkte und längen benutzt sondern von mit vorgegebene?

    Einbinden ist schlecht, da hast du schneller ein Script geschrieben, dass zu deinem Problem passt...

    Zitat

    also z. B. für diese Karte? (siehe Anhang)

    Wieso taucht dein "Problem" erst im 11. Post auf 8|

    Naja, ich würde die einzelnen Strecken benennen und die Länge zuordnen => "B-I" = "I-B" = 34

    Jede "Stadt" hat Nachbarn, du kannst also eine Liste erstellen, um alle möglichen Wege vom Startpunkt zum Endpunkt zu erstellen.
    Gesucht, der Weg von A nach Y:
    Anfangen mit A

    A-M
    A-N
    A-D

    Nun die Nachbarn der Nachbarn

    A-M-C
    A-M-X
    A-M-I

    A-N-D
    A-N-X
    A-N-Z

    A-D-N
    A-D-B
    A-D-L

    usw usf....dann hast du irgendwann den Zielpunkt auf allen möglichen Wegen erreicht und musst nur noch den kürzesten Weg bestimmen

    Mögl. Lösungsweg:
    Eintragen der Start- und Zielstädte in ein Array (mit den Abständen) und dann einen Algorithmus schreiben, der den kürzesten Weg findet!

    In der Netzplantechnik nennt man das einen "Kritischen Pfad"

    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

    3 Mal editiert, zuletzt von Andy (14. Februar 2013 um 18:19)

    Danke Andy!

    Werde mich wohl ein bisschen damit beschäftigen müssen.
    Kann ich nicht den Algoritmus von Andy benutzen? Also Brut-Force?

    Ich setze mal auf gelöst und melde mich bei neuen Fragen.
    Wer zur letzen Frage noch was weiß kann es gerne noch schreiben ich gucke dann man rein.
    Danke

    Schau mal nach Scripten bzw Programmen in Basic zum Thema "Kritischer Pfad" (Kritischer Weg), da findest du sicher etwas...