A space mission is scheduled to visit the five moons of several distant planets

Question

A space mission is scheduled to visit the five moons of several distant planets to collect rock samples and then return to Earth (E). The moons are labeled A, B, C D, and F, and the travel times (in years) are given in the weighted graph. 4.1 1.4 Complete parts (a) and (b). 2.5 3.4 2.7 7.3 5.3 5.8 (a) Find the nearest-neighbor tour starting with vertex E. Give the total travel time of this tour Fill in the nearest neighbor tour hat is the total travel time (in years) of the tour? years ter your answer in each of the answer boxes.

Explanation / Answer

The Neareast Neighbour algorithm steps are described in the following:
1) A vertex will be picked randomly as the current vertex
2) The lightest edge will be chosen that connect current
vertex to the nearest unvisited vertex V.
3) Our current vertex is vertex V.
4) Vertex V is marked as visited.
5) If all of the vertices in the domain are visited, then
terminate the procedure.
The output of the algorithm is the sequence of all visited
vertices. This implies a short tour but not an optimal one.

In our case Starting point is E and its nearest neighbour is A. Mark A as current vertex. Mark E Vistied.

Nearest neighbour of A is B. Mark B current vertex. Mark A as visited.

Nearest neighbour of B is C. Mark C current vertex. Mark B as visited.

Nearest neighbour of C is D. Mark D current vertex. Mark C as visited.

Nearest neighbour of D is F . Mark F current vertex. Mark D as visited.

The route is E -> A -> B -> C -> D ->F -> E

Total cost is 53+23+14+34+37+73=234

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.