Improve Upper Bound with Shortcuts

A question is this type if and only if it asks the student to improve an existing upper bound by identifying and applying shortcuts to reduce the tour length below a specified value.

4 questions · Moderate -0.1

7.04d Travelling salesman lower bound: using minimum spanning tree

Sort by: Default | Easiest first | Hardest first

Edexcel D2 2013 June Q2

8 marks Standard +0.3

2. The table shows the least distances, in km, between six towns, A, B, C, D, E and F.

	A	B	C	D	E	F
A	-	122	217	137	109	82
B	122	-	110	130	128	204
C	217	110	-	204	238	135
D	137	130	204	-	98	211
E	109	128	238	98	-	113
F	82	204	135	211	113	-

Liz must visit each town at least once. She will start and finish at A and wishes to minimise the total distance she will travel.

Starting with the minimum spanning tree given in your answer book, use the shortcut method to find an upper bound below 810 km for Liz's route. You must state the shortcut(s) you use and the length of your upper bound.
(2)
Use the nearest neighbour algorithm, starting at A , to find another upper bound for the length of Liz's route.
Starting by deleting F , and all of its arcs, find a lower bound for the length of Liz's route.
Use your results to write down the smallest interval which you are confident contains the optimal length of the route.

Edexcel D1 2020 June Q3

7 marks Standard +0.3

3. The table below shows the least distances, in km, between six towns, A, B, C, D, E and F.

	A	B	C	D	E	F
A	-	57	76	59	72	65
B	57	-	67	80	66	76
C	76	67	-	71	83	80
D	59	80	71	-	77	78
E	72	66	83	77	-	69
F	65	76	80	78	69	-

Mei must visit each town at least once. She will start and finish at A and wishes her route to minimise the total distance she will travel.

Starting with the minimum spanning tree in the answer book, use the shortcut method to find an upper bound below 520 km for Mei's route. You must state the shortcut(s) you use and the length of your upper bound.
Use the nearest neighbour algorithm, starting at A , to find another upper bound for the length of Mei's route.
Starting by deleting E, and all of its arcs, find a lower bound for the length of Mei's route. Make your method clear.

Edexcel D1 2018 Specimen Q1

8 marks Moderate -0.8

The table shows the least distances, in km, between six towns, A, B, C, D, E and F.

	A	B	C	D	E	F
A	--	122	217	137	109	82
B	122	--	110	130	128	204
C	217	110	--	204	238	135
D	137	130	204	--	98	211
E	109	128	238	98	--	113
F	82	204	135	211	113	--

Liz must visit each town at least once. She will start and finish at A and wishes to minimise the total distance she will travel.

Starting with the minimum spanning tree given in your answer book, use the shortcut method to find an upper bound below 810 km for Liz's route. You must state the shortcut(s) you use and the length of your upper bound. \hfill [2]
Use the nearest neighbour algorithm, starting at A, to find another upper bound for the length of Liz's route. \hfill [2]
Starting by deleting F, and all of its arcs, find a lower bound for the length of Liz's route. \hfill [3]
Use your results to write down the smallest interval which you are confident contains the optimal length of the route. \hfill [1]

Edexcel D2 Q6

14 marks Moderate -0.3

The table below shows the distances, in km, between six towns \(A\), \(B\), \(C\), \(D\), \(E\) and \(F\).

	A	B	C	D	E	F
A	\(-\)	85	110	175	108	100
B	85	\(-\)	38	175	160	93
C	110	38	\(-\)	148	156	73
D	175	175	148	\(-\)	110	84
E	108	160	156	110	\(-\)	92
F	100	93	73	84	92	\(-\)

Starting from \(A\), use Prim's algorithm to find a minimum connector and draw the minimum spanning tree. You must make your method clear by stating the order in which the arcs are selected. [4]
1. Using your answer to part (a) obtain an initial upper bound for the solution of the travelling salesman problem. [2]
2. Use a short cut to reduce the upper bound to a value less than 680. [4]
Starting by deleting \(F\), find a lower bound for the solution of the travelling salesman problem. [4]

	A	B	C	D	E	F
A	-	122	217	137	109	82
B	122	-	110	130	128	204
C	217	110	-	204	238	135
D	137	130	204	-	98	211
E	109	128	238	98	-	113
F	82	204	135	211	113	-

	A	B	C	D	E	F
A	-	57	76	59	72	65
B	57	-	67	80	66	76
C	76	67	-	71	83	80
D	59	80	71	-	77	78
E	72	66	83	77	-	69
F	65	76	80	78	69	-

	A	B	C	D	E	F
A	--	122	217	137	109	82
B	122	--	110	130	128	204
C	217	110	--	204	238	135
D	137	130	204	--	98	211
E	109	128	238	98	--	113
F	82	204	135	211	113	--

	A	B	C	D	E	F
A	-	122	217	137	109	82
B	122	-	110	130	128	204
C	217	110	-	204	238	135
D	137	130	204	-	98	211
E	109	128	238	98	-	113
F	82	204	135	211	113	-

	A	B	C	D	E	F
A	-	57	76	59	72	65
B	57	-	67	80	66	76
C	76	67	-	71	83	80
D	59	80	71	-	77	78
E	72	66	83	77	-	69
F	65	76	80	78	69	-

	A	B	C	D	E	F
A	--	122	217	137	109	82
B	122	--	110	130	128	204
C	217	110	--	204	238	135
D	137	130	204	--	98	211
E	109	128	238	98	--	113
F	82	204	135	211	113	--

	A	B	C	D	E	F
A	-	122	217	137	109	82
B	122	-	110	130	128	204
C	217	110	-	204	238	135
D	137	130	204	-	98	211
E	109	128	238	98	-	113
F	82	204	135	211	113	-

	A	B	C	D	E	F
A	-	57	76	59	72	65
B	57	-	67	80	66	76
C	76	67	-	71	83	80
D	59	80	71	-	77	78
E	72	66	83	77	-	69
F	65	76	80	78	69	-

	A	B	C	D	E	F
A	--	122	217	137	109	82
B	122	--	110	130	128	204
C	217	110	--	204	238	135
D	137	130	204	--	98	211
E	109	128	238	98	--	113
F	82	204	135	211	113	--