Traveling Salesman Pb

Traveling Salesman Problem for the HP-41

Overview

1°) 2-Dimensional Problem
2°) 3-Dimensional Problem
3°) Spherical Problem

-These programs employ the "nearest neighbor algorithm".
-It's not the best algorithm to solve this problem, but it may perhaps be useful.

1°) 2-Dimensional Problem

Data Registers: • R00 = n = Nb of points ( Registers R00 thru R2n are to be initialized before executing "TSP" )

• R01 = x₁ • R03 = x₂ ...................................... • R2n-1 = x_n
• R02 = y₁ • R04 = y₂ ...................................... • R2n = y_n

Flags: /
Subroutines: /

01 LBL "TSP"
02 RCL 00
03 2
04 -
05 ST+ X
06 E3
07 /
08 ISG X
09 STO M
10 LBL 01
11 RCL M
12 2.004
13 +
14 STO N
15 E99
16 STO O
17 LBL 02
18 RCL IND M
19 RCL IND N
20 -

21 X^2
22 ISG M
23 ISG N
24 RCL IND M
25 RCL IND N
26 -
27 X^2
28 +
29 RCL O
30 X<=Y?
31 GTO 03
32 X<>Y
33 STO O
34 RCL N
35 RCL M
36 2
37 +
38 RCL IND X
39 X<> IND Z
40 STO IND Y

41 CLX
42 SIGN
43 ST- Z
44 -
45 RCL IND X
46 X<> IND Z
47 STO IND Y
48 CLX
49 LBL 03
50 SIGN
51 ST- M
52 ISG N
53 GTO 02
54 ST+ M
55 ISG M
56 GTO 01
57 RCL 00
58 ST+ X
59 STO M
60 STO N

61 RCL IND X
62 RCL 02
63 -
64 X^2
65 DSE N
66 RCL IND N
67 RCL 01
68 -
69 X^2
70 +
71 SQRT
72 DSE N
73 LBL 04
74 RCL IND M
75 RCL IND N
76 -
77 X^2
78 DSE M
79 DSE N
80 RCL IND M

81 RCL IND N
82 -
83 X^2
84 +
85 SQRT
86 +
87 DSE M
88 DSE N
89 GTO 04
90 RCL 00
91 ST+ X
92 E3
93 /
94 ISG X
95 X<>Y
96 CLA
97 END

( 161 bytes / SIZE 2n+1 )

STACK	INPUTS	OUTPUTS
Y	/	1.2n
X	/	Length

Example: The coordinates of 8 points are:

x | 1 2 6 7 9 8 3 4 R01 R03 R05 R07 R09 R11 R13 R15
y | 1 7 9 6 4 2 5 8 Store these 16 numbers into R02 R04 R06 R08 R10 R12 R14 R16 respectively

Nb of points = 8 STO 00

XEQ "TSP" >>>> L = 26.47818047 ---Execution time = 34s---
X<>Y 1.016

-The points have been permuted and we find in R01 thru R24:

x | 1 3 2 4 6 7 9 8
y | 1 5 7 8 9 6 4 2

-So, the suggested solution is 1-7-2-8-3-4-5-6

Note:

-If there are 23 points, the execution time is about 4m00s

2°) 3-Dimensional Problem

Data Registers: • R00 = n = Nb of points ( Registers R00 thru R3n are to be initialized before executing "TSP3" )

                                      • R01 = x₁     • R04 = x₂     ......................................    • R3n-2 = x_n
                                      • R02 = y₁     • R05 = y₂     ......................................    • R3n-1 = y_n
                                      • R03 = z₁     • R06 = z₂     ......................................    • R3n = z_n
Flags: /
Subroutines: /

01 LBL "TSP3"
02 RCL 00
03 2
04 -
05 3
06 *
07 E3
08 /
09 ISG X
10 STO M
11 LBL 01
12 RCL M
13 3.006
14 +
15 STO N
16 E99
17 STO O
18 LBL 02
19 RCL IND M
20 RCL IND N
21 -

22 X^2
23 ISG M
24 ISG N
25 RCL IND M
26 RCL IND N
27 -
28 X^2
29 +
30 ISG M
31 ISG N
32 RCL IND M
33 RCL IND N
34 -
35 X^2
36 +
37 RCL O
38 X<=Y?
39 GTO 03
40 X<>Y
41 STO O
42 RCL N

43 RCL M
44 3
45 +
46 RCL IND X
47 X<> IND Z
48 STO IND Y
49 CLX
50 SIGN
51 ST- Z
52 -
53 RCL IND X
54 X<> IND Z
55 STO IND Y
56 CLX
57 SIGN
58 ST- Z
59 -
60 RCL IND X
61 X<> IND Z
62 STO IND Y
63 LBL 03

64 2
65 ST- M
66 ISG N
67 GTO 02
68 ST+ M
69 ISG M
70 GTO 01
71 RCL 00
72 3
73 *
74 STO M
75 STO N
76 RCL IND X
77 RCL 03
78 -
79 X^2
80 DSE N
81 RCL IND N
82 RCL 02
83 -
84 X^2

85 +
86 DSE N
87 RCL IND N
88 RCL 01
89 -
90 X^2
91 +
92 SQRT
93 DSE N
94 LBL 04
95 RCL IND M
96 RCL IND N
97 -
98 X^2
99 DSE M
100 DSE N
101 RCL IND M
102 RCL IND N
103 -
104 X^2
105 +

106 DSE M
107 DSE N
108 RCL IND M
109 RCL IND N
110 -
111 X^2
112 +
113 SQRT
114 +
115 DSE M
116 DSE N
117 GTO 04
118 RCL 00
119 3
120 *
121 E3
122 /
123 ISG X
124 X<>Y
125 CLA
126 END

( 202 bytes / SIZE 3n+1 )

STACK	INPUTS	OUTPUTS
Y	/	1.3n
X	/	Length

Example: The coordinates of 8 points are:

    x | 1 2 10 7 9 8 3 4                                                      R01 R04 R07 R10 R13 R16 R19 R22
    y | 1 7   1   6 4 2 5 5       Store these 24 numbers into     R02 R05 R08 R11 R14 R17 R20 R23    respectively
    z | 1 5   4   8 7 1 2 6                                                       R03 R06 R09 R12 R15 R18 R21 R24

Nb of points = 8 STO 00

XEQ "TSP3" >>>> L = 33.23751462 ---Execution time = 50s---
X<>Y 1.024

-The points have been permuted and we find in R01 thru R24:

    x | 1 3 2 4 7 9 10 8
    y | 1 5 7 5 6 4   1   2
    z | 1 2 5 6 8 7   4   1

-So, the suggested solution is 1-7-2-8-4-5-3-6

Note:

-If there are 17 points, the execution time is about 3m25s

3°) Spherical Problem

Data Registers: • R00 = n = Nb of points ( Registers R00 thru R2n are to be initialized before executing "TSPS" )

• R01 = L₁ • R03 = L₂ ...................................... • R2n-1 = L_n L & b expressed in ° ' ''
• R02 = b₁ • R04 = b₂ ...................................... • R2n = b_n

Flags: /
Subroutines: /

01 LBL "TSPS"
02 DEG
03 RCL 00
04 2
05 -
06 ST+ X
07 E3
08 /
09 ISG X
10 STO M
11 LBL 01
12 RCL M
13 2.004
14 +
15 STO N
16 SIGN
17 STO O
18 LBL 02
19 RCL IND M
20 RCL IND N

21 ISG M
22 ISG N
23 RCL IND M
24 X<>Y
25 RCL IND N
26 XEQ 04
27 RCL O
28 X<=Y?
29 GTO 03
30 X<>Y
31 STO O
32 RCL N
33 RCL M
34 2
35 +
36 RCL IND X
37 X<> IND Z
38 STO IND Y
39 CLX
40 SIGN

41 ST- Z
42 -
43 RCL IND X
44 X<> IND Z
45 STO IND Y
46 CLX
47 LBL 03
48 SIGN
49 ST- M
50 ISG N
51 GTO 02
52 ST+ M
53 ISG M
54 GTO 01
55 GTO 05
56 LBL 04
57 HR
58 X<> T
59 HMS-
60 HR

61 2
62 /
63 SIN
64 X^2
65 RDN
66 HR
67 +
68 2
69 /
70 ST- Y
71 COS
72 X^2
73 ST* T
74 RDN
75 SIN
76 X^2
77 ST* Y
78 -
79 -
80 RTN

81 LBL 05
82 RCL 00
83 ST+ X
84 STO M
85 STO N
86 DSE N
87 RCL IND N
88 RCL IND Y
89 RCL 01
90 RCL 02
91 XEQ 04
92 SQRT
93 ASIN
94 STO O
95 DSE N
96 LBL 06
97 RCL IND M
98 RCL IND N
99 DSE M
100 DSE N
101 RCL IND M

102 RCL IND N
103 X<> T
104 XEQ 04
105 SQRT
106 ASIN
107 ST+ O
108 DSE M
109 DSE N
110 GTO 06
111 RCL 00
112 ST+ X
113 E3
114 /
115 ISG X
116 RCL O
117 ST+ X
118 D-R
119 6371
120 *
121 CLA
122 END

( 204 bytes / SIZE 2n+1 )

STACK	INPUTS	OUTPUTS
Y	/	1.2n
X	/	Length

Example: The coordinates of 16 "points" are:

Paris Bombay Canberra Glasgow Johannesburg CapeTown Madrid Moskow Ottawa Oslo MountPalomar Pulkovo Rio Sydney Washington Zikawei

L 2°20' 72°49' 149°00 -4°17' 28°01' 18°29' -3°41' 37°33' -75°43' 10°43' -116°52' 30°20' -43°13' 151°12' -77°04' 121°11'
b 48°50' 18°53' -35°19 55°52' -26°11' -33°56' 40°24' 55°42' 45°24' 59°54' 33°21' 53°46' -22°53' -33°52' 38°55' 31°11'

-Store these 32 numbers into R01 to R32

16 STO 00

XEQ "TSPS" >>>> L = 71589 km ---Execution time = 7m52s---
X<>Y 1.032

-The coordinates of these 16 points have been modified in R01 thru R32 which suggests the following journey:

Paris-Glasgow-Oslo-Pulkovo-Moskow-Madrid-Ottawa-Washington-MountPalomar-Rio-CapeTown-Johannesburg-Bombay-Zikawei-Sydney-Canberra

Notes:

-The length is calculated for the Earth, assuming the mean radius = 6371 km ( line 119 )
-In fact, it's not the shortest path: if you swap the first 2 towns, you get L = 65181 km

-So you can try to execute "TSPS" again after changing the order of the points.
-Of course V41 will give you the results much more quickly.

hp41programs

Traveling Salesman Problem for the HP-41