Question

Consider a TSP case with 9 cities to be visited (starting from D and returning to...

Consider a TSP case with 9 cities to be visited (starting from D and returning to D). Using the distance matrix is provided below, use the nearest neighborhood heuristic to find the minimum distance route.

Distances

D

1

2

3

4

5

6

7

8

D

0

61

42

22

50

45

32

57

30

1

61

0

21

62

80

91

32

76

82

2

42

21

0

41

61

71

20

71

67

3

22

62

41

0

28

30

41

78

51

4

50

80

61

28

0

22

67

106

76

5

45

91

71

30

22

0

71

100

64

6

32

32

20

41

67

71

0

51

50

7

57

76

71

78

106

100

51

0

41

8

30

82

67

51

76

64

50

41

0

Group of answer choices

a. D-3-4-5-8-7-6-1-2-D (D-3-4-2-1-6-8-7-5-D also accepted)

b. D-1-2-3-4-5-6-7-8-D

c. D-5-3-6-4-2-1-7-8-D

d. D-2-7-4-8-5-1-2-D

Homework Answers

Answer #1

SOLUTION:

Given that,

Consider a TSP case with 9 cities to be visited ( starting from D and returnig to D).

To find the minimum distance rout by using the nearest neighborhood heuristic:

DISTANCES:

S.NO From Node Un-visited nearest neighbor Distances
1 D 3 22
2 3 4 28
3 4 5 22
4 5 8 64
5 8 7 41
6 7 6 51
7 6 2 20
8 2 1 21
9 1 D 61
10 Total distances 330

So, the minimum rout using the nearest neighborhood algorith will be:

D-3-4-5-8-7-6-2-1-D .

--------------------------------------- O --------------------------------------

Please give a rating for this solution, THANK YOU.

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
This dataset contains consumer responses indicating the number of times they had to send their product...
This dataset contains consumer responses indicating the number of times they had to send their product for repair and their satisfaction with the repair process. Create a graph which can be used to visually demonstrate the relationship between the two columns of data. Ensure that the chart is professional with appropriate titles, axis labels, etc. Note any observations you see in your visualization (type these as sentences directly into an Excel cell(s)). Sample Satisfaction Rating Repair Requests 1 63% 13...
10 A) What is the best regression to forecast salary? 10 C) Are  all variables statistically significant?...
10 A) What is the best regression to forecast salary? 10 C) Are  all variables statistically significant? Did you drop any Final Math Pre req Hours Work experience 94 92 5 Y 74 90 3 Y 74 87 4 Y 76 84 3 N 66 87 2 N 80 49 4 Y 74 42 3 N 71 61 4 N 84 81 5 N 76 67 5 Y 95 93 4 N 78 56 5 N 71 54 3 Y 82...
Find regression line for the data X 0   1   2   3    4   5   6   7 8           ...
Find regression line for the data X 0   1   2   3    4   5   6   7 8            Y 11 21 31 41 51 61 71 81 91 X 0   2   4   6   8 10                            Y 12 15 17 18 20 22
Question 1: Table 1 shows the number of customers visited by a salesman over an 80-week...
Question 1: Table 1 shows the number of customers visited by a salesman over an 80-week period. Table 1: Customers Visited Over an 80-Week Period 68 64 75 82 68 60 62 88 76 93 73 79 88 73 60 93 71 59 85 75 61 65 75 87 74 62 95 78 63 72 66 78 82 75 94 77 69 74 68 60 96 78 89 61 75 95 60 79 83 71 79 62 67 97 78...
Using the accompanying Student Grades​ data, construct a scatter chart for midterm versus final exam grades...
Using the accompanying Student Grades​ data, construct a scatter chart for midterm versus final exam grades and add a linear trendline. What is the​ model? If a student scores 7878 on the​ midterm, what would you predict her grade on the final exam to​ be? Student Midterm Final Exam 1 75 64 2 85 91 3 80 68 4 88 83 5 76 60 6 67 80 7 78 74 8 95 94 9 67 61 10 93 87 11...
Student Grades Student Test Grade 1 76 62 2 84 90 3 79 68 4 88...
Student Grades Student Test Grade 1 76 62 2 84 90 3 79 68 4 88 84 5 76 58 6 66 79 7 75 73 8 94 93 9 66 65 10 92 86 11 80 53 12 87 83 13 86 49 14 63 72 15 92 87 16 75 89 17 69 81 18 92 94 19 79 78 20 60 71 21 68 84 22 71 74 23 61 74 24 68 54 25 76 97...
Kuya teaches a two-trimester course in Passionate Analysis Involving Numbers (PAIN). He would like to know...
Kuya teaches a two-trimester course in Passionate Analysis Involving Numbers (PAIN). He would like to know if these students improved their scores in their second trimester of the course. Is there a significant difference in PAIN scores? Apparently a couple students were too 'pained' and dropped out after the first trimester (too bad so sad). STUDENT TRIMESTER 1 TRIMESTER 2 1 69 78 2 76 79 3 70 81 4 71 5 75 57 6 61 55 7 67 59...
Refer to the Body Measurements Female Data Set and Body Measurements Male Data Set found in...
Refer to the Body Measurements Female Data Set and Body Measurements Male Data Set found in StatDisk (Elementary Stats 12th Edition, sets #1a and 1b) and use columns 5 for HDL. Use a .05 significance level to test the claim that men and women have the same mean HDL level (High-Density Lipoprotein) female 74 56 70 40 67 96 43 80 77 41 23 76 39 52 38 37 57 81 37 50 73 61 33 41 60 62 67...
Consider the following list of ages 71, 61, 78, 77, 81, 33, 80, 62, 74, 59,...
Consider the following list of ages 71, 61, 78, 77, 81, 33, 80, 62, 74, 59, 91, 76, 70, 98, 96, 94, 80, 59, 72, 82, 83, 74, 86, 77, 57, 75, 62, 74, 62, 79, 86 (a) Create a stemplot for the ages using each 10s value twice instead of once on the stem. (Enter numbers from smallest to largest separated by spaces. Enter NONE for stems with no values.) stem leaf 3 3 4 4 5 5 6...
Question 2: Write a C program that read 100 integers from the attached file (integers.txt) into...
Question 2: Write a C program that read 100 integers from the attached file (integers.txt) into an array and copy the integers from the array into a Binary Search Tree (BST). The program prints out the following: The number of comparisons made to search for a given integer in the BST And The number of comparisons made to search for the same integer in the array Question 3 Run the program developed in Question 2 ten times. The given values...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT