logging in or signing up tsp bellidharmaraj Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 203 Category: Entertainment License: All Rights Reserved Like it (0) Dislike it (0) Added: September 18, 2010 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript Slide 1: Solving the Traveling Salesman Problem Outline : Outline Traveling Salesman Problem (TSP) Applications Simple TSP Instance : Simple TSP Instance The Traveling Salesman Problem : The Traveling Salesman Problem Informally: The problem of finding the shortest tour through a set of cities starting at some city and going through all other cities once and only once, returning to the starting city Formally: Finding the shortest Hamiltonian path in a fully-connected graph Crash Course in Graph Theory : Crash Course in Graph Theory A graph is defined as nodes N connected by edges E Graph on the right is fully connected a,b,c,d,e – nodes N (a,b),(b,c),... – edges E a,c,d,b,e – Hamiltonian Circuit How hard is the TSP? : How hard is the TSP? 3 cities – 3! = 6 4 cities – 4! = 24 5 cities – 5! = 120 6 cities – 6! = 720 7 cities – 7! = 5040 … 16 cities – 16! = 20922789888000 Ways of Solving the TSP : Ways of Solving the TSP Exact methods – solve via exhaustive enumeration of solution and their evaluation (not a good idea) Approximate methods - iterative methods start with a “good” solution and try to improve it over the course of a specific number of steps Optimization Terminology : Optimization Terminology Solution space 6 cities – 6! = 720 7 cities – 7! = 5040 Exploration Making choices contrary to previous experience in order to explore new tours Exploitation Making choices considering previous experience in order to find tours close to the ones we already have TSP Applications : TSP Applications Routing of trucks for parcel pickup Scheduling of service calls Drilling holes in a circuit board to minimize total drilling time and maximize output … Summary : Summary Traveling Salesman Problem A problem in theoretical computer science which is very hard to solve A number of real-world problems can be formalized as TSP problems You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
tsp bellidharmaraj Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 203 Category: Entertainment License: All Rights Reserved Like it (0) Dislike it (0) Added: September 18, 2010 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript Slide 1: Solving the Traveling Salesman Problem Outline : Outline Traveling Salesman Problem (TSP) Applications Simple TSP Instance : Simple TSP Instance The Traveling Salesman Problem : The Traveling Salesman Problem Informally: The problem of finding the shortest tour through a set of cities starting at some city and going through all other cities once and only once, returning to the starting city Formally: Finding the shortest Hamiltonian path in a fully-connected graph Crash Course in Graph Theory : Crash Course in Graph Theory A graph is defined as nodes N connected by edges E Graph on the right is fully connected a,b,c,d,e – nodes N (a,b),(b,c),... – edges E a,c,d,b,e – Hamiltonian Circuit How hard is the TSP? : How hard is the TSP? 3 cities – 3! = 6 4 cities – 4! = 24 5 cities – 5! = 120 6 cities – 6! = 720 7 cities – 7! = 5040 … 16 cities – 16! = 20922789888000 Ways of Solving the TSP : Ways of Solving the TSP Exact methods – solve via exhaustive enumeration of solution and their evaluation (not a good idea) Approximate methods - iterative methods start with a “good” solution and try to improve it over the course of a specific number of steps Optimization Terminology : Optimization Terminology Solution space 6 cities – 6! = 720 7 cities – 7! = 5040 Exploration Making choices contrary to previous experience in order to explore new tours Exploitation Making choices considering previous experience in order to find tours close to the ones we already have TSP Applications : TSP Applications Routing of trucks for parcel pickup Scheduling of service calls Drilling holes in a circuit board to minimize total drilling time and maximize output … Summary : Summary Traveling Salesman Problem A problem in theoretical computer science which is very hard to solve A number of real-world problems can be formalized as TSP problems