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

\author{Victor Pinto / Thiago Theodoro}

\title{Trabalho pr\'atico 0}

\begin{document}

\maketitle

\section{Introdu\c c\~ao}


Neste trabalho ser\~ao abordados estruturas auxiliares que auxiliar\~ao na implementa\c c\~ao das heurísticas do TSP.

\section{ KDTree }
A KDtree \'e uma estrutura utilizada pra repartir pontos no espa\c co, em duas ou tr\^es dimens\~oes. Foram efetuados os seguintes testes com os seguintes conjuntos de pontos:

\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline Conj. de ptos & \textbf{Tempo} & \textbf{Mem} \\
\hline
\hline \textbf{att48}   & 0m0.021s & 894,936 bytes \\
\hline \textbf{kroA100} & 0m0.028s & 1,914,972 bytes\\
\hline \textbf{lin105}  & 0m0.030s & 1,895,524 bytes\\
\hline \textbf{lin318}  & 0m0.073s & 8,980,352 bytes\\
\hline \textbf{pr1002}  & 0m0.210s & 29,024,760 bytes\\
\hline \textbf{nrw1379} & 0m0.504s & 92,170,960 bytes \\
\hline
\end{tabular}
\caption{Tempo de execu\c c\~ao e Mem\'oria alocada}
\label{tab1}
\end{center}
\end{table}

\subsection{Conclus\~oes}
Para todos os conjuntos de pontos a contru\c c\~ao da KDTree foi realizada com sucesso. E ainda foi usada a fun\c c\~ao isKdtree para avaliar se a \'arvore criada realmente \'e uma KDTree, e em todos os casos o resultado foi True. Por enquanto ela, a KDTree, ainda n\~ao teve utilidade, mas mais a frente ser\'a de grande utilidade \'as heur\'isticas do TSP, devido a sua praticidade, e agilidade na busca por elementos.

\section{Compara\c c\~oes entre heur\'isticas}
Foram testadas quatro heur\'isticas para a solu\c c\~ao do TSP. Segue abaixo as compara\c c\~oes
entre elas, Tempo de execu\c c\~ao (Tabela 1), mem\'oria alocada (Tabela 2), e taxa entre o peso
da heur\'istica e o melhor tour existente (Tabela 3) . Para uma maior quantidade pontos ocorreu estouro da pilha ( Stack Over Flow ), e s\'o foi comparada a taxa, os conjuntos de pontos que possuem seus respectivos melhores tours.
\\
\\

\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c|c|c|c|} \hline &\multicolumn{4}{|c|}{Heur\'istica} \\
\hline Conj. de ptos & \textbf{NN} & \textbf{FRP} & \textbf{Greedy} & \textbf{PQGreedy} \\
\hline
\hline \textbf{att48}   & 0m0.015s & 0m0.013s & 0m0.025s & 0m0.018s \\
\hline \textbf{kroA100} & 0m0.024s & 0m0.022s & 0m0.090s & 0m0.040s \\
\hline \textbf{lin105}  & 0m0.026s & 0m0.023s & 0m0.105s & 0m0.042s \\
\hline \textbf{lin318}  & 0m0.084s & 0m0.059s & 0m1.552s & 0m0.196s \\
\hline \textbf{pr1002}  & 0m0.578s & 0m0.175s & 0m36.536s & 0m1.268s \\
\hline \textbf{nrw1379} & 0m0.981s & 0m0.344s & 1m19.034s & 0m2.397s \\
\hline
\end{tabular}
\caption{Tempo de execu\c c\~ao}
\label{tab1}
\end{center}
\end{table}

\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c|c|c|c|} \hline &\multicolumn{4}{|c|}{Heur\'istica} \\
\hline Conj. de ptos & \textbf{NN} & \textbf{FRP} & \textbf{Greedy} & \textbf{PQGreedy} \\
\hline
\hline \textbf{att48}   & 1,153,364   & 1,000,832  & 2,801,336      & 2,405,740 \\
\hline \textbf{kroA100} & 3,009,992   & 2,133,260  & 13,451,524     & 6,280,300 \\
\hline \textbf{lin105}  & 2,128,716   & 15,496,112 & 3,142,540      & 6,964,664 \\
\hline \textbf{lin318}  & 17,631,788  & 10,082,148 & 245,442,384    & 38,961,200 \\
\hline \textbf{pr1002}  & 142,931,972 & 32,202,780 & 5,912,549,036  & 247,948,728 \\
\hline \textbf{nrw1379} & 263,092,244 & 99,713,164 & 14,160,907,156 & 493,422,100 \\
\hline
\end{tabular}
\caption{Mem\'oria alocada, em bytes}
\label{tab2}
\end{center}
\end{table}

\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c|c|c|c|} \hline &\multicolumn{4}{|c|}{Heur\'istica} \\
\hline Conj. de ptos & \textbf{NN} & \textbf{FRP} & \textbf{Greedy} & \textbf{PQGreedy} \\
\hline \hline \textbf{att48} & 1.20888836171914 & 1.652023028724 & 1.19796914883162 & 1.28012564041996 \\
\hline \textbf{kroA100} & 1.26172560101985 & 1.87304553227699 & 1.13679974385868 & 1.27765186805663 \\
\hline \textbf{lin105} & 1.41575215007234 & 1.88181117661256 & 1.16608712817508 & 1.15319634247905 \\
\hline \textbf{pr1002} & 3.15221792504948 & 4.68257352011615 & 2.89946804631958 & 2.98857390070824 \\
\hline
\end{tabular}
\caption{Qualidade do tour ( somente para os conjuntos de pontos que possuem arquivo com melhor tour)}
\label{tab3}
\end{center}
\end{table}





\subsection{Conclus\~oes}

Analisando os resultados obtidos a partir dos profiles dos testes dos pontos, verificamos que:
No quesito tempo a heur\'istica do FRP supera as demais, e assim como no quesito mem\'oria alocada, aonde ele troca vantagens com o pqgreedy, j\'a que os dois usam a estrutura da KDtree, o que agiliza a busca pelo ponto mais pr\'oximo. Por\'em se tratando de qualidade de tour, mesmo sendo mais lento e alocando uma quantidade de mem\'oria muito maior ( devido ao tamanho de sua lista de prioridade ), o tour gerado pela Greedy \'e superior aos demais.


\end{document}

