\documentclass{article}
\pagestyle{headings}
\usepackage{noweb}
\usepackage{geometry}
\geometry{verbose,a4paper,tmargin=15mm,bmargin=10mm,lmargin=15mm,rmargin=10mm}
\title{Trabalho de TBO \\
\'{A}rvores e estruturas de Prioridade\\
Relat\'{o}rio}
\author{Anderson Luiz Kil Caetano e Andr\'{e} Manh\~{a}es Machado\\ Ci\^{e}ncia da Computa\c{c}\~{a}o - UFES}

\begin{document}
\maketitle
	Neste primeiro trabalho, implementamos quatro heur\'{i}sticas para o TSP.
	As heur\'{i}sticas s\~{a}o: Greedy, Nearest Neighbour, PQGreedy (Greedy utilizando
	fila de prioridade e kd-tree) e FRP.	\\
	As heur\'{i}sticas foram testadas e agora, apresentaremos um pequeno
	relat\'{o}rio sobre recursos consumidos, desempenho e qualidade do tour obtido
	para cada heur\'{i}stica implementada.

\section{Apresenta\c{c}\~{a}o dos Dados}
	Para a realiza\c{c}\~{a}o dos testes, utilizamos conjuntos de pontos contendo 29, 48,
	100, 105, 1002 e 1379 pontos. Mostraremos, em forma de tabela, os
	dados colhidos atrav\'{e}s de estudos de Profile e desempenho da fun\c{c}\~{a}o.

\subsection{Heur\'{i}stica Nearest Neighbour}
\begin{center}
\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Consumo de Mem\'{o}ria}			\\
\hline
N\'{u}mero de Pontos	&	Mem\'{o}ria utilizada (bytes)	\\
\hline
29			&	663,196				\\
48			&	1,322,168			\\
100			&	3,789,992			\\
105			&	4,068,396			\\
1002			&	228,311,696			\\
1379			&	422,851,740			\\
\hline
\end{tabular}
\\
\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Desempenho}					\\
\hline
N\'{u}mero de Pontos	&	Tempo Gasto (segundos)		\\
\hline
29			&	0.02				\\
48			&	0.04				\\
100			&	0.10				\\
105			&	0.11				\\
1002			&	6.26				\\
1379			&	11.67				\\
\hline
\end{tabular}
\\
\begin{tabular}{|c|c|c|c|}
\multicolumn{4}{c}{Qualidade do Tour}						\\
\hline
N\'{u}mero de Pontos	&	Tour Calculado	& Tour \'{O}timo & Fator(T/Topt)\\
\hline
48 & 39236.884 & 33523.708 & 1.170 \\
100 & 26133.451 & 21285.443 & 1.227 \\
105 & 20365.073 & 14382.995 & 1.415 \\
1002 & 315596.587 & 105694.610 & 2.985 \\
\hline
\end{tabular}
\end{center}

\subsection{Heur\'{i}stica Greedy}
\begin{center}
\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Consumo de Mem\'{o}ria}			\\
\hline
N\'{u}mero de Pontos	&	Mem\'{o}ria utilizada (bytes)	\\
\hline
29			&	1,074,468			\\
48			&	2,308,904			\\
100			&	10,034,760			\\
105			&	13,740,532			\\
1002			&	3,108,125,240			\\
1379			&	10,171,948,948			\\
\hline
\end{tabular}
\\
\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Desempenho}					\\
\hline
N\'{u}mero de Pontos	&	Tempo Gasto (segundos)		\\
\hline
29			&	0.02				\\
48			&	0.04				\\
100			&	0.20				\\
105			&	0.28				\\
1002			&	71.39				\\
1379			&	297.14				\\
\hline
\end{tabular}
\\
\begin{tabular}{|c|c|c|c|}
\multicolumn{4}{c}{Qualidade do Tour}						\\
\hline
N\'{u}mero de Pontos	&	Tour Calculado	& Tour \'{O}timo & Fator(T/Topt)\\
\hline
48 & 40160.368 & 33523.708 & 1.197	\\
100 & 24197.286 & 21285.443 & 1.136	\\
105 & 16771.826 & 14382.995 & 1.166	\\
1002 & 306458.145 & 105694.610 & 2.899	\\
\hline
\end{tabular}
\end{center}


\subsection{Heur\'{i}stica FRP}
\begin{center}
\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Consumo de Mem\'{o}ria}			\\
\hline
N\'{u}mero de Pontos	&	Mem\'{o}ria utilizada (bytes)	\\
\hline
29			&	555,528			\\
48			&	987,988			\\
100			&	2,162,524		\\
105			&	2,548,452		\\
1002			&	48,610,544		\\
1379			&	123,685,980		\\
\hline
\end{tabular}
\\
\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Desempenho}					\\
\hline
N\'{u}mero de Pontos	&	Tempo Gasto (segundos)		\\
\hline
29			&	0.01				\\
48			&	0.02				\\
100			&	0.04				\\
105			&	0.96				\\
1002			&	0.96				\\
1379			&	2.60				\\
\hline
\end{tabular}
\\
\begin{tabular}{|c|c|c|c|}
\multicolumn{4}{c}{Qualidade do Tour}						\\
\hline
N\'{u}mero de Pontos	&	Tour Calculado	& Tour \'{O}timo & Fator(T/Topt)\\
\hline
48 & 60524.178 & 33523.708 & 1.805	\\
100 & 39974.811 & 21285.443 & 1.878	\\
105 & 27356.679 & 14382.995 & 1.902	\\
1002 & 526600.042 & 105694.610 & 4.982	\\
\hline
\end{tabular}
\end{center}


\subsection{Heur\'{i}stica PQGreedy}
\begin{center}
\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Consumo de Mem\'{o}ria}			\\
\hline
N\'{u}mero de Pontos	&	Mem\'{o}ria utilizada (bytes)	\\
\hline
29			&	2,078,516		\\
48			&	5,844,880		\\
100			&	28,852,012		\\
105			&	23,706,648		\\
1002			&	4,521,054,840		\\
1379			&	8,733,508,488		\\
\hline
\end{tabular}
\\
\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Desempenho}					\\
\hline
N\'{u}mero de Pontos	&	Tempo Gasto (segundos)		\\
\hline
29			&	0.04			\\
48			&	0.09			\\
100			&	0.44			\\
105			&	0.34			\\
1002			&	76.5			\\
1379			&	148.02			\\
\hline
\end{tabular}
\\
\begin{tabular}{|c|c|c|c|}
\multicolumn{4}{c}{Qualidade do Tour}						\\
\hline
N\'{u}mero de Pontos	&	Tour Calculado	& Tour \'{O}timo & Fator(T/Topt)\\
\hline
48 & 41946.866 & 33523.708 & 1.251	\\
100 & 25621.620 & 21285.443 & 1.203	\\
105 & 15339.076 & 14382.995 & 1.066	\\
1002 & 318179.683 & 105694.610 & 3.010	\\
\hline
\end{tabular}
\end{center}


\end{document}
\nwenddocs{}
