Optimal route calculation

[Acanis]

Hey, I'm trying to figure out what my algorithm has to look like so that I can reach a certain number of targets from a starting point and go back again with a minimum number of steps.
I found Dijkstra and A*, but I don't know if it's too complex for this problem and how to start correctly with the AutoIt implementation.

Can you please help me or give me a hint?

My code so far:

expandcollapse popup

#include <Array.au3>

Dim $aArray[20][20] ; x/y

Local $aHome[1][2] = [[8, 9]] ; Array starts with 0, so 7/8 in $aArray
Local $aTargets[6][2] = [[7, 11], [8, 12], [9, 7], [7, 5], [10, 10], [5, 9]]

;~ ********************
;~ ********************
;~ ********************
;~ ********************
;~ ******4*************
;~ ********************
;~ ********3***********
;~ ********************
;~ ****6**H************
;~ *********5**********
;~ ******1*************
;~ *******2************
;~ ********************
;~ ********************
;~ ********************
;~ ********************
;~ ********************
;~ ********************
;~ ********************
;~ ********************
; Find an algorithm that calculates the optimal way to run from a coordinate to x (3 / 4) targets in a Cartesian coordinate system and to end back at the initial coordinate.

; Test Distance Home -> Target 1 (8/9 to 7/11)
Dim $aTarget[1][2] = [[$aTargets[0][0], $aTargets[0][1]]]
ConsoleWrite("Test Home -> Target 1: " & (getDistance($aHome, $aTarget) = 2) & @CRLF)


Func getDistance($aHome, $aTarget)
    Local $aX = $aHome[0][0], $aY = $aHome[0][1], $bX = $aTarget[0][0], $bY = $aTarget[0][1]
    Local $iDist = Min(Abs($aX - $bX), Abs($aY - $bY))

    $aX += $aX > $bX ? -$iDist : $iDist
    $aY += $aY > $bY ? -$iDist : $iDist

    Return $iDist + Abs($aX - $bX) + Abs($aY - $bY)
EndFunc

Func getCoordInArray($aArray)
    Dim $aArray2[1][2] = [[$aArray[0] - 1, $aArray[1] -1]]

    Return $aArray2
EndFunc

Func Min($a, $b)
    Return $a < $b ? $a : $b
EndFunc

Thank you

[RTFC]

You may wish to study the TSP example here.

Alternatively, you can ask an amoeba.

Edited December 22, 2018 by RTFC

[Acanis]

1 hour ago, RTFC said:

You may wish to study the TSP example here.

Alternatively, you can ask an amoeba.

Thank you - looks good. I try to understand the TSP example, even its different, because I dont want to go to "every city". I have to say, that its not easy to understand the script (for me^^), you use a lot of Globals and even if its just 300 lines (and I can skip/delete the GUI), I feel a little overwhelmed. But I try to follow this puls.

I like the idea behind Simulated Annealing. Iam just a little inexperienced^^.