% -*- latex -*-
% FILE: "/home/evmik/jobs/wm/2015_fall_practical_computing_for_scientists/hw08/hw08.tex"
% LAST MODIFICATION: "Wed, 21 Oct 2015 09:33:46 -0400 (evmik)"
% (C) 2010 by Eugeniy Mikhailov, <evgmik@gmail.com>
% $Id:$
\documentclass[letter,12pt]{article}

%---------------------------------------------------------------
\usepackage{listings}
\usepackage{color}
\usepackage{fullpage}
%---------------------------------------------------------------

\begin{document}
\newcommand{\problem}[1]{%
	{\flushleft  \bf #1\\}
}
\newcommand{\hw}[1]{%
	\begin{center}
		\Large  \bf Homework #1%
	\end{center}%
}
\newcommand{\mat}[1]{% matlab code
{\color{blue}\texttt{#1}}%
}

%---------------------------------------------------------------
\hw{08}

General comments: 
\begin{itemize}
	\item Do not forget to run some test cases. 
\end{itemize}

\problem{Problem 1 (5 points)}
%---------------------------------------------------------------
Modify the provided traveler salesman combinatorial algorithm to solve 
a slightly different problem. You are looking for the shortest route which
goes through all cities, while it starts and ends in the same city (the first
one), i.e. the close loop route. 

Coordinates of cities are provided in the 'cities\_for\_combinatorial\_search.dat' file:
the first column  of
the data file is 'x' coordinate and second one contains 'y' coordinates.
The coordinates of the beginning/end route city are in the first string.  

What is the sequence of all cities in the shortest route?

What is the total length of the best route?

Provide a plot with visible cities and the shortest route.



\problem{Problem 2 (10 points)}
%---------------------------------------------------------------
Implement the Metropolis algorithm to solve the above problem. A good way to obtain
a new test route is to randomly swap two cities  along the route.
Tweak the algorithm number of cycles,  initial and final  temperature ($kT$).

Compare this algorithm solution  with the above combinatorial one.

Now load the cities coordinates from the 
'cities\_for\_metropolis\_search.dat' file.  Find the shortest route for
this set of cities.

What is the sequence of  cities in the shortest route?

What is the total length of the best route?

Provide a plot with visible cities and the shortest route.






%---------------------------------------------------------------
\end{document}
%---------------------------------------------------------------