Solve a real-world optimization problem using graph theory.
Part I: Complete the following steps:
- Select a real-world optimization problem that is an example of the Traveling Salesman Problem (TSP).
- Create a graph modeling the real-world scenario corresponding to the problem. Use weights to represent the
variable that you are optimizing. - Find an optimal solution for the problem using the concepts studied in this module.
Part II: Based on your work in Part I, discuss the following: - Discuss your rationale for your choice of the real-world optimization problem. How were you able to identify
that it was an example of the TSP? Why is this example relevant? - Describe how you created the graph modeling the real-world scenario corresponding to the problem.
- Determine if the graph is complete. If so, use your graph to describe the formula for computing the number
of Hamilton circuits. - Explain in detail how you solved the problem.
- Describe a method for finding a non-optimal solution to the problem.
- Consider another variable that could be optimized in the problem. How would your answers to Part I be
affected by this change? - Discuss the advantages of using graph theory to solve this problem.