Traveling Salesperson Problem using Bruteforce
Using the bruteforce method, create and show an algorithm on the matrix below by hand drawing a diagram with nodes showing all of the possible outcomes of th given matrix below. Please make your handwriting legible. Will uprate if the work follows the requirements. Thanks in advance
Exercise 1 (Traveling Salesperson Problem by Brute Force) Suppose we have a directed graph (like below) with n vertices labeled 1 through n, im- plemented using an n by n matrix where row j, column k contains the weight of the edge going from vertex j to vertex k, or a dash if there is no edge from j to k. The Traveling Salesperson Problem (TSP) is as follows: given a weight matrix as input, determine the cycle a path that starts at vertex 1, hits all the vertices exactly once, and ends up back at vertex 1that has smallest total weight of its edge. Note that the minimum weight cycle might be . Figure out how to use the brute force technique to solve an instance of this problem, and demonstrate your algorithm on the matrix below. Be sure to think about pruning, and what information should be kept in each node. To avoid me demanding that you fix your work, be sure that the nodes have enough information to allow construction of their child nodes, without any knowledge of where a node appears in the tree. Along the same lines, you must not have any information stored on the edges of the tree. 3 2 5 4 7 10 9 5 7 12 8 9 12 6 7 Exercise 1 (Traveling Salesperson Problem by Brute Force) Suppose we have a directed graph (like below) with n vertices labeled 1 through n, im- plemented using an n by n matrix where row j, column k contains the weight of the edge going from vertex j to vertex k, or a dash if there is no edge from j to k. The Traveling Salesperson Problem (TSP) is as follows: given a weight matrix as input, determine the cycle a path that starts at vertex 1, hits all the vertices exactly once, and ends up back at vertex 1that has smallest total weight of its edge. Note that the minimum weight cycle might be . Figure out how to use the brute force technique to solve an instance of this problem, and demonstrate your algorithm on the matrix below. Be sure to think about pruning, and what information should be kept in each node. To avoid me demanding that you fix your work, be sure that the nodes have enough information to allow construction of their child nodes, without any knowledge of where a node appears in the tree. Along the same lines, you must not have any information stored on the edges of the tree. 3 2 5 4 7 10 9 5 7 12 8 9 12 6 7
