Tek-Tips is the largest IT community on the Internet today!

Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!

Register Log in
  • Congratulations Mike Lewis on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!

Travelling Salesman Problem in QBasic 1

Status
Not open for further replies.
Sort by date Sort by votes
Hi pya,

Here is an example:
Code: 
[COLOR=#0000ff]'Travelling Salesman Problem[/color]

[COLOR=#0000ff]'number of cities[/color]
N = [COLOR=#ff00ff]7[/color]

[COLOR=#a52a2a][b]Dim[/b][/color] cities(N, N)
[COLOR=#a52a2a][b]Dim[/b][/color] visit(N + [COLOR=#ff00ff]1[/color])
[COLOR=#a52a2a][b]Dim[/b][/color] visit_distance(N)

[COLOR=#0000ff]'read data into matrix[/color]
[COLOR=#a52a2a][b]Print[/b][/color] [COLOR=#ff00ff]"Matrix of distances between the cities:"[/color]
[COLOR=#a52a2a][b]Print[/b][/color]
[COLOR=#a52a2a][b]For[/b][/color] i = [COLOR=#ff00ff]1[/color] To N
    [COLOR=#a52a2a][b]For[/b][/color] j = [COLOR=#ff00ff]1[/color] To N
        [COLOR=#a52a2a][b]Read[/b][/color] cities(i, j)
        [COLOR=#a52a2a][b]Print[/b][/color] cities(i, j);
    [COLOR=#a52a2a][b]Next[/b][/color] j
    [COLOR=#a52a2a][b]Print[/b][/color]
[COLOR=#a52a2a][b]Next[/b][/color] i
[COLOR=#a52a2a][b]Print[/b][/color]

[COLOR=#0000ff]'read data into vector[/color]
[COLOR=#a52a2a][b]Print[/b][/color] [COLOR=#ff00ff]"Visiting cities in this order:"[/color]
[COLOR=#a52a2a][b]Print[/b][/color]
[COLOR=#a52a2a][b]For[/b][/color] i = [COLOR=#ff00ff]1[/color] To N + [COLOR=#ff00ff]1[/color]
    [COLOR=#a52a2a][b]Read[/b][/color] visit(i)
    [COLOR=#a52a2a][b]Print[/b][/color] visit(i);
[COLOR=#a52a2a][b]Next[/b][/color] i
[COLOR=#a52a2a][b]Print[/b][/color]
[COLOR=#a52a2a][b]Print[/b][/color]

[COLOR=#0000ff]'compute partial distances[/color]
[COLOR=#a52a2a][b]Print[/b][/color] [COLOR=#ff00ff]"Distances between cities travelled:"[/color]
[COLOR=#a52a2a][b]Print[/b][/color]
[COLOR=#a52a2a][b]For[/b][/color] i = [COLOR=#ff00ff]1[/color] To N
    visit_distance(i) = cities(visit(i), visit(i + [COLOR=#ff00ff]1[/color]))
    [COLOR=#a52a2a][b]Print[/b][/color] visit_distance(i);
[COLOR=#a52a2a][b]Next[/b][/color] i
[COLOR=#a52a2a][b]Print[/b][/color]
[COLOR=#a52a2a][b]Print[/b][/color]

[COLOR=#0000ff]'compute sum of distances[/color]
total_distance = [COLOR=#ff00ff]0[/color]
[COLOR=#a52a2a][b]For[/b][/color] i = [COLOR=#ff00ff]1[/color] To N
    total_distance = total_distance + visit_distance(i)
[COLOR=#a52a2a][b]Next[/b][/color] i
[COLOR=#a52a2a][b]Print[/b][/color] [COLOR=#ff00ff]"Total distance travelled ="[/color]; total_distance


[COLOR=#0000ff]'---------------------------------------------------------------------[/color]
[COLOR=#0000ff]'Matrix contains distances between the cities[/color]
Distance_Matrix:
[COLOR=#a52a2a][b]Data[/b][/color] [COLOR=#ff00ff]0[/color],[COLOR=#ff00ff]34[/color],[COLOR=#ff00ff]36[/color],[COLOR=#ff00ff]37[/color],[COLOR=#ff00ff]31[/color],[COLOR=#ff00ff]33[/color],[COLOR=#ff00ff]35[/color]
[COLOR=#a52a2a][b]Data[/b][/color] [COLOR=#ff00ff]34[/color],[COLOR=#ff00ff]0[/color],[COLOR=#ff00ff]29[/color],[COLOR=#ff00ff]23[/color],[COLOR=#ff00ff]22[/color],[COLOR=#ff00ff]25[/color],[COLOR=#ff00ff]24[/color]
[COLOR=#a52a2a][b]Data[/b][/color] [COLOR=#ff00ff]36[/color],[COLOR=#ff00ff]29[/color],[COLOR=#ff00ff]0[/color],[COLOR=#ff00ff]17[/color],[COLOR=#ff00ff]12[/color],[COLOR=#ff00ff]18[/color],[COLOR=#ff00ff]17[/color]
[COLOR=#a52a2a][b]Data[/b][/color] [COLOR=#ff00ff]37[/color],[COLOR=#ff00ff]23[/color],[COLOR=#ff00ff]17[/color],[COLOR=#ff00ff]0[/color],[COLOR=#ff00ff]32[/color],[COLOR=#ff00ff]30[/color],[COLOR=#ff00ff]29[/color]
[COLOR=#a52a2a][b]Data[/b][/color] [COLOR=#ff00ff]31[/color],[COLOR=#ff00ff]22[/color],[COLOR=#ff00ff]12[/color],[COLOR=#ff00ff]32[/color],[COLOR=#ff00ff]0[/color],[COLOR=#ff00ff]26[/color],[COLOR=#ff00ff]24[/color]
[COLOR=#a52a2a][b]Data[/b][/color] [COLOR=#ff00ff]33[/color],[COLOR=#ff00ff]25[/color],[COLOR=#ff00ff]18[/color],[COLOR=#ff00ff]30[/color],[COLOR=#ff00ff]26[/color],[COLOR=#ff00ff]0[/color],[COLOR=#ff00ff]19[/color]
[COLOR=#a52a2a][b]Data[/b][/color] [COLOR=#ff00ff]35[/color],[COLOR=#ff00ff]24[/color],[COLOR=#ff00ff]17[/color],[COLOR=#ff00ff]29[/color],[COLOR=#ff00ff]24[/color],[COLOR=#ff00ff]19[/color],[COLOR=#ff00ff]0[/color]

[COLOR=#0000ff]'Vector contains the order in which to visit the cities[/color]
Visit_vector:
[COLOR=#a52a2a][b]Data[/b][/color] [COLOR=#ff00ff]4[/color],[COLOR=#ff00ff]3[/color],[COLOR=#ff00ff]5[/color],[COLOR=#ff00ff]1[/color],[COLOR=#ff00ff]6[/color],[COLOR=#ff00ff]7[/color],[COLOR=#ff00ff]2[/color],[COLOR=#ff00ff]4[/color]

Output:
tsp_output_1_s6optn.png
 
Upvote 0 Downvote
Hi Mikrom,

I think I did not make myself clear.

I am trying to find the shortest route from any city (example 4) back to 4, while going through ALL cities exactly once.

Travelling Salesman Problem – Qbasic
5 'Travelling Salesman Problem

10 'number of cities
20 N = 10

30 Dim cities(N, N)
40 Dim visit(N + 1)
50 Dim visit_distance(N)

60 'read data into matrix
70 Print "Matrix of distances between the cities:"
80 Print
90 For i = 1 To N
100 For j = 1 To N
110 Read cities(i, j)
120 Print cities(i, j);
130 Next j
140 Print
150 Next i
160 Print

170 'read data into vector
180 Print "Visiting cities in this order:"
190 Print
200 For i = 1 To N + 1
210 Read visit(i)
220 Print visit(i);
230 Next i
240 Print
250 Print

260 START = TIMER
270 'compute partial distances
280 Print "Distances between cities travelled:"
290 Print
300 For i = 1 To N
310 visit_distance(i) = cities(visit(i), visit(i + 1))
320 Print visit_distance(i);
330 Next i
340 Print
350 Print

360 'compute sum of distances
370 total_distance = 0
380 For i = 1 To N
390 total_distance = total_distance + visit_distance(i)
400 Next i
410 Print "Total distance travelled ="; total_distance
420 ELAPSED = TIMER – START
430 PRINT “elapsed time is” ; ELAPSED, “seconds”


440 '---------------------------------------------------------------------
450 'Matrix contains distances between the cities
460 Distance_Matrix:
470 Data 0,34,36,37,31,33,35,21,18,30
480 Data 34,0,29,23,22,25,24,31,20,27
490 Data 36,29,0,17,12,18,17,24,22,13
500 Data 37,23,17,0,32,30,29,16,33,29
510 Data 31,22,12,32,0,26,24,18,17,18
520 Data 33,25,18,30,26,0,19,20,18,22
530 Data 35,24,17,29,24,19,0,19,25,30
540 Data 21,31,24,16,18,20,19,0,21,24
550 Data 18,20,22,33,17,18,25,22,0,19
560 Data 30,27,13,29,18,22,30,24,19,0

700 'Vector contains the order in which to visit the cities
710 Visit_vector:
720 Data 4,3,5,1,6,7,2,4, 8,9,10

Your code, takes the visit vector, line 720, as input data.
I need to find the minimum route and then output the visit vector as the shortest route from city 4 back to 4, after visiting 1, 2, 3, 5, 6, 7,8,9,10,4 in any order which gives the shortest path.
Please see attached xls for 10 cities.

Seven cities will require enumerating 7! routes; 10 cities will require analysing 10! routes to find the shortest.

Thanx & Regards

Pervez

PS: I think I will take my star back :)
 
Upvote 0 Downvote
Hi Pya,

In the excel sheet for 7 cities you posted the visit vector was hard coded. I didn't found any computation how you computed it. So I hard coded it too.
To compute it like you want, one first need to solve how to generate all 7! permutations. I don't know it yet. Maybe we will find an algorithm.
 
Upvote 0 Downvote
Hi pya,

I found an algorithm how to compute all permutations: see QuickPerm algorithm here Then I could use it for programming TSP.

tsp_solver.bas
Code: 
[COLOR=#0000ff]'Travelling Salesman Problem[/color]

[COLOR=#0000ff]'number of cities[/color]
[COLOR=#804040][b]Const[/b][/color] N = [COLOR=#ff00ff]7[/color]

[COLOR=#804040][b]Dim[/b][/color] cities(N - [COLOR=#ff00ff]1[/color], N - [COLOR=#ff00ff]1[/color])
[COLOR=#804040][b]Dim[/b][/color] visit(N)
[COLOR=#804040][b]Dim[/b][/color] minimum_visit(N)
[COLOR=#804040][b]Dim[/b][/color] visit_distance(N - [COLOR=#ff00ff]1[/color])
[COLOR=#804040][b]Dim[/b][/color] minimum_visit_distance(N - [COLOR=#ff00ff]1[/color])
[COLOR=#804040][b]Dim[/b][/color] a(N - [COLOR=#ff00ff]1[/color])
[COLOR=#804040][b]Dim[/b][/color] p(N)

[COLOR=#804040][b]Call[/b][/color] populate_distance_matrix(cities())

output_file[COLOR=#2e8b57][b]$[/b][/color] = [COLOR=#ff00ff]"tsp_solver.txt"[/color]

[COLOR=#804040][b]Open[/b][/color] output_file[COLOR=#2e8b57][b]$[/b][/color] [COLOR=#804040][b]For[/b][/color] Output As [COLOR=#2e8b57][b]#1[/b][/color]

[COLOR=#804040][b]For[/b][/color] i = [COLOR=#ff00ff]0[/color] To N - [COLOR=#ff00ff]1[/color]
    a(i) = i + [COLOR=#ff00ff]1[/color]
[COLOR=#804040][b]Next[/b][/color]

[COLOR=#804040][b]For[/b][/color] i = [COLOR=#ff00ff]0[/color] To N
    p(i) = i
[COLOR=#804040][b]Next[/b][/color]

output_line[COLOR=#2e8b57][b]$[/b][/color] = [COLOR=#ff00ff]"Given number of cities:"[/color]
[COLOR=#804040][b]Print[/b][/color] output_line[COLOR=#2e8b57][b]$[/b][/color]
[COLOR=#804040][b]Print[/b][/color] [COLOR=#2e8b57][b]#1[/b][/color], output_line[COLOR=#2e8b57][b]$[/b][/color]

output_line[COLOR=#2e8b57][b]$[/b][/color] = [COLOR=#ff00ff]"a = "[/color] + int_array_to_string[COLOR=#2e8b57][b]$[/b][/color](a())
[COLOR=#804040][b]Print[/b][/color] output_line[COLOR=#2e8b57][b]$[/b][/color]
[COLOR=#804040][b]Print[/b][/color] [COLOR=#2e8b57][b]#1[/b][/color], output_line[COLOR=#2e8b57][b]$[/b][/color]

output_line[COLOR=#2e8b57][b]$[/b][/color] = [COLOR=#ff00ff]"All permutations:"[/color]
[COLOR=#804040][b]Print[/b][/color] output_line[COLOR=#2e8b57][b]$[/b][/color]
[COLOR=#804040][b]Print[/b][/color] [COLOR=#2e8b57][b]#1[/b][/color], output_line[COLOR=#2e8b57][b]$[/b][/color]

minimum_distance = [COLOR=#ff00ff]0[/color]
[COLOR=#0000ff]'-- QuickPerm algorithm[/color]
i = [COLOR=#ff00ff]0[/color]
nr = [COLOR=#ff00ff]1[/color]
[COLOR=#804040][b]Do[/b][/color] [COLOR=#804040][b]While[/b][/color] i < N
    p(i) = p(i) - [COLOR=#ff00ff]1[/color]
    j = [COLOR=#ff00ff]0[/color]
    [COLOR=#804040][b]If[/b][/color] i Mod [COLOR=#ff00ff]2[/color] = [COLOR=#ff00ff]1[/color] [COLOR=#804040][b]Then[/b][/color]
        j = p(i)
    [COLOR=#804040][b]End[/b][/color] [COLOR=#804040][b]If[/b][/color]
    [COLOR=#804040][b]Swap[/b][/color] a(i), a(j)
    i = [COLOR=#ff00ff]1[/color]
    [COLOR=#804040][b]Do[/b][/color] [COLOR=#804040][b]While[/b][/color] p(i) = [COLOR=#ff00ff]0[/color]
        p(i) = i
        i = i + [COLOR=#ff00ff]1[/color]
    [COLOR=#804040][b]Loop[/b][/color]

[COLOR=#0000ff]    '#-- processing one permutation[/color]
[COLOR=#0000ff]    'create visit vector from permutation a()[/color]
    [COLOR=#804040][b]Call[/b][/color] permutation_to_visit(a(), visit())
[COLOR=#0000ff]    'compute vector of distances between cities travelled[/color]
    [COLOR=#804040][b]Call[/b][/color] compute_visit_distances(cities(), visit(), visit_distance())

[COLOR=#0000ff]    'compute total distance travelled[/color]
    total_distance = total_distance_travelled(visit_distance())

[COLOR=#0000ff]    '-- print visit info[/color]
    [COLOR=#804040][b]Print[/b][/color] [COLOR=#804040][b]Using[/b][/color] [COLOR=#ff00ff]"####)"[/color]; nr,
    [COLOR=#804040][b]Print[/b][/color] [COLOR=#2e8b57][b]#1[/b][/color], [COLOR=#804040][b]Using[/b][/color] [COLOR=#ff00ff]"####)"[/color]; nr,

    output_line[COLOR=#2e8b57][b]$[/b][/color] = [COLOR=#ff00ff]" "[/color] _
                 + [COLOR=#ff00ff]"permutation a = "[/color] + int_array_to_string[COLOR=#2e8b57][b]$[/b][/color](a())
    [COLOR=#804040][b]Print[/b][/color] output_line[COLOR=#2e8b57][b]$[/b][/color]
    [COLOR=#804040][b]Print[/b][/color] [COLOR=#2e8b57][b]#1[/b][/color], output_line[COLOR=#2e8b57][b]$[/b][/color]

    output_line[COLOR=#2e8b57][b]$[/b][/color] = [COLOR=#ff00ff]"      "[/color] _
                 + [COLOR=#ff00ff]"visit = "[/color] + int_array_to_string[COLOR=#2e8b57][b]$[/b][/color](visit())
    [COLOR=#804040][b]Print[/b][/color] output_line[COLOR=#2e8b57][b]$[/b][/color]
    [COLOR=#804040][b]Print[/b][/color] [COLOR=#2e8b57][b]#1[/b][/color], output_line[COLOR=#2e8b57][b]$[/b][/color]

    output_line[COLOR=#2e8b57][b]$[/b][/color] = [COLOR=#ff00ff]"      "[/color] _
                 + [COLOR=#ff00ff]"visit_distance = "[/color] _
                 + int_array_to_string[COLOR=#2e8b57][b]$[/b][/color](visit_distance())
    [COLOR=#804040][b]Print[/b][/color] output_line[COLOR=#2e8b57][b]$[/b][/color]
    [COLOR=#804040][b]Print[/b][/color] [COLOR=#2e8b57][b]#1[/b][/color], output_line[COLOR=#2e8b57][b]$[/b][/color]

    output_line[COLOR=#2e8b57][b]$[/b][/color] = [COLOR=#ff00ff]"      "[/color] _
                 + [COLOR=#ff00ff]"total_distance = "[/color] + str[COLOR=#2e8b57][b]$[/b][/color](total_distance)
    [COLOR=#804040][b]Print[/b][/color] output_line[COLOR=#2e8b57][b]$[/b][/color]
    [COLOR=#804040][b]Print[/b][/color] [COLOR=#2e8b57][b]#1[/b][/color], output_line[COLOR=#2e8b57][b]$[/b][/color]
[COLOR=#0000ff]    '-- end of printing visit info[/color]

[COLOR=#0000ff]    'check minimum[/color]
    [COLOR=#804040][b]If[/b][/color] nr = [COLOR=#ff00ff]1[/color] [COLOR=#804040][b]Then[/b][/color]
        minimum_distance = total_distance
    [COLOR=#804040][b]End[/b][/color] [COLOR=#804040][b]If[/b][/color]

    [COLOR=#804040][b]If[/b][/color] total_distance < minimum_distance [COLOR=#804040][b]Then[/b][/color]
        minimum_distance = total_distance
        [COLOR=#804040][b]Call[/b][/color] assign_array(visit(), minimum_visit())
        [COLOR=#804040][b]Call[/b][/color] assign_array(visit_distance(), minimum_visit_distance())
        output_line[COLOR=#2e8b57][b]$[/b][/color] = [COLOR=#ff00ff]"      * ==> Less value found !"[/color]
        [COLOR=#804040][b]Print[/b][/color] output_line[COLOR=#2e8b57][b]$[/b][/color]
        [COLOR=#804040][b]Print[/b][/color] [COLOR=#2e8b57][b]#1[/b][/color], output_line[COLOR=#2e8b57][b]$[/b][/color]
    [COLOR=#804040][b]End[/b][/color] [COLOR=#804040][b]If[/b][/color]
[COLOR=#0000ff]    '#-- processing end[/color]

    nr = nr + [COLOR=#ff00ff]1[/color]
[COLOR=#804040][b]Loop[/b][/color]

[COLOR=#804040][b]Print[/b][/color]
[COLOR=#804040][b]Print[/b][/color] [COLOR=#2e8b57][b]#1[/b][/color], [COLOR=#ff00ff]""[/color]

[COLOR=#0000ff]'print result[/color]
output_line[COLOR=#2e8b57][b]$[/b][/color] = [COLOR=#ff00ff]"*******************"[/color]
[COLOR=#804040][b]Print[/b][/color] output_line[COLOR=#2e8b57][b]$[/b][/color]
[COLOR=#804040][b]Print[/b][/color] [COLOR=#2e8b57][b]#1[/b][/color], output_line[COLOR=#2e8b57][b]$[/b][/color]

output_line[COLOR=#2e8b57][b]$[/b][/color] = [COLOR=#ff00ff]"* Minimum Result: *"[/color]
[COLOR=#804040][b]Print[/b][/color] output_line[COLOR=#2e8b57][b]$[/b][/color]
[COLOR=#804040][b]Print[/b][/color] [COLOR=#2e8b57][b]#1[/b][/color], output_line[COLOR=#2e8b57][b]$[/b][/color]

output_line[COLOR=#2e8b57][b]$[/b][/color] = [COLOR=#ff00ff]"*******************"[/color]
[COLOR=#804040][b]Print[/b][/color] output_line[COLOR=#2e8b57][b]$[/b][/color]
[COLOR=#804040][b]Print[/b][/color] [COLOR=#2e8b57][b]#1[/b][/color], output_line[COLOR=#2e8b57][b]$[/b][/color]

output_line[COLOR=#2e8b57][b]$[/b][/color] = [COLOR=#ff00ff]"Visiting cities in this order:"[/color]
[COLOR=#804040][b]Print[/b][/color] output_line[COLOR=#2e8b57][b]$[/b][/color]
[COLOR=#804040][b]Print[/b][/color] [COLOR=#2e8b57][b]#1[/b][/color], output_line[COLOR=#2e8b57][b]$[/b][/color]

[COLOR=#804040][b]Print[/b][/color]
[COLOR=#804040][b]Print[/b][/color] [COLOR=#2e8b57][b]#1[/b][/color], [COLOR=#ff00ff]""[/color]

output_line[COLOR=#2e8b57][b]$[/b][/color] = int_array_to_string[COLOR=#2e8b57][b]$[/b][/color](minimum_visit())
[COLOR=#804040][b]Print[/b][/color] output_line[COLOR=#2e8b57][b]$[/b][/color]
[COLOR=#804040][b]Print[/b][/color] [COLOR=#2e8b57][b]#1[/b][/color], output_line[COLOR=#2e8b57][b]$[/b][/color]

[COLOR=#804040][b]Print[/b][/color]
[COLOR=#804040][b]Print[/b][/color] [COLOR=#2e8b57][b]#1[/b][/color], [COLOR=#ff00ff]""[/color]

output_line[COLOR=#2e8b57][b]$[/b][/color] = [COLOR=#ff00ff]"Distances between cities travelled:"[/color]
[COLOR=#804040][b]Print[/b][/color] output_line[COLOR=#2e8b57][b]$[/b][/color]
[COLOR=#804040][b]Print[/b][/color] [COLOR=#2e8b57][b]#1[/b][/color], output_line[COLOR=#2e8b57][b]$[/b][/color]

[COLOR=#804040][b]Print[/b][/color]
[COLOR=#804040][b]Print[/b][/color] [COLOR=#2e8b57][b]#1[/b][/color], [COLOR=#ff00ff]""[/color]

output_line[COLOR=#2e8b57][b]$[/b][/color] = int_array_to_string[COLOR=#2e8b57][b]$[/b][/color](minimum_visit_distance())
[COLOR=#804040][b]Print[/b][/color] output_line[COLOR=#2e8b57][b]$[/b][/color]
[COLOR=#804040][b]Print[/b][/color] [COLOR=#2e8b57][b]#1[/b][/color], output_line[COLOR=#2e8b57][b]$[/b][/color]

[COLOR=#804040][b]Print[/b][/color]
[COLOR=#804040][b]Print[/b][/color] [COLOR=#2e8b57][b]#1[/b][/color], [COLOR=#ff00ff]""[/color]

output_line[COLOR=#2e8b57][b]$[/b][/color] = [COLOR=#ff00ff]"Total distance travelled = "[/color] + Str[COLOR=#2e8b57][b]$[/b][/color](minimum_distance)
[COLOR=#804040][b]Print[/b][/color] output_line[COLOR=#2e8b57][b]$[/b][/color]
[COLOR=#804040][b]Print[/b][/color] [COLOR=#2e8b57][b]#1[/b][/color], output_line[COLOR=#2e8b57][b]$[/b][/color]

[COLOR=#0000ff]'close output file[/color]
[COLOR=#804040][b]Close[/b][/color] [COLOR=#2e8b57][b]#1[/b][/color]

[COLOR=#0000ff]'---------------------------------------------------------------------[/color]
[COLOR=#0000ff]'Data[/color]
[COLOR=#0000ff]'---------------------------------------------------------------------[/color]
[COLOR=#0000ff]'Matrix contains distances between the cities[/color]
[COLOR=#0000ff]'Distance_Matrix:[/color]
[COLOR=#0000ff]'Data 0,34,36[/color]
[COLOR=#0000ff]'Data 35,20,29[/color]
[COLOR=#0000ff]'Data 40,29,10[/color]

Distance_Matrix:
[COLOR=#804040][b]Data[/b][/color] [COLOR=#ff00ff]0[/color],[COLOR=#ff00ff]34[/color],[COLOR=#ff00ff]36[/color],[COLOR=#ff00ff]37[/color],[COLOR=#ff00ff]31[/color],[COLOR=#ff00ff]33[/color],[COLOR=#ff00ff]35[/color]
[COLOR=#804040][b]Data[/b][/color] [COLOR=#ff00ff]34[/color],[COLOR=#ff00ff]0[/color],[COLOR=#ff00ff]29[/color],[COLOR=#ff00ff]23[/color],[COLOR=#ff00ff]22[/color],[COLOR=#ff00ff]25[/color],[COLOR=#ff00ff]24[/color]
[COLOR=#804040][b]Data[/b][/color] [COLOR=#ff00ff]36[/color],[COLOR=#ff00ff]29[/color],[COLOR=#ff00ff]0[/color],[COLOR=#ff00ff]17[/color],[COLOR=#ff00ff]12[/color],[COLOR=#ff00ff]18[/color],[COLOR=#ff00ff]17[/color]
[COLOR=#804040][b]Data[/b][/color] [COLOR=#ff00ff]37[/color],[COLOR=#ff00ff]23[/color],[COLOR=#ff00ff]17[/color],[COLOR=#ff00ff]0[/color],[COLOR=#ff00ff]32[/color],[COLOR=#ff00ff]30[/color],[COLOR=#ff00ff]29[/color]
[COLOR=#804040][b]Data[/b][/color] [COLOR=#ff00ff]31[/color],[COLOR=#ff00ff]22[/color],[COLOR=#ff00ff]12[/color],[COLOR=#ff00ff]32[/color],[COLOR=#ff00ff]0[/color],[COLOR=#ff00ff]26[/color],[COLOR=#ff00ff]24[/color]
[COLOR=#804040][b]Data[/b][/color] [COLOR=#ff00ff]33[/color],[COLOR=#ff00ff]25[/color],[COLOR=#ff00ff]18[/color],[COLOR=#ff00ff]30[/color],[COLOR=#ff00ff]26[/color],[COLOR=#ff00ff]0[/color],[COLOR=#ff00ff]19[/color]
[COLOR=#804040][b]Data[/b][/color] [COLOR=#ff00ff]35[/color],[COLOR=#ff00ff]24[/color],[COLOR=#ff00ff]17[/color],[COLOR=#ff00ff]29[/color],[COLOR=#ff00ff]24[/color],[COLOR=#ff00ff]19[/color],[COLOR=#ff00ff]0[/color]

[COLOR=#0000ff]'---------------------------------------------------------------------[/color]
[COLOR=#0000ff]'Functions and Subroutines[/color]
[COLOR=#0000ff]'---------------------------------------------------------------------[/color]
[COLOR=#804040][b]Function[/b][/color] int_array_to_string[COLOR=#2e8b57][b]$[/b][/color] (a())
    res[COLOR=#2e8b57][b]$[/b][/color] = [COLOR=#ff00ff]"["[/color]
    [COLOR=#804040][b]For[/b][/color] i = [COLOR=#ff00ff]0[/color] To UBound(a)
        res[COLOR=#2e8b57][b]$[/b][/color] = res[COLOR=#2e8b57][b]$[/b][/color] + LTrim[COLOR=#2e8b57][b]$[/b][/color](Str[COLOR=#2e8b57][b]$[/b][/color](a(i)))
        [COLOR=#804040][b]If[/b][/color] i < UBound(a) [COLOR=#804040][b]Then[/b][/color]
            res[COLOR=#2e8b57][b]$[/b][/color] = res[COLOR=#2e8b57][b]$[/b][/color] + [COLOR=#ff00ff]", "[/color]
        [COLOR=#804040][b]End[/b][/color] [COLOR=#804040][b]If[/b][/color]
    [COLOR=#804040][b]Next[/b][/color] i
    res[COLOR=#2e8b57][b]$[/b][/color] = res[COLOR=#2e8b57][b]$[/b][/color] + [COLOR=#ff00ff]"]"[/color]
    int_array_to_string[COLOR=#2e8b57][b]$[/b][/color] = res[COLOR=#2e8b57][b]$[/b][/color]
[COLOR=#804040][b]End[/b][/color] [COLOR=#804040][b]Function[/b][/color]

[COLOR=#804040][b]Function[/b][/color] total_distance_travelled (visit_distance())
    total_distance = [COLOR=#ff00ff]0[/color]
    [COLOR=#804040][b]For[/b][/color] i = [COLOR=#ff00ff]0[/color] To N - [COLOR=#ff00ff]1[/color]
        total_distance = total_distance + visit_distance(i)
    [COLOR=#804040][b]Next[/b][/color]
    total_distance_travelled = total_distance
[COLOR=#804040][b]End[/b][/color] [COLOR=#804040][b]Function[/b][/color]

[COLOR=#804040][b]Sub[/b][/color] permutation_to_visit (a(), visit())
[COLOR=#0000ff]    'create visit vector from one permutation[/color]
    [COLOR=#804040][b]For[/b][/color] i = [COLOR=#ff00ff]0[/color] To N - [COLOR=#ff00ff]1[/color]
        visit(i) = a(i)
    [COLOR=#804040][b]Next[/b][/color]
    visit(N) = a([COLOR=#ff00ff]0[/color])
[COLOR=#804040][b]End[/b][/color] [COLOR=#804040][b]Sub[/b][/color]

[COLOR=#804040][b]Sub[/b][/color] compute_visit_distances (cities(), visit(), visit_distance())
[COLOR=#0000ff]    'compute partial distances[/color]
    [COLOR=#804040][b]For[/b][/color] i = [COLOR=#ff00ff]0[/color] To N - [COLOR=#ff00ff]1[/color]
        visit_distance(i) = cities(visit(i) - [COLOR=#ff00ff]1[/color], visit(i + [COLOR=#ff00ff]1[/color]) - [COLOR=#ff00ff]1[/color])
    [COLOR=#804040][b]Next[/b][/color]
[COLOR=#804040][b]End[/b][/color] [COLOR=#804040][b]Sub[/b][/color]

[COLOR=#804040][b]Sub[/b][/color] populate_distance_matrix (cities())
[COLOR=#0000ff]    'read data into matrix[/color]
    [COLOR=#804040][b]Print[/b][/color] [COLOR=#ff00ff]"Matrix of distances between the cities:"[/color]
    [COLOR=#804040][b]Print[/b][/color]
    [COLOR=#804040][b]For[/b][/color] i = [COLOR=#ff00ff]0[/color] To N - [COLOR=#ff00ff]1[/color]
        [COLOR=#804040][b]For[/b][/color] j = [COLOR=#ff00ff]0[/color] To N - [COLOR=#ff00ff]1[/color]
            [COLOR=#804040][b]Read[/b][/color] cities(i, j)
            [COLOR=#804040][b]Print[/b][/color] cities(i, j);
        [COLOR=#804040][b]Next[/b][/color] j
        [COLOR=#804040][b]Print[/b][/color]
    [COLOR=#804040][b]Next[/b][/color] i
    [COLOR=#804040][b]Print[/b][/color]
[COLOR=#804040][b]End[/b][/color] [COLOR=#804040][b]Sub[/b][/color]

[COLOR=#804040][b]Sub[/b][/color] assign_array (a(), b())
[COLOR=#0000ff]    'b() <- a()[/color]
    [COLOR=#804040][b]For[/b][/color] i = [COLOR=#ff00ff]0[/color] To UBound(a)
        b(i) = a(i)
    [COLOR=#804040][b]Next[/b][/color]
[COLOR=#804040][b]End[/b][/color] [COLOR=#804040][b]Sub[/b][/color]

tsp_2022-02-17_nplapx.png


However you cannot see all 5040 permutation on the QB64 screen, so the program creates in the same directory the log file tsp_solver.txt which you can open with notepad and you can see all computation steps

tsp_solver.txt
Code: 
Given number of cities:
a = [1, 2, 3, 4, 5, 6, 7]
All permutations:
   1) permutation a = [1, 2, 3, 4, 5, 6, 7]
      visit = [1, 2, 3, 4, 5, 6, 7, 1]
      visit_distance = [34, 29, 17, 32, 26, 19, 35]
      total_distance =  192
   2) permutation a = [2, 1, 3, 4, 5, 6, 7]
      visit = [2, 1, 3, 4, 5, 6, 7, 2]
      visit_distance = [34, 36, 17, 32, 26, 19, 24]
      total_distance =  188
      * ==> Less value found !

...
...
...
...

5039) permutation a = [2, 7, 3, 4, 5, 6, 1]
      visit = [2, 7, 3, 4, 5, 6, 1, 2]
      visit_distance = [24, 17, 17, 32, 26, 33, 34]
      total_distance =  183
5040) permutation a = [7, 2, 3, 4, 5, 6, 1]
      visit = [7, 2, 3, 4, 5, 6, 1, 7]
      visit_distance = [24, 29, 17, 32, 26, 33, 35]
      total_distance =  196

*******************
* Minimum Result: *
*******************
Visiting cities in this order:

[2, 4, 3, 5, 1, 6, 7, 2]

Distances between cities travelled:

[23, 17, 12, 31, 33, 19, 24]

Total distance travelled =  159
 
Upvote 0 Downvote
Hi Mikrom,

Just thrilled to receive your response.

Will try it out later.

If it works I will give you another star.
If it does not I will take back the first star :)

Thanx

Pervez
 
Upvote 0 Downvote
Hi pya,

I tested it on several cases, the largest case was with ten cities and it always calculated a result :)
 
Upvote 0 Downvote
Hi mikrom,

When you have time can you please look at the ERROR I get when running your code.

Also, I do not understand Lines 2320 - 2360.

The Distance Matrix lines 2370 - 2384 I recognise as the distance between cities 1 to 7.

But what do lines 2320 - 2360 represent?

Regards

Pervez

PS: No urgency on this issue.
Please respond when convenient.
 
 https://files.engineering.com/getfile.aspx?folder=470261ba-505e-4c7e-b06b-14c9581bee70&file=TSP7_Failure.PNG
Upvote 0 Downvote
Hi pya,
pya said:
When you have time can you please look at the ERROR I get when running your code.
...
Attached is the compilelog ...
Click to expand...

In the compile log you attached are only these lines
Code: 
In file included from qbx.cpp:2120:0:
..\\temp\\main.txt:1285:1: error: 'LABEL_2700' does not name a type
compilation terminated due to -Wfatal-errors.
From this I can not determine what the cause of the error is.
Maybe you changed something in the program improperly.
The code I posted, I tested before in QB64 on two PCs: my home PC with Linux and my work PC with Windows 10. It runs successfully on both.
First try to run the program as I posted it, without changing anything.
I also noticed from the screenshot you posted that you have a different version of QB64 than me. You have a 32 bit version (QB64 x32) and I have a 64 bit version (QB64 x64).
If I can't reproduce your error, then unfortunately I can't help you

pya said:
Also, I do not understand Lines 2320 - 2360.
Click to expand...
I don't know what line numbers you mean.
The program I posted has only 236 lines - see the screenshot:
Screenshot_at_2022-02-19_10-16-16_abg4ki.png
 
Upvote 0 Downvote
Hi mikrom,

Mea Culpa!

I took your advice and your untouched (untouched by human hands?) version worked!

I must have screwed up during line numbering.

Thanx for all your help.

Pervez
 
Upvote 0 Downvote
Hi mikrom,

I ran your code for 10 cities and it worked fine.

But, I have a couple of questions and would be grateful if you could answer at your convenience.

1. I do not understand the first set of Distance Matrix - DATA 0,34,36 and the following 2 lines.

2. My 2nd question is where is the right place to put a TIMER?
I start the timer after the initial 7 DIM statements and end it just before Functions and Subroutines

My aim is to calculate the computing time only and not include any printing or output time.

Your help appreciated.

Pervez

'Data
'---------------------------------------------------------------------
'Matrix contains distances between the cities
'Distance_Matrix:
'Data 0,34,36
'Data 35,20,29
'Data 40,29,10

Distance_Matrix:
Data 0,34,36,37,31,33,35,21,18,30
Data 34,0,29,23,22,25,24,31,20,27
Data 36,29,0,17,12,18,17,24,22,13
Data 37,23,17,0,32,30,29,16,33,29
Data 31,22,12,32,0,26,24,18,17,18
Data 33,25,18,30,26,0,19,20,18,22
Data 35,24,17,29,24,19,0,19,25,30
Data 21,31,24,16,18,20,19,0,21,24
Data 18,20,22,33,17,18,25,22,0,19
Data 30,27,13,29,18,22,30,24,19,0

ELAPSED = TIMER – START
PRINT “elapsed time is”; ELAPSED, “secs”

'---------------------------------------------------------------------
'Functions and Subroutines
'---------------------------------------------------------------------
 
Upvote 0 Downvote
Hi pya,

To your questions:
I do not understand the first set of Distance Matrix - DATA 0,34,36 and the following 2 lines.
Click to expand...
As you could see these lines begin with ' and are set on comments. It was only a small example of three cities on which I tested the program during development. You can delete these lines.

My 2nd question is where is the right place to put a TIMER?
I start the timer after the initial 7 DIM statements and end it just before Functions and Subroutines
Click to expand...
I would START the timer as you have done and END it after the main program is over i.e. after these lines
Code: 
'close output file
Close #1

My aim is to calculate the computing time only and not include any printing or output time.
Click to expand...
Then make your own modification of the program, where you remove:
commands for opening and closing output file
all commands needed for printing the intermediate results on the screen and in the file, i.e. statements which begin with [tt]output_line$[/tt] and [tt]Print[/tt]


 
Upvote 0 Downvote
Hi mikrom,

One last question:

How do I insert spaces between the brackets in the output?

( 2, .....7, 2 ) and ( 23, .... 19, 24 )

At my age I can get confused if the output is like

(2, ....7, 2) and (23, .....19,24)

I modified a few lines but got no change.

Regards

Pervez
 
 https://files.engineering.com/getfile.aspx?folder=dc5dd292-d45f-49d7-8bbf-071ae3327c39&file=TSP7_-_Output.PNG
Upvote 0 Downvote
You can insert the spaces in the function [tt]int_array_to_string$[/tt]
 
Upvote 0 Downvote
Status
Not open for further replies.

Similar threads

pya
  • Locked
  • Question
Data Type Mismatch in QBASIC 1
Replies
7
Views
292
mikrom
mikrom
pya
  • Locked
  • Question
Name already in use ERROR
Replies
3
Views
225
mikrom
mikrom
Murugank
  • Locked
  • Question
Get source code from a QBasic exe
Replies
1
Views
216
mikrom
mikrom
PeterTX
  • Locked
  • Question
Error in reading data file QB64
Replies
4
Views
213
mikrom
mikrom
pya
  • Locked
  • Question
Branching with Strings Input
Replies
1
Views
142
mikrom
mikrom

Part and Inventory Search

Sponsor

Back
Top