Repetitive Nearest Neighbor And Cheapest Link Algorithms PDF

Preview

Summary

Explanation and Practice Examples about Repetitive Nearest Neighbor and Cheapest Link Algorithms. ...

Description

MATH 11008:

Repetitive Nearest Neighbor and Cheapest Link Algorithms Sections 6.7 & 6.8

• There is currently no algorithm for solving the traveling salesman problem that is both efficient and optimal. Also, no one has been able to prove that such an algorithm does not exist. • An approximate algorithm is an algorithm that produces solutions that are, most of the time, reasonably close to the optimal solution. We will now discuss two algorithms that are approximate but efficient algorithms. Repetitive Nearest Neighbor Algorithm: 1. Let X be any vertex. Apply the nearest neighbor algorithm using X as the starting vertex and calculate the total weight of the circuit obtained. 2. Repeat the process using each of the other vertices of the graph as the starting vertex. 3. Of the Hamilton circuits obtained, choose the one with least cost. If necessary, rewrite the tour so that it starts at the designating starting vertex. Example 1: For the weighted graph shown below, find the repetitive nearest-neighbor tour. Write the tour using A as the starting vertex. A

28

F

16 19

32

25

41

19 .7

17 27

B

E 20

23

30

24

19.5

C

18

D

MATH 11008: REPETITIVE NEAREST NEIGHBOR AND CHEAPEST LINK ALGORITHMS SECTIONS 6.7 & 6.8

2

Cheapest-Link Algorithm: 1. Pick the cheapest link (the edge with the smallest weight) available. (In the case of a tie, pick one at random.) Mark it. 2. Pick the next cheapest link available and mark it. 3. Continue picking the marking the cheapest unmarked link available that does not (a) close a circuit or (b) create three edges coming out of a single vertex. 4. Connect the last two vertices to close the circuit.

Example 2: Repeat Example 1, using the Cheapest-Link Algorithm. The graph from example 1 is below. Write the tour using A as the starting vertex. A

28

F

16 19

32

25

41

19 .7

17 27

B

E 20

23

30

24

19.5

C

18

D

MATH 11008: REPETITIVE NEAREST NEIGHBOR AND CHEAPEST LINK ALGORITHMS SECTIONS 6.7 & 6.8

3

Example 3: For the weighted graph shown below, find the cheapest-link tour. Write the tour using A as the starting point.

A

133

119

5

0

15

12

2

200

E

18

B

150

199

121 D 174

C...