# hp41programs

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 = x1     •  R03 = x2     ......................................    •  R2n-1 = xn
•  R02 = y1     •  R04 = y2     ......................................    •  R2n = yn

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 = x1     •  R04 = x2     ......................................    •  R3n-2 = xn
•  R02 = y1     •  R05 = y2     ......................................    •  R3n-1 = yn
•  R03 = z1     •  R06 = z2     ......................................    •  R3n = zn
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 = L1     •  R03 = L2     ......................................    •  R2n-1 = Ln         L & b expressed in ° ' ''
•  R02 = b1     •  R04 = b2     ......................................    •  R2n = bn

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: