Greetings,

Having problems with six questions and wondered if I could get some assistance (Discrete Math)

Heuristic Challenge Doing a brute force search (trying every path) is prohibitively difficult for finding a solution for a 7 point graph. Come up with an approach that will allow you to find a good low cost circuit (if not necessarily the best) 6. Select a "good" circuit in the the following graph and give the cost of traversing it The lowest cost path in the class gets 15 points Any score in the to 20% of paths will get 12 points B D E F G Any score in the top 50% of paths will get 10 points 0 12 24 21 17 Any valid circuit will earn 5 points B 12 10 14 30 20 This is weighted adjacenty matrix for the graph 32 10 10 you are looking to traverse. e. For simplicity sake D 24 14 5 0 22 31 4 the graph is non-directed E 9 30 12 22 0 12 24 You can use this information to draw a graph is you want to F 21 10 31 12 visualize the graph. See question 9 in project 2 for a refresher. G 17 20 16 24Objective - Explore Applications of Graph Theory and Combinatorics . Identify why certain problems are difcult to solve efciently - Explore the use of Heuristics Instructions Answer all numbered questions in the Document Introduction The traveling salesman problem is stated as \"Given a list of cities and the distances between each pair of cities. what is the shortest possible route that visits each city and returns to the origin city?\" Brute Force Search 1 . Write all possible circu'ts for the graph in the form Example: There will be 24 possible circuits to list 2. For each circuit, calculate the total distance traveled The total distance is the sum of each distance on the route 3. Identify the Optimal Path The optimal path is the one with the shortest distance Reflection 4. Why did the process of finding the optima! path using the above technique require so many steps? What would the process be like for nding the optimal path for larger graphs (10, 20. 100 nodes) 5. Describe method you codd use to reduce the number of calculations to find a good solution? A heuristic is a technique for finding an approximate solution based on discovery when finding a optimal one is too difcult