Travelling Salesman Problem in QBasic
Travelling Salesman Problem in QBasic
(OP)
Has anyone written a code in QBasic to solve the Travelling Salesman Problem?
I can solve it in Excel Solver but would be interested in the code.
Pervez
I can solve it in Excel Solver but would be interested in the code.
Pervez
RE: Travelling Salesman Problem in QBasic
Here is an example:
CODE
Output:
RE: Travelling Salesman Problem in QBasic
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 :)
RE: Travelling Salesman Problem in QBasic
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.
RE: Travelling Salesman Problem in QBasic
I found an algorithm how to compute all permutations: see QuickPerm algorithm here https://www.quickperm.org
Then I could use it for programming TSP.
tsp_solver.bas
CODE
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
RE: Travelling Salesman Problem in QBasic
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
RE: Travelling Salesman Problem in QBasic
I tested it on several cases, the largest case was with ten cities and it always calculated a result
RE: Travelling Salesman Problem in QBasic
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.
RE: Travelling Salesman Problem in QBasic
Attached is the compilelog which I forgot to attach before.
Pervez
RE: Travelling Salesman Problem in QBasic
In the compile log you attached are only these lines
CODE
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
I don't know what line numbers you mean.
The program I posted has only 236 lines - see the screenshot:
RE: Travelling Salesman Problem in QBasic
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
RE: Travelling Salesman Problem in QBasic
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
'---------------------------------------------------------------------
RE: Travelling Salesman Problem in QBasic
To your questions:
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.
I would START the timer as you have done and END it after the main program is over i.e. after these lines
CODE
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 output_line$ and Print
RE: Travelling Salesman Problem in QBasic
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
RE: Travelling Salesman Problem in QBasic