# Travelling Salesperson (Decision Maths)

Visual Powerpoint to explain the Travelling Salesperson problem and the nearest neighbour algorithm.

- Created by: Jackarias
- Created on: 01-06-10 10:16

## Slides in this set

### Slide 1

The travelling salesman problem

Finding a tour using the nearest neighbour algorithm

The Nearest Neighbour algorithm:

· Choose an arbitrary starting node.

· Choose the smallest arc from this node to a node not yet in

the tour.

· Repeat until all nodes are in the tour. Then add an arc back to

the starting node.…read more

### Slide 2

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

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

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

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

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

### Slide 8

### Slide 9

### Slide 10

## Related discussions on The Student Room

- OCR D1 Decision Revision thread »
- AQA AS Mathematics (Old Spec) - Decision 1 MD01 - 22 June ... »
- AQA AS Mathematics MD01 Decision 1 ? Tuesday 16th June ... »
- AQA Mathematics MD01 Decision 1 ? Friday 24th June [Exam ... »
- Current Year 12 Thread Mark I (2014/15) »
- The "Is this university/course good enough for banking ... »
- Optometry Students 2015 »
- OCR (non mei) D1 Wednesday 15th June 2016 »
- THE curly-wurly, super duper, mega AWESOME current Year ... »
- KPMG Audit School Leavers' 2014 »

## Similar Mathematics resources:

# Travelling Salesperson (Decision Maths)

Visual Powerpoint to explain the Travelling Salesperson problem and the nearest neighbour algorithm.

- Created by: Jackarias
- Created on: 01-06-10 10:16

## Slides in this set

### Slide 1

The travelling salesman problem

Finding a tour using the nearest neighbour algorithm

The Nearest Neighbour algorithm:

· Choose an arbitrary starting node.

· Choose the smallest arc from this node to a node not yet in

the tour.

· Repeat until all nodes are in the tour. Then add an arc back to

the starting node.…read more

### Slide 2

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

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

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

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

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

### Slide 8

### Slide 9

### Slide 10

## Comments

No comments have yet been made

## Similar Mathematics resources:

## Related discussions on The Student Room

- OCR D1 Decision Revision thread »
- AQA AS Mathematics (Old Spec) - Decision 1 MD01 - 22 June ... »
- AQA AS Mathematics MD01 Decision 1 ? Tuesday 16th June ... »
- AQA Mathematics MD01 Decision 1 ? Friday 24th June [Exam ... »
- Current Year 12 Thread Mark I (2014/15) »
- The "Is this university/course good enough for banking ... »
- Optometry Students 2015 »
- OCR (non mei) D1 Wednesday 15th June 2016 »
- THE curly-wurly, super duper, mega AWESOME current Year ... »
- KPMG Audit School Leavers' 2014 »

## Comments

No comments have yet been made