10 and 12 please Show the two children produced. 10. Consider the instance of th

Question

10 and 12 please

Show the two children produced. 10. Consider the instance of the TSP in Figure 10.12. Apply the Nearest Neighbor Algorithm starting with each of the vertices. Do any of them yield the shortest tour? 11. Form the union graph of the two tours shown in Figure 10.13, and apply the 12. Apply the Greedy Edge Algorithm to the instance of the TSP in Figure Figure 10.12 An instance of TSP Nearest Neighborhood Algorithm to the resultant graph starting at vertex v, 10.12. Does it yield a shortest tour? 71 Sto

Explanation / Answer

10.

Path from every vertices and choosing the one path with lesser weightage.

v1 -v4-v2-v3-v5

Gives:2+3+1+2=8

v2-v3-v5-v4-v1

Gives:1+2+3+2=8

v3-v5-v4-v1-v2

Gives:2+3+2+4=11

v4-v1-v2-v3-v5

Gives:2+4+1+2=9

v5-v3-v2-v4-v1

Gives:2+1+3+2=8

12.

Greedy algorithm using krushkals algorithm.

Basically as the name suggest greedy so here we will.choose the best among th choice .

Note:1. moving with path fr.vertex another vertex there must be no cycle formation or loop.

2.must visit.every vertice once

Here we can go.from.any vertixes

We choose v1 as the starting vertex so from.v1 to v4 as it cost less than v2

Now v2 has 3 option v2(3),v5(3),v3(6) we can choose any between v2 and v3 becahse there cost is same.

We choose v5 here.

Now we hav two optn v3(2) and v2(7), obviously.we will.take v3

Now from.v3 we can only.go.to v2(1) without making any loop

So we hav path v1-v4-v5-v3-v2

Which is 2+3+2+1=8

In this.question both tha method gives same.result but greedy algorithm not alwaysa gives optimal.result.

Thank you

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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