8.2: Travelling Salesman

Last updated
Save as PDF

Page ID: 14958

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

A famous problem in mathematics is the Traveling Salesman Problem where the minimum distance of traveling from a home city, through n cities and back to the home city. In this program, you will simulate part of this problem.

Homework
You will write a Matlab function with the following details:

Name the function appropriately (like siemerstjTravelingSalesman)
Comment the function appropriately including a description of the usage.
The function has one input (a matrix of locations of the cities) and no outputs.
Once the function is run, a figure will appear with the cities indicated with one type of symbol and the home city (at the origin) with another.
The user will select cities one at a time with the mouse.
Each time a city is selected, a line is drawn from the previous city with a message of the city selected.
Repeat until all cities are selected.
Once the last remaining city is selected, a line is drawn back to the home city and the total distance of the trip is displayed.

Code execution:

Suppose I enter siemerstjTravelingSalesman([1 1;2 2;3 10]).

Then the following picture chould appear. The “home base” plotted as a green asterisk at the origin and the three cities are plotted at the coordinates (1, 1),(2, 2),(3, 10). Note that the screen is a little larger so that the cities do not fall on the edge of the plot (see either xlim\ylim or axes).

When I click on the closest city (at (1; 1)), I now have

Click the next city...

Finish with the last city...

A few issues arise as you work through the code for this project:

Does the user have to click exactly on top of a city, or can you write the code so that they can click close to the city (and how “close” is close enough?).
How do you keep the user from selecting the same city twice?
How do you make the text for one city “disappear” when the next city is clicked? (see set command for one possibility).