Bruno Guerrieri: New Applications
http://www.maplesoft.com/applications/author.aspx?mid=265
en-us2014 Maplesoft, A Division of Waterloo Maple Inc.Maplesoft Document SystemTue, 02 Sep 2014 11:36:07 GMTTue, 02 Sep 2014 11:36:07 GMTNew applications published by Bruno Guerrierihttp://www.mapleprimes.com/images/mapleapps.gifBruno Guerrieri: New Applications
http://www.maplesoft.com/applications/author.aspx?mid=265
Traveling Salesman Problem
http://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 Guerrieri2-D Voronoi Diagrams with Byers' Method
http://www.maplesoft.com/applications/view.aspx?SID=4499&ref=Feed
Given N points (sites) in the plane (a 1x1 square) we would like to generate a tessellation of that domain by assigning every point in the plane to its nearest site. The process, as presented by Byers [1], is to select a particular site, call it C, and determine its Voronoi polygon. This is achieved by a) generating all segments from C to the remaining sites, b) considering all bisecting lines of each of these segments (in other words, the normal to the segment through the midpoint), c) determining all intersections points of these 'bisectors", d) eliminate those intersection points not in the 1x1 square, and e) determine which ones of the remaining intersection points are "closest" to C. Their convex hull is the Voronoi cell we are looking for. We then repeat the process for each of the remaining sites. We are mainly interested in the discovery process and, therefore, are not always concerned with efficiency or storage minimization.<img src="/view.aspx?si=4499//applications/images/app_image_blank_lg.jpg" alt="2-D Voronoi Diagrams with Byers' Method" align="left"/>Given N points (sites) in the plane (a 1x1 square) we would like to generate a tessellation of that domain by assigning every point in the plane to its nearest site. The process, as presented by Byers [1], is to select a particular site, call it C, and determine its Voronoi polygon. This is achieved by a) generating all segments from C to the remaining sites, b) considering all bisecting lines of each of these segments (in other words, the normal to the segment through the midpoint), c) determining all intersections points of these 'bisectors", d) eliminate those intersection points not in the 1x1 square, and e) determine which ones of the remaining intersection points are "closest" to C. Their convex hull is the Voronoi cell we are looking for. We then repeat the process for each of the remaining sites. We are mainly interested in the discovery process and, therefore, are not always concerned with efficiency or storage minimization.4499Mon, 26 Apr 2004 09:35:32 ZBruno GuerrieriBruno GuerrieriReconstruction of 2-D Images and CAT Scans
http://www.maplesoft.com/applications/view.aspx?SID=4273&ref=Feed
This is a Maple application centered around the article "How to resurrect a cat from its grin" that appeared in the Mathematical Recreations" section of Scientific American (Sept. 1990).<img src="/view.aspx?si=4273/cat.gif" alt="Reconstruction of 2-D Images and CAT Scans" align="left"/>This is a Maple application centered around the article "How to resurrect a cat from its grin" that appeared in the Mathematical Recreations" section of Scientific American (Sept. 1990).4273Mon, 13 May 2002 11:54:43 ZBruno GuerrieriBruno GuerrieriAn Example Of Round-Off Error
http://www.maplesoft.com/applications/view.aspx?SID=4271&ref=Feed
The following is in no way an original idea. I heard about it, many years ago, from my major professor, Dr. Christopher Hunter (Florida State University), and, at a later date, have come across essentially the same idea in "Computer Methods for Mathematical Computations" by G.E. Forsythe, M.A. Malcolm, C.B. Moller, Prentice-Hall (1977), page 16. The results you will be getting on your machine will, perhaps, be different from ours, due to different machine accuracy, but we hope that our presentation will remain consistent.
<img src="/view.aspx?si=4271//applications/images/app_image_blank_lg.jpg" alt="An Example Of Round-Off Error" align="left"/>The following is in no way an original idea. I heard about it, many years ago, from my major professor, Dr. Christopher Hunter (Florida State University), and, at a later date, have come across essentially the same idea in "Computer Methods for Mathematical Computations" by G.E. Forsythe, M.A. Malcolm, C.B. Moller, Prentice-Hall (1977), page 16. The results you will be getting on your machine will, perhaps, be different from ours, due to different machine accuracy, but we hope that our presentation will remain consistent.
4271Thu, 09 May 2002 15:24:43 ZBruno GuerrieriBruno Guerrieri