Graph Theory: New Applications
http://www.maplesoft.com/applications/category.aspx?cid=141
en-us2017 Maplesoft, A Division of Waterloo Maple Inc.Maplesoft Document SystemMon, 26 Jun 2017 19:08:16 GMTMon, 26 Jun 2017 19:08:16 GMTNew applications in the Graph Theory categoryhttp://www.mapleprimes.com/images/mapleapps.gifGraph Theory: New Applications
http://www.maplesoft.com/applications/category.aspx?cid=141
Mathematics for Chemistry
https://www.maplesoft.com/applications/view.aspx?SID=154267&ref=Feed
This interactive electronic textbook in the form of Maple worksheets comprises two parts.
<BR><BR>
Part I, mathematics for chemistry, is supposed to cover all mathematics that an instructor of chemistry might hope and expect that his students would learn, understand and be able to apply as a result of sufficient courses typically, but not exclusively, presented in departments of mathematics. Its nine chapters include (0) a summary and illustration of useful Maple commands, (1) arithmetic, algebra and elementary functions, (2) plotting, descriptive geometry, trigonometry, series, complex functions, (3) differential calculus of one variable, (4) integral calculus of one variable, (5) multivariate calculus, (6) linear algebra including matrix, vector, eigenvector, vector calculus, tensor, spreadsheet, (7) differential and integral equations, and (8) probability, distribution, treatment of laboratory data, linear and non-linear regression and optimization.
<BR><BR>
Part II presents mathematical topics typically taught within chemistry courses, including (9) chemical equilibrium, (10) group theory, (11) graph theory, (12a) introduction to quantum mechanics and quantum chemistry, (14) applications of Fourier transforms in chemistry including electron diffraction, x-ray diffraction, microwave spectra, infrared and Raman spectra and nuclear-magnetic-resonance spectra, and (18) dielectric and magnetic properties of chemical matter.
<BR><BR>
Other chapters are in preparation and will be released in due course.<img src="/view.aspx?si=154267/molecule.PNG" alt="Mathematics for Chemistry" align="left"/>This interactive electronic textbook in the form of Maple worksheets comprises two parts.
<BR><BR>
Part I, mathematics for chemistry, is supposed to cover all mathematics that an instructor of chemistry might hope and expect that his students would learn, understand and be able to apply as a result of sufficient courses typically, but not exclusively, presented in departments of mathematics. Its nine chapters include (0) a summary and illustration of useful Maple commands, (1) arithmetic, algebra and elementary functions, (2) plotting, descriptive geometry, trigonometry, series, complex functions, (3) differential calculus of one variable, (4) integral calculus of one variable, (5) multivariate calculus, (6) linear algebra including matrix, vector, eigenvector, vector calculus, tensor, spreadsheet, (7) differential and integral equations, and (8) probability, distribution, treatment of laboratory data, linear and non-linear regression and optimization.
<BR><BR>
Part II presents mathematical topics typically taught within chemistry courses, including (9) chemical equilibrium, (10) group theory, (11) graph theory, (12a) introduction to quantum mechanics and quantum chemistry, (14) applications of Fourier transforms in chemistry including electron diffraction, x-ray diffraction, microwave spectra, infrared and Raman spectra and nuclear-magnetic-resonance spectra, and (18) dielectric and magnetic properties of chemical matter.
<BR><BR>
Other chapters are in preparation and will be released in due course.154267Tue, 30 May 2017 04:00:00 ZProf. John OgilvieProf. John OgilviePrim’s Minimum Spanning Tree: Step by Step
https://www.maplesoft.com/applications/view.aspx?SID=153972&ref=Feed
Prim's MST Algorithm is a well known solution to the Minimum Spanning Tree (MST) problem, which consists in finding a subset of the edges of a connected weighed graph, such that it satisfies two properties: it maintains connectivity, and the sum of the weights of the edges in the set is minimized. This implementation shows the step-by-step progress of the algorithm.
<BR><BR>
This work is part of a social service project consisting in the implementation of several graph theory algorithms with step-by-step execution, intended to be used as a teaching aid in graph theory related courses. See also applications for <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153975">Kruskal’s Minimum Spanning Tree</A>, <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153974">Ford-Bellman’s Shortest Path</A>, and <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153973">Dijkstra’s Shortest Path</A>.<img src="/view.aspx?si=153972/prim.PNG" alt="Prim’s Minimum Spanning Tree: Step by Step" align="left"/>Prim's MST Algorithm is a well known solution to the Minimum Spanning Tree (MST) problem, which consists in finding a subset of the edges of a connected weighed graph, such that it satisfies two properties: it maintains connectivity, and the sum of the weights of the edges in the set is minimized. This implementation shows the step-by-step progress of the algorithm.
<BR><BR>
This work is part of a social service project consisting in the implementation of several graph theory algorithms with step-by-step execution, intended to be used as a teaching aid in graph theory related courses. See also applications for <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153975">Kruskal’s Minimum Spanning Tree</A>, <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153974">Ford-Bellman’s Shortest Path</A>, and <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153973">Dijkstra’s Shortest Path</A>.153972Tue, 16 Feb 2016 05:00:00 ZDaniel MichelDaniel MichelDijkstra's Shortest Path Algorithm: Step by Step
https://www.maplesoft.com/applications/view.aspx?SID=153973&ref=Feed
Dijkstra's Shortest Path Algorithm is a well known solution to the Shortest Paths problem, which consists in finding the shortest path (in terms of arc weights) from an initial vertex r to each other vertex in a directed weighted graph with nonnegative weights. This implementation shows the step-by-step progress of the algorithm.
<BR><BR>
This work is part of a social service project consisting in the implementation of several graph theory algorithms with step-by-step execution, intended to be used as a teaching aid in graph theory related courses. See also applications for <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153972">Prim’s Minimum Spanning Tree</A>, <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153974">Ford-Bellman’s Shortest Path</A>, and <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153975">Kruskal’s Minimum Spanning Tree</A>.<img src="/view.aspx?si=153973/dijkstra.PNG" alt="Dijkstra's Shortest Path Algorithm: Step by Step" align="left"/>Dijkstra's Shortest Path Algorithm is a well known solution to the Shortest Paths problem, which consists in finding the shortest path (in terms of arc weights) from an initial vertex r to each other vertex in a directed weighted graph with nonnegative weights. This implementation shows the step-by-step progress of the algorithm.
<BR><BR>
This work is part of a social service project consisting in the implementation of several graph theory algorithms with step-by-step execution, intended to be used as a teaching aid in graph theory related courses. See also applications for <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153972">Prim’s Minimum Spanning Tree</A>, <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153974">Ford-Bellman’s Shortest Path</A>, and <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153975">Kruskal’s Minimum Spanning Tree</A>.153973Tue, 16 Feb 2016 05:00:00 ZFernando MichelFernando MichelFord-Bellman’s Shortest Path Algorithm: Step by Step
https://www.maplesoft.com/applications/view.aspx?SID=153974&ref=Feed
The Ford-Bellman Shortest Path Algorithm is a well known solution to the Shortest Paths problem, which consists in finding the shortest path (in terms of arc weights) from an initial vertex r to each other vertex in a directed weighted graph. This implementation shows the step-by-step progress of the algorithm.
<BR><BR>
This work is part of a social service project consisting in the implementation of several graph theory algorithms with step-by-step execution, intended to be used as a teaching aid in graph theory related courses. See also applications for <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153975">Kruskal’s Minimum Spanning Tree</A>, <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153972">Prim’s Minimum Spanning Tree</A>, and <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153973">Dijkstra’s Shortest Path</A>.<img src="/view.aspx?si=153974/FordBellman.PNG" alt="Ford-Bellman’s Shortest Path Algorithm: Step by Step" align="left"/>The Ford-Bellman Shortest Path Algorithm is a well known solution to the Shortest Paths problem, which consists in finding the shortest path (in terms of arc weights) from an initial vertex r to each other vertex in a directed weighted graph. This implementation shows the step-by-step progress of the algorithm.
<BR><BR>
This work is part of a social service project consisting in the implementation of several graph theory algorithms with step-by-step execution, intended to be used as a teaching aid in graph theory related courses. See also applications for <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153975">Kruskal’s Minimum Spanning Tree</A>, <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153972">Prim’s Minimum Spanning Tree</A>, and <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153973">Dijkstra’s Shortest Path</A>.153974Tue, 16 Feb 2016 05:00:00 ZFernando MichelFernando MichelKruskal's Minimum Spanning Tree: Step by Step
https://www.maplesoft.com/applications/view.aspx?SID=153975&ref=Feed
Kruskal's MST Algorithm is a well known solution to the Minimum Spanning Tree (MST) problem, which consists in finding a subset of the edges of a connected weighed graph, such that it satisfies two properties: it maintains connectivity, and the sum of the weights of the edges in the set is minimized. This implementation shows the step-by-step progress of the algorithm.
<BR><BR>
This work is part of a social service project consisting in the implementation of several graph theory algorithms with step-by-step execution, intended to be used as a teaching aid in graph theory related courses. See also applications for <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153972">Prim’s Minimum Spanning Tree</A>, <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153974">Ford-Bellman’s Shortest Path</A>, and <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153973">Dijkstra’s Shortest Path</A>.<img src="/applications/images/app_image_blank_lg.jpg" alt="Kruskal's Minimum Spanning Tree: Step by Step" align="left"/>Kruskal's MST Algorithm is a well known solution to the Minimum Spanning Tree (MST) problem, which consists in finding a subset of the edges of a connected weighed graph, such that it satisfies two properties: it maintains connectivity, and the sum of the weights of the edges in the set is minimized. This implementation shows the step-by-step progress of the algorithm.
<BR><BR>
This work is part of a social service project consisting in the implementation of several graph theory algorithms with step-by-step execution, intended to be used as a teaching aid in graph theory related courses. See also applications for <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153972">Prim’s Minimum Spanning Tree</A>, <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153974">Ford-Bellman’s Shortest Path</A>, and <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153973">Dijkstra’s Shortest Path</A>.153975Tue, 16 Feb 2016 05:00:00 ZDaniel MichelDaniel MichelKnight's Tour
https://www.maplesoft.com/applications/view.aspx?SID=153842&ref=Feed
A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once.
This application presents the implementation of this task in Maple.<img src="/view.aspx?si=153842/26f19bd457ac566083dec1b86db8b91b.gif" alt="Knight's Tour" align="left"/>A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once.
This application presents the implementation of this task in Maple.153842Thu, 13 Aug 2015 04:00:00 ZYury ZavarovskyYury ZavarovskyOptimize the Flight Path of a Pan-US Delivery Drone
https://www.maplesoft.com/applications/view.aspx?SID=153536&ref=Feed
<p>You run a pan-US drone delivery service for a popular online retailer. You're given a list of zip codes across the US at which you need to drop off parcels, and want to optimize its journey so it travels the shortest distance.</p>
<p>This application extracts the latitude and longitude of those zip codes from an SQLlite database (the application includes the database, which cross-references US zip codes against their latitude, longitude, city and state). The application then performs a traveling salesman optimization and plots the shortest path on a map of the US.</p>
<p>This application uses background plot images, and SQLLite integration, two new features introduced in Maple 18.</p><img src="/view.aspx?si=153536/pan-us_drone.jpg" alt="Optimize the Flight Path of a Pan-US Delivery Drone" align="left"/><p>You run a pan-US drone delivery service for a popular online retailer. You're given a list of zip codes across the US at which you need to drop off parcels, and want to optimize its journey so it travels the shortest distance.</p>
<p>This application extracts the latitude and longitude of those zip codes from an SQLlite database (the application includes the database, which cross-references US zip codes against their latitude, longitude, city and state). The application then performs a traveling salesman optimization and plots the shortest path on a map of the US.</p>
<p>This application uses background plot images, and SQLLite integration, two new features introduced in Maple 18.</p>153536Mon, 31 Mar 2014 04:00:00 ZSamir KhanSamir KhanInternet Page Ranking Algorithms
https://www.maplesoft.com/applications/view.aspx?SID=153532&ref=Feed
In this guest article in the Tips and Techniques series, Dr. Michael Monagan explains how internet pages are ranked.<img src="/view.aspx?si=153532/thumb.jpg" alt="Internet Page Ranking Algorithms" align="left"/>In this guest article in the Tips and Techniques series, Dr. Michael Monagan explains how internet pages are ranked.153532Thu, 20 Mar 2014 04:00:00 ZProf. Michael MonaganProf. Michael MonaganClassroom Tips and Techniques: Bivariate Limits - Then and Now
https://www.maplesoft.com/applications/view.aspx?SID=145979&ref=Feed
An introductory overview of the functionalities in Maple's GraphTheory package.<img src="/view.aspx?si=145979/thumb.jpg" alt="Classroom Tips and Techniques: Bivariate Limits - Then and Now" align="left"/>An introductory overview of the functionalities in Maple's GraphTheory package.145979Wed, 17 Apr 2013 04:00:00 ZDr. Robert LopezDr. Robert LopezSimulating the Spread of an Infection
https://www.maplesoft.com/applications/view.aspx?SID=144175&ref=Feed
<p>In the problem below I take advantage of Maple's Graph Theory package to simulate how an infection might spread throughout a small community of 15 individuals.</p>
<p>This is a computer simulation project rather than a biology project! For example, the infection may not be a biological infection at all. The 15 vertices could represent 15 different computers, and the "infection" that spreads could be interpreted as a computer virus rather than a biological virus.</p><img src="/view.aspx?si=144175/siminfection_thumb.png" alt="Simulating the Spread of an Infection" align="left"/><p>In the problem below I take advantage of Maple's Graph Theory package to simulate how an infection might spread throughout a small community of 15 individuals.</p>
<p>This is a computer simulation project rather than a biology project! For example, the infection may not be a biological infection at all. The 15 vertices could represent 15 different computers, and the "infection" that spreads could be interpreted as a computer virus rather than a biological virus.</p>144175Mon, 04 Mar 2013 05:00:00 ZDouglas LewitDouglas LewitClassroom Tips and Techniques: Introduction to Maple's GraphTheory Package
https://www.maplesoft.com/applications/view.aspx?SID=142357&ref=Feed
An introductory overview of the functionality in Maple's GraphTheory package.<img src="/view.aspx?si=142357/thumb.jpg" alt="Classroom Tips and Techniques: Introduction to Maple's GraphTheory Package" align="left"/>An introductory overview of the functionality in Maple's GraphTheory package.142357Thu, 17 Jan 2013 05:00:00 ZProf. Michael MonaganProf. Michael MonaganGraph Theory Editor
https://www.maplesoft.com/applications/view.aspx?SID=141905&ref=Feed
<p>A component for editing Maple Graphs, along with tools for visualization and for import/export from GraphML.</p><img src="/view.aspx?si=141905/GraphEditor.jpg" alt="Graph Theory Editor" align="left"/><p>A component for editing Maple Graphs, along with tools for visualization and for import/export from GraphML.</p>141905Sat, 29 Dec 2012 05:00:00 ZJeff KnisleyJeff KnisleyBipartite Degree Sequences
https://www.maplesoft.com/applications/view.aspx?SID=135974&ref=Feed
<p>Given the degree sequence of one vertex set of a bipartite graph, this application allows the user to obtain information about the degree sequence of the other vertex set. Tools for generating all of the possible degree sequences of the unknown set are included. Without generating these degree sequences, we may also place bounds on any given position in the unknown degree sequence; procedures for bounding any given position in the unknown degree sequence, including the median, are given.</p><img src="/view.aspx?si=135974/135974_thumb.jpg" alt="Bipartite Degree Sequences" align="left"/><p>Given the degree sequence of one vertex set of a bipartite graph, this application allows the user to obtain information about the degree sequence of the other vertex set. Tools for generating all of the possible degree sequences of the unknown set are included. Without generating these degree sequences, we may also place bounds on any given position in the unknown degree sequence; procedures for bounding any given position in the unknown degree sequence, including the median, are given.</p>135974Fri, 20 Jul 2012 04:00:00 ZSamuel PineSamuel PineHollywood Math
https://www.maplesoft.com/applications/view.aspx?SID=6611&ref=Feed
Over its storied and intriguing history, Hollywood has entertained us with many mathematical moments in film. John Nash in “A Beautiful Mind,” the brilliant janitor in “Good Will Hunting,” the number theory genius in “Pi,” and even Abbott and Costello are just a few of the Hollywood “mathematicians” that come to mind. This document highlights just a few examples of mathematics in film, and how Maple can work with them.<img src="/view.aspx?si=6611/thumb.jpg" alt="Hollywood Math" align="left"/>Over its storied and intriguing history, Hollywood has entertained us with many mathematical moments in film. John Nash in “A Beautiful Mind,” the brilliant janitor in “Good Will Hunting,” the number theory genius in “Pi,” and even Abbott and Costello are just a few of the Hollywood “mathematicians” that come to mind. This document highlights just a few examples of mathematics in film, and how Maple can work with them.6611Fri, 23 Sep 2011 04:00:00 ZMaplesoftMaplesoftThe Traveling Salesman’s US Roadtrip
https://www.maplesoft.com/applications/view.aspx?SID=89020&ref=Feed
<p class="MsoNormal">This application</p>
<ul>
<li>plots the location of user-specified US zip codes on a map by querying a database of longitudes and latitudes</li>
<li>calculates the optimal path, or Hamiltonian cycle, for the Traveling Salesman Problem with Maple graph theory functionality,</li>
<li>and draws an undirected graph highlighting the Hamiltonian cycle.</li>
</ul>
<p class="MsoNormal">You will need to install PostreSQL to query the zip code database provided with this application.</p><img src="/view.aspx?si=89020/0\map.png" alt="The Traveling Salesman’s US Roadtrip" align="left"/><p class="MsoNormal">This application</p>
<ul>
<li>plots the location of user-specified US zip codes on a map by querying a database of longitudes and latitudes</li>
<li>calculates the optimal path, or Hamiltonian cycle, for the Traveling Salesman Problem with Maple graph theory functionality,</li>
<li>and draws an undirected graph highlighting the Hamiltonian cycle.</li>
</ul>
<p class="MsoNormal">You will need to install PostreSQL to query the zip code database provided with this application.</p>89020Fri, 04 Jun 2010 04:00:00 ZMaplesoftMaplesoftClassroom Tips and Techniques: A Note on Parametric Plotting
https://www.maplesoft.com/applications/view.aspx?SID=87605&ref=Feed
<p>Under suitable conditions, the equations f(x, y, t) = g(x, y, t) and g(x, y, t) = 0 define the curve x = x(t), y = y(t) parametrically. If the algebra permits an explicit solution, the resulting curve can be drawn with Maple's basic parametric plotting functionality. However, when the algebra is recalcitrant, the equations must be solved numerically for a sequence of points, or converted to differential equations that are solved numerically. All three of these alternatives are explored in this month's article.</p><img src="/view.aspx?si=87605/thumb.jpg" alt="Classroom Tips and Techniques: A Note on Parametric Plotting" align="left"/><p>Under suitable conditions, the equations f(x, y, t) = g(x, y, t) and g(x, y, t) = 0 define the curve x = x(t), y = y(t) parametrically. If the algebra permits an explicit solution, the resulting curve can be drawn with Maple's basic parametric plotting functionality. However, when the algebra is recalcitrant, the equations must be solved numerically for a sequence of points, or converted to differential equations that are solved numerically. All three of these alternatives are explored in this month's article.</p>87605Wed, 05 May 2010 04:00:00 ZDr. Robert LopezDr. Robert LopezSecret Santa Selection
https://www.maplesoft.com/applications/view.aspx?SID=34985&ref=Feed
<p>Every year my extended family does a "secret santa" gift exchange. Each person draws another person at random and then gets a gift for them. At first, none of my siblings were married, and so the draw was completely random. Then, as people got married, we added the restriction that spouses should not draw each others names. This restriction meant that we moved from using slips of paper on a hat to using a simple computer program to choose names.</p><img src="/view.aspx?si=34985/thumb.jpg" alt="Secret Santa Selection" align="left"/><p>Every year my extended family does a "secret santa" gift exchange. Each person draws another person at random and then gets a gift for them. At first, none of my siblings were married, and so the draw was completely random. Then, as people got married, we added the restriction that spouses should not draw each others names. This restriction meant that we moved from using slips of paper on a hat to using a simple computer program to choose names.</p>34985Thu, 17 Dec 2009 05:00:00 ZMaplesoftMaplesoftClassroom Tips and Techniques: Plotting a Slice of a Vector Field
https://www.maplesoft.com/applications/view.aspx?SID=19202&ref=Feed
This month's article answers a user's question about plotting a "slice" of a vector field, and superimposing this graph on a density plot of the underlying scalar field. The "slice" of the vector field is a graph of the field arrows emanating from a coordinate plane.<img src="/view.aspx?si=19202/thumb.png" alt="Classroom Tips and Techniques: Plotting a Slice of a Vector Field" align="left"/>This month's article answers a user's question about plotting a "slice" of a vector field, and superimposing this graph on a density plot of the underlying scalar field. The "slice" of the vector field is a graph of the field arrows emanating from a coordinate plane.19202Fri, 06 Mar 2009 00:00:00 ZDr. Robert LopezDr. Robert LopezOptions with Foreign Exchange Adjustment
https://www.maplesoft.com/applications/view.aspx?SID=6874&ref=Feed
The document presents the methods used by market practitioners to adjust the financial instruments processes and options valuations when payoffs are converted into different currency. Foreign exchange adjustment in the financial options universe brings in additional stochastic factor that extends the traditional univariate space into bi-variate or even multi-variate setting. We show that key tool to handle this scenario is an appropriate change of probability measure. In this context we also discuss the essence of the Siegel Paradox and show the way to resolve it.<img src="/view.aspx?si=6874/Quanto Options_95.gif" alt="Options with Foreign Exchange Adjustment" align="left"/>The document presents the methods used by market practitioners to adjust the financial instruments processes and options valuations when payoffs are converted into different currency. Foreign exchange adjustment in the financial options universe brings in additional stochastic factor that extends the traditional univariate space into bi-variate or even multi-variate setting. We show that key tool to handle this scenario is an appropriate change of probability measure. In this context we also discuss the essence of the Siegel Paradox and show the way to resolve it.6874Mon, 10 Nov 2008 00:00:00 ZIgor HlivkaIgor HlivkaTraveling Salesman Problem
https://www.maplesoft.com/applications/view.aspx?SID=6873&ref=Feed
The Traveling Salesman Problem (TSP) is a fascinating optimization problem in which a salesman wishes to visit each of N cities exactly once and return to the city of departure, attempting to minimize the overall distance traveled. For the symmetric problem where distance (cost) from city A to city B is the same as from B to A, the number of possible paths to consider is given by (N-1)!/2. The exhaustive search for the shortest tour becomes very quickly impossible to conduct. Why? Because, assuming that your computer can evaluate the length of a billion tours per second, calculations would last 40 years in the case of twenty cities and would jump to 800 years if you added one city to the tour [1]. These numbers give meaning to the expression "combinatorial explosion". Consequently, we must settle for an approximate solutions, provided we can compute them efficiently. In this worksheet, we will compare two approximation algorithms, a simple-minded one (nearest neighbor) and one of the best (Lin-Kernighan 2-opt).<img src="/view.aspx?si=6873/TSgif.gif" alt="Traveling Salesman Problem" align="left"/>The Traveling Salesman Problem (TSP) is a fascinating optimization problem in which a salesman wishes to visit each of N cities exactly once and return to the city of departure, attempting to minimize the overall distance traveled. For the symmetric problem where distance (cost) from city A to city B is the same as from B to A, the number of possible paths to consider is given by (N-1)!/2. The exhaustive search for the shortest tour becomes very quickly impossible to conduct. Why? Because, assuming that your computer can evaluate the length of a billion tours per second, calculations would last 40 years in the case of twenty cities and would jump to 800 years if you added one city to the tour [1]. These numbers give meaning to the expression "combinatorial explosion". Consequently, we must settle for an approximate solutions, provided we can compute them efficiently. In this worksheet, we will compare two approximation algorithms, a simple-minded one (nearest neighbor) and one of the best (Lin-Kernighan 2-opt).6873Mon, 10 Nov 2008 00:00:00 ZBruno GuerrieriBruno Guerrieri