- 60 Pts Consider The Traveling Salesperson Problem With Five Cities Which Are Represented By Vertices V1 V2 V3 V4 A 1 (129.99 KiB) Viewed 48 times
- 60 Pts Consider The Traveling Salesperson Problem With Five Cities Which Are Represented By Vertices V1 V2 V3 V4 A 2 (86.67 KiB) Viewed 48 times
NO CODE
(60 pts) Consider the traveling salesperson problem with five cities which are represented by vertices v1, v2, v3, v4, and v5 in a directed complete graph whose weights are given in the following adjacency matrix W: 3 14 v2 13 v3 3 7 9 v1 0 14 4 v1 v2 v3 14 0 ღო|N|ojთ v5 19 7 16 2 0 8 7 0 5 11 7 7 9 17 v5 18 4 Let's solve this problem by using the branch and bound algorithm with best-first search using the exact algorithm described during the lecture. Answer the following questions using the portion of the pruned sate space tree shown below. a) (10 pts) Show how the bound at the root node is computed b) (10pts) Compute the bound for node (1,2) representing all tours that begin with v1 → V2. Show your work. c) (10pts) Compute the bound for node (1,4,2) representing all tours that begin with vi → v4 → v2. Show your work. d) (10pts) Show the order in which the branch and bound algorithm with best-first search visits the nodes in the below pruned state space tree.
d) (10pts) Show the order in which the branch and bound algorithm with best-first search visits the nodes in the below pruned state space tree. e) (10pts) Explain why the node (1,5) was considered non-promissing. f) (10pts) Show the solution of this instance of the traveling salesperson problem by the above algorithm, as well as the total distance travelled by the tour. [1] Bound = 20 [1,2] Bound = ? [1,3] Bound =21 [1,4] Bound=29 (1,5] Bound=41 (1,3,2] Bound=21 (1,3,4] Bound=26 (1,3,5] Bound=38 (1,4,2] Bound=? (1,4,3] Bound=37 (1,4,5) Bound=29 (1,3,2,4] (1,3,2,4,5,1] ength=36 (1,3,2,5) (1,3,4,2]> (1,3,4,5) (1,3,2,5,4,1] (1,3,4,2,5,1) ([1,3,4,5,2,1) Length=30 Length=42 Length=33 (1,4,5,2] (1,4,5,3) (1,4,5,2,3,1) (1,4,5,3,2,1) Length=29 Length=47