Other slides in this set

Slide 2

Preview of page 2

Here's a taster:

The travelling salesman problem
Finding a tour using the nearest neighbour algorithm
Example
3 B
A
4 2
2
5
5 5 C
4
6
E 6
D…read more

Slide 3

Preview of page 3

Here's a taster:

The travelling salesman problem
Finding a tour using the nearest neighbour algorithm
Example
3 B
A
4 2
2
5
5 5 C
4
6
E 6
D
Start from node A.
The
From
All nodes
nearest
D, the
C,
B, are
only
nearest
node
nownode
is
in D.
node
the
not
tour,
not
yet so
yet
in the
return
in the
tourto
tour
is
the
E.
isstarting
C.
B. point.
Length of tour = 2 + 4 + 2 + 5 + 5 = 18…read more

Slide 4

Preview of page 4

Here's a taster:

The travelling salesman problem
Finding a tour using the nearest neighbour algorithm
Example
3 B
A
4 2
2
5
5 5 C
4
6
E 6
D
Next, start from node B.
The nearest node is C. However, from C, A and D are equally near.
Choosing A gives the route A, D, E and then back to B.
Length of tour = 2 + 4 + 2 + 6 + 5 = 19…read more

Slide 5

Preview of page 5

Here's a taster:

The travelling salesman problem
Finding a tour using the nearest neighbour algorithm
Example
3 B
A
4 2
2
5
5 5 C
4
6
E 6
D
Next, start from node B.
The nearest node is C. However, from C, A and D are equally near.
Choosing D gives the route D, A, E and then back to B.
Length of tour = 2 + 4 + 2 + 5 + 5 = 18…read more

Slide 6

Preview of page 6

Here's a taster:

The travelling salesman problem
Finding a tour using the nearest neighbour algorithm
Example
3 B
A
4 2
2
5
5 5 C
4
6
E 6
D
Next, start from node C.
This gives the route C, B, A, D, E and then back to C.
Length of tour = 2 + 3 + 2 + 6 + 6 = 19…read more

Slide 7

Preview of page 7
Preview of page 7

Slide 8

Preview of page 8
Preview of page 8

Slide 9

Preview of page 9
Preview of page 9

Slide 10

Preview of page 10
Preview of page 10

Comments

No comments have yet been made

Similar Mathematics resources:

See all Mathematics resources »See all resources »