\documentclass[a4paper,10pt]{article}
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
\usepackage[backref=page,plainpages=false,pdfpagelabels]{hyperref}

%opening
\title{Trabalho 0: \'Arvores e estruturas de prioridade \\
Avalia\c c\~ao da qualidade dos tours\\ e desempenho dos algoritmos}
\author{Mariana Lorenzon de Arag\~ao \\
	Marcos Alexandre Figur Messer}

\begin{document}
\maketitle
   Para compararmos as heur\'isticas \emph{Nearest Neighbor},
\emph{Frp}, \emph{Greedy} e \emph{PQGreedy} realizamos tr\^es testes em nossos
  algoritmos. Sendo estes: qualidade dos tours, efici\^encia e quantidade de
  mem\'oria para se executar o algoritmo. Nas se\c c\~oes a seguir encontram-se
  os resultados dos testes.

  Neste documento tamb\'em encontra-se os resultados dos testes de efici\^encia para o
  algoritmo \emph{KDTree}. Os resultados se encontram nas se\c c\~oes a seguir.


\section{Desempenho dos algoritmos}

\subsection{Efici\^encia}
	Resultados retirados do profile de cada heur\'istica.

\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c|c|c|c|} \hline &\multicolumn{4}{|c|}{Heur\'istica} \\
\hline Pontos & \textbf{Nn} & \textbf{Frp} & \textbf{Greedy} & \textbf{PqGreedy} \\
\hline \hline \textbf{att48}	& 0m0.027s & 0m0.031s & 0m0.051s & 0m0.019s\\
\hline \textbf{kroA100} 	& 0m0.058s & 0m0.033s & 0m0.335s & 0m0.023s\\
\hline \textbf{lin105}	 	& 0m0.034s & 0m0.035s & 0m0.394s & 0m0.025s\\
\hline \textbf{linhp318}	& 0m0.099s & 0m0.068s & 0m7.040s &  --\\
\hline \textbf{lin318} 		& 0m0.101s & 0m0.064s & 0m7.013s & --\\
\hline \textbf{pr1002} 		& 0m1.226s & 0m0.229s & 0m44.353s &  --\\
\hline \textbf{nrw1379} 	& 0m2.148s & 0m0.301s & (out of memory) & --\\
\hline \textbf{pla7397} 	& 0m55.537s & 0m3.222s & (out of memory) &  --\\
\hline
\end{tabular}
\caption{Tempo de execu\c c\~ao do algoritimo para um determinado conjunto de pontos.}
\label{Tabela2}
\end{center}
\end{table}

\subsection{Mem\'oria}
	Resultados retirados do profile de cada heur\'istica.

\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c|c|c|c|} \hline &\multicolumn{4}{|c|}{Heur\'istica} \\
\hline Pontos & \textbf{Nn} & \textbf{Frp} & \textbf{Greedy} & \textbf{PqGreedy} \\
\hline \hline \textbf{att48} & 1,058,688 & 900,512 & 2,561,052 & 1,094,364 \\
\hline \textbf{kroA100} & 2,735,404 & 1,886,572 & 12,298,936 & 2,445,984 \\
\hline \textbf{lin105} & 2,873,352 & 1,987,192 & 15,798,304 & 2,603,048 \\
\hline \textbf{linhp318} & 16,032,256 & 6,288,588 & 218,788,904 & -- \\
\hline \textbf{lin318} & 16,032,240 & 6,288,588 & 218,785,06 & --\\
\hline \textbf{pr1002} & 128,364,612 & 21,785,492 & 7,456,036,124 & --\\
\hline \textbf{nrw1379} & 235,469,300 & 29,666,584 & 16,000,142,656 & --\\
\hline \textbf{pla7397} & 6,301,994,088 & 200,741,896 & (out of memory) & -- \\
\hline
\end{tabular}
\caption{Uso de mem\'oria, dados em bytes}
\label{Tabela3}
\end{center}
\end{table}


\subsection{Qualidade dos Tours}
 Esses resultados foram obtidos do c\'alculo da raz\~ao entre o melhor tour e o tour resultante de cada heur\'istica.\\

\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c|c|c|c|} \hline &\multicolumn{4}{|c|}{Heur\'istica} \\
\hline Pontos & \textbf{Nn} & \textbf{Frp} & \textbf{Greedy} & \textbf{PqGreedy} \\
\hline \hline \textbf{att48} & 1.2089 & 1.686 & 1.1980 &  1.6045\\
\hline \textbf{kroA100} & 1.2617 & 1.628 & 1.1368 &  2.4945\\
\hline \textbf{lin105} & 1.4158 & 2.016 & 1.1661 & 2.0959 \\
\hline \textbf{pr1002} & 3.1522 & 4.9291 & 2.9218 & --\\
\hline
\end{tabular}
\caption{Qualidade dos tours}
\label{Tabela1}
\end{center}
\end{table}

\subsection{Efici\^encia e uso de mem\'oria da KDTree}

\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c|c|}
\hline Pontos & \textbf{Tempo} & \textbf{Uso de mem\'oria} \\
\hline \hline \textbf{att48} & 0m0.029s & 829,416 bytes\\
\hline \textbf{kroA100} &  0m0.038s &  1,697,980 bytes\\
\hline \textbf{lin105} &  0m0.038s & 1,788,348 bytes\\
\hline \textbf{linhp318} &  0m0.069s & 26,236 bytes\\
\hline \textbf{lin318} & 0m0.126s & 5,539,772 bytes\\
\hline \textbf{pr1002} & 0m0.272s & 18,597,528 bytes\\
\hline \textbf{nrw1379} & 0m0.303s & 25,159,604 bytes\\
\hline \textbf{pla7397} & 0m2.566s & 168,217,356 bytes\\
\hline
\end{tabular}
\caption{Tempo de execu\c c\~ao do algoritmo e uso de mem\'oria}
\label{Tabela4}
\end{center}
\end{table}


\end{document}
