📄 http:^^www.cs.washington.edu^education^courses^521^winter96^project^project.html
字号:
Date: Tue, 10 Dec 1996 14:44:06 GMTServer: NCSA/1.4.2Content-type: text/html<HTML><head><title>CSE 521, Project</title></head><Body><P><h1>The Traveling Tourist Problem</h1><pre></pre>It is summer vacation, and you have purchased a Greyhound Bus passallowing you unlimited travel. Can you visit every city in the UnitedStates before your vacation ends? This is the Traveling tourist problem.<p>The CSE 521 course project is to implement algorithms for theTraveling Tourist Problem, and test them out on various data sets.The <!WA0><a href=http://www.cs.washington.edu/education/courses/521/winter96/project/fastest.html> Speedy Tourist Page </a> keeps track of thebest tours found on each of the problem instances in the project dataset. The <!WA1><a href=http://www.cs.washington.edu/education/courses/521/winter96/project/challenge.html>Challenge Page </a> gives a fewspecific challenges, and <!WA2><a href=http://www.cs.washington.edu/education/courses/521/winter96/project/lower.html>Lower bound page</a> givesthe best known lower bounds. Last update: 1/24/96.Eric Anderson has developed an <!WA3><a href="http://www.cs.washington.edu/homes/eric/java/TravellingTourist.html">applet</a> to animate tours.<p>The Traveling Tourist Problem can be viewed as a politically correctversion of the Traveling Salesman Problem, where travel isrestricted to public transportation. The TTP is easily shown to beNP-complete. An instanceof the Traveling TouristProblem is given by providing a schedule, which lists the departuretime each bus. The schedules are periodic, so it is only necessary togive a single day's schedule. The goal is to find aminimum duration tour which visits every city, and gets back to theoriginal city. A tour is allowed to visit the same city multipletimes. Since the problem is NP-complete, it is unlikely that you canfind an algorithm that efficiently solves large instances. So it is natural to look for approximation algorithms, which find good (butmaybe not optimal tours). Another option is to implement anexponential algorithm, and use it to solve small instances of theproblems. <p>In this project, you should investigate both approaches for theTraveling tourist problem. Try to come up with good approximations,and also implement branch and bound to solve smaller instancesexactly. There is a lot of literature on the Traveling salesmanproblem, so that suggests a number of approaches. However, there aresignificant differences between the two problems, so it will benecessary to invent new algorithms.<p>This project is modelled after various DIMACS Challenges, where researchers were invited to implement algorithms to solve specific problems. Animportant aspect of the DIMACS Challenges was a publically availableset of problem instances which made it possible to directly compareresults. In this challenge, the problem is to do as well as possibleon an NP-complete problem, so the two competitions are to come up withas good approximations on large instances, and to solve smallerinstances exactly with a branch and bound algorithm. As far as Iknow, this isn't a well studied problem, so there should be a chanceto prove some interesting theorems as well.<p><h2> How to Participate </h2>I welcome participation from outside of my University of Washington, CSE 521 class. The datafiles and source code are available from the web. If you can findbetter tours to the official instances, send them to me, and Iwill update the hall of fame. (I hope to automate this soon.) I willalso keep track of lower bound results on various instances.<h2> <!WA4><a href=http://www.cs.washington.edu/education/courses/521/winter96/project/details.html> Details </a> </h2>Here are a few details on exactly how the problem is formulated, andwhat a solution is.<h2> <!WA5><a href=http://www.cs.washington.edu/education/courses/521/winter96/project/theory.html> Theory </a> </h2>I don't know of any results related to this problem (although I haven't looked either). The theory page will contain some useful theorems, aswell as pointers to the literature. Contributions welcome!<p><h2> <!WA6><a href=http://www.cs.washington.edu/education/courses/521/winter96/project/data.html> Data Sets </a> </h2>The current data sets were randomly generated, although some of them are based upon the locations for real cities. Each instance specifies aschedule file, a city file, a starting city, and a starting time.(I would be interested in receiving real data sets to add to set ofinstances.)<p><h2> <!WA7><a href=http://www.cs.washington.edu/education/courses/521/winter96/project/source.html> Source Code and Support Software </a> </h2><p>Some source code is available to "use at your own risk". This codehandles I/0 and provides some very primitive graphics capabilities.There is also an algorithm which finds very bad tours. You can use theshowmap, showsch, and showtour programs to examine the data files.If you submit a tour, make sure that it conforms to the format of atour file.<p><h2> <!WA8><a href=http://www.cs.washington.edu/education/courses/521/winter96/project/mechanics.html> Mechanics </a> </h2>For the CSE 521 course project, there are a few rules, regulations, and deadlines.<p><p></body></html><address>anderson@cs.washington.edu</address>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -