\documentclass[12pt]{amsart}
\usepackage[portuges]{babel}
\usepackage{color}
\usepackage{listings}
\usepackage{enumerate}
\title{Trabalho 0: \\Heur\'isticas para TSP \\}
\author{Nuno Almeida Rasseli}

\begin{document}
\maketitle

\lstset{
basicstyle=\small,
keywordstyle=\color{blue}\bfseries,
language=C,
indent=12pt
}

\textbf{Disciplina: TBO}



\textbf{Professor: Raul H. C. Lopes}

\section{Introdu\c c\~ao}

Neste trabalho foram implementadas quartro heur\'isticas para c\'alculo de melhor caminho para um dado conjunto de pontos.
O funcionamento dos algoritmos mostrou-se bastante interessante, tendo resultados bem satisfatorios no ponto de vista de um iniciante.
Esse artigo ir\'a abordar a diferen\c ca no funcionamento dos algoritmos implementados nos quesitos desempenho e qualidade de resultado.

Uma observa\c c\~ao importante \'e que todos os arquivos estao sendo compilados com diretiva de otimiza\c c\~ao O2. Portanto isso ser\'a levado em conta no quesito desempenho.


\section{Qualidade de resultado}

\subsection{Nearest Neighbor}

Esta tabela foi obtida executanto o algoritmo do nearest nighbor para os arquivos dados.

\begin{tabular}{|c|c|c| l|}
\hline
\multicolumn{4}{|c|}{Tabela de compara\c cao de resultados}\\
\hline
Arquivo de teste & Peso calculado & Melhor peso & Taxa de diferen\c ca \\
\hline
%../../tsp.tour/test.data/tourcmp.pl ../../test.data/a280.tsp.gz ../../test.data/frtsplib.pl ./tsp.nn ./../../tsp.tour/tour.eval/tourlen ../../tsp.tour/test.data/tsplibopt.pl
a280.tsp.gz & 3214.4634396871743 & 2586.769647563161 & 1.24265546517268 \\
%../../tsp.tour/test.data/tourcmp.pl ../../test.data/att48.tsp.gz ../../test.data/frtsplib.pl ./tsp.nn ./../../tsp.tour/tour.eval/tourlen ../../tsp.tour/test.data/tsplibopt.pl
att48.tsp.gz & 43544.27194238312 & 33523.7085074356 & 1.29890975315947 \\
%../../tsp.tour/test.data/tourcmp.pl ../../test.data/kroA100.tsp.gz ../../test.data/frtsplib.pl ./tsp.nn ./../../tsp.tour/tour.eval/tourlen ../../tsp.tour/test.data/tsplibopt.pl
kroA100.tsp.gz & 26480.883557065656 & 21285.443181571078 & 1.24408420022905 \\
%../../tsp.tour/test.data/tourcmp.pl ../../test.data/pr1002.tsp.gz ../../test.data/frtsplib.pl ./tsp.nn ./../../tsp.tour/tour.eval/tourlen ../../tsp.tour/test.data/tsplibopt.pl
pr1002.tsp.gz & 315596.5873942434 & 105694.61023909131 & 2.98592886316846 \\
\hline
\end{tabular}

\subsection{FRP}

Esta tabela foi obtida executanto o algoritmo do FRP para os arquivos dados.

\begin{tabular}{|c|c|c| l|}
\hline
\multicolumn{4}{|c|}{Tabela de compara\c cao de resultados}\\
\hline
Arquivo de teste & Peso calculado & Melhor peso & Taxa de diferen\c ca \\
%../../tsp.tour/test.data/tourcmp.pl ../../test.data/a280.tsp.gz ../../test.data/frtsplib.pl ./tsp.nn ./../../tsp.tour/tour.eval/tourlen ../../tsp.tour/test.data/tsplibopt.pl
a280.tsp.gz & 4106.877615072053 & 2586.769647563161 & 1.58764721046611 \\
%../../tsp.tour/test.data/tourcmp.pl ../../test.data/att48.tsp.gz ../../test.data/frtsplib.pl ./tsp.nn ./../../tsp.tour/tour.eval/tourlen ../../tsp.tour/test.data/tsplibopt.pl
att48.tsp.gz & 45384.01864383262 & 33523.7085074356 & 1.35378872638051 \\
%../../tsp.tour/test.data/tourcmp.pl ../../test.data/kroA100.tsp.gz ../../test.data/frtsplib.pl ./tsp.nn ./../../tsp.tour/tour.eval/tourlen ../../tsp.tour/test.data/tsplibopt.pl
kroA100.tsp.gz & 35614.42069698089 & 21285.443181571078 & 1.67318201426108 \\
%../../tsp.tour/test.data/tourcmp.pl ../../test.data/pr1002.tsp.gz ../../test.data/frtsplib.pl ./tsp.nn ./../../tsp.tour/tour.eval/tourlen ../../tsp.tour/test.data/tsplibopt.pl
pr1002.tsp.gz & 447676.5933873587 & 105694.61023909131 & 4.2355669070984 \\
\hline
\end{tabular}

\subsection{Greedy}

Esta tabela foi obtida executanto o algoritmo do greedy para os arquivos dados.

\begin{tabular}{|c|c|c| l|}
\hline
\multicolumn{4}{|c|}{Tabela de compara\c cao de resultados}\\
\hline
Arquivo de teste & Peso calculado & Melhor peso & Taxa de diferen\c ca \\
%../../tsp.tour/test.data/tourcmp.pl ../../test.data/a280.tsp.gz ../../test.data/frtsplib.pl ./tsp.nn ./../../tsp.tour/tour.eval/tourlen ../../tsp.tour/test.data/tsplibopt.pl
a280.tsp.gz & 3660.8161265035883 & 2586.769647563161 & 1.41520762389965 \\
%../../tsp.tour/test.data/tourcmp.pl ../../test.data/att48.tsp.gz ../../test.data/frtsplib.pl ./tsp.nn ./../../tsp.tour/tour.eval/tourlen ../../tsp.tour/test.data/tsplibopt.pl
att48.tsp.gz & 67686.74017575837 & 33523.7085074356 & 2.01907077675328 \\
%../../tsp.tour/test.data/tourcmp.pl ../../test.data/kroA100.tsp.gz ../../test.data/frtsplib.pl ./tsp.nn ./../../tsp.tour/tour.eval/tourlen ../../tsp.tour/test.data/tsplibopt.pl
kroA100.tsp.gz & 57923.74284336055 & 21285.443181571078 & 2.72128432324636 \\
%../../tsp.tour/test.data/tourcmp.pl ../../test.data/pr1002.tsp.gz ../../test.data/frtsplib.pl ./tsp.nn ./../../tsp.tour/tour.eval/tourlen ../../tsp.tour/test.data/tsplibopt.pl
pr1002.tsp.gz & 755458.7039244107 & 105694.61023909131 & 7.14756128259985 \\
\hline
\end{tabular}

\subsection{PQGreedy}

O PQGreedy n\~ao retornou resposta em tempo h\'abil (menos de cinco minutos). Portanto n\~ao h\'a tabela de resultados para o mesmo!

\section{Desempenho}

Dos algoritmos implementados, o frp se mostrou o mais eficiente.
No entanto o mesmo retornou um resultado com qualidades baixas em rela\c c\~ao aos outros implementados.
Em seguida vem o nearest neighbor, que al\'em de apresentar um r\'apido tempo de resposta tamb\'em retornou o melhor resultado.
A explica\c c\~ao encontrada para tantas qualidades foi sua simplicidade.
O greedy n\~ao apresentou uma boa qualidade na sua resposta, mas teve um tempo de resposta razo\'avel na m\'edia. No entanto houve casos em que a resposta foi quase estant\^anea. Assim como tamb\'em houve um caso em que o temo de resposta foi muito grande (pr1002.tsp.gz), provavelmente devido a seu alto gasto em mem\'oria.
O pqgreedy n\~ao retornou resposta em tempo h\'abil, impossibilitanto assim a an\'alise de seus resultados.

Em termos de desempenho os melhores foram ordenadamente:

\end{document}
