The Traveling Salesman Problem

[lrcvs]

Code: Select all

'THE TRAVELING SALESMAN PROBLEM

CLS
DIM AS INTEGER ia,ib,ic,id,ie,ig,ih,ii,ij,ik,il,im,in
DIM AS DOUBLE  db

'ia: number of points
'ib: coord X traveler
'ic: coord Y traveler
'id: for/next variable of the number of points
'ie: x2 coordinate of the rest of the points
'ig: y2 coordinate of the rest of the points
'ih: flag 0 = not visited * 1 = yes visited
'ii: x coordinate max of the screen
'ij: y coordinate max of the screen
'ik: stores the index where the smallest distance is found
'il: final loop
'im: memory X coord traveler
'in: memory Y coord traveler

'da: array with coordinates, distances and visited flag
'db: the shortest distance from the traveler

CLS
INPUT "Number of points = ";ia
db = 999999
ik = 0
il = 0

DIM da (ia,4)AS DOUBLE

SCREEN 19

SCREENINFO ii,ij

RANDOMIZE TIMER

FOR id = 1 TO ia
    ie = INT(RND * (ii-2)+1)
    ig = INT(RND * (ij-2)+1)
    
    IF id = 1 THEN
        'this is the point of origin (coordinates of thE traveler)
        ib = ie
        ic = ig
        im = ib
        in = ic
        CIRCLE (ie,ig),5,12,,,,f
    END IF
    
    IF id > 1 THEN
        'these are the rest of the points
        CIRCLE(ie,ig),2,15,,,,f
        da(id,1)= ie
        da(id,2)= ig
        
        'here we calculate the distance from the point of the traveler, using Pythagoras       
        da(id,3)= SQR(ABS(((ib-da(id,1))^2) + ((ic-da(id,2))^2)))
        
        'here we start the flag at "0" all the coordinates of the rest of the points        
        da(id,4) = 0
    END IF
NEXT id

'here we look for the smallest distance with respect to the coordinates of the traveler
FOR id = 2 TO ia
    IF da(id,3) < db THEN
        db = da(id,3)
        ik = id
    END IF
NEXT id

'here we draw the line between the traveler and the nearest coordinate
LINE(ib,ic)-(da(ik,1),da(ik,2)),10

ib = da(ik,1)
ic = da(ik,2)
da(ik,4) = 1


'restart cycles
WHILE il < ia
    FOR id = 2 TO ia
        IF da(id,4) = 0 THEN
            da(id,3) = SQR(ABS(((ib-da(id,1))^2) + ((ic-da(id,2))^2)))
        END IF
    NEXT id
    
    db = 999999
    
    FOR id = 2 TO ia
        IF da(id,4) = 0 THEN
            IF da(id,3) < db THEN
                db = da(id,3)
                ik = id
            END IF
        END IF
    NEXT id
    
    LINE(ib,ic)-(da(ik,1),da(ik,2)),10
    
    ib = da(ik,1)
    ic = da(ik,2)
    da(ik,4) = 1
    
    il= il + 1
    IF il = ia -1 THEN
        'line of return to the point of origin
        LINE(da(ik,1),da(ik,2))-(im,in),14 
    END IF
    
WEND
SLEEP
END