% ===> this file was generated automatically by noweave --- better not edit it

\documentclass[a4paper,11pt]{article}
\usepackage{noweb}
\usepackage{geometry}
\geometry{verbose,a4paper,tmargin=30mm,bmargin=30mm,lmargin=20mm,rmargin=20mm}
\author{Luana Morellato e Vin\'icius Salom\~ao}
\title{T\'ecnicas de Busca e Ordena\c{c}\~ao \\ Traveling Salesman Problem}

\begin{document}
\maketitle

\section{Introdu\c{c}\~ao}
        Os Algoritimos aqui apresentados demonstram v\'arias formas de se resolver o TSP de maneira r\'apida.
        As heur\'isticas usadas s\~ao: Nearest Neigbour (NN), FRP, Greedy e Preority Queue Greedy (PqGreedy).
        Nesse relat\'orio, apresentamos os resultados obtidos quando as heur\'isticas acima apresentadas s\~ao
        executadas para tipos diversos de pontos.

\section{Problema com 48 pontos (att48)}
        Em um problema com pequena quantidade de pontos como este, fica dif\'icil uma an\'alise minuciosa. N\~ao foi
        poss\'ivel notar uma diferen\c{c}a no tempo de execu\c{c}\~ao de NN, FRP e PqGreedy, apenas Greedy teve um
        tempo percept\'ivel. Em rela\c{c}\~ao a mem\'oria alocada FRP despendiou uma menor quantidade, mas na qualidade
        do tour o que obteve melhor resultado foi o Greedy.
\subsection{NN}
Tempo de execu\c{c}\~ao = 0.00 secs \\
Mem\'oria Alocada = 1,507,232 bytes \\
Qualidade do Tour = Aproximadamente 20.9\% superior ao melhor tour.

\subsection{FRP}
Tempo de execu\c{c}\~ao = 0.00 secs \\
Mem\'oria Alocada = 1,024,260 bytes \\
Qualidade do Tour = Aproximadamente 50.3\% superior ao melhor tour. 
\subsection{Greedy}
Tempo de execu\c{c}\~ao = 0.02 secs \\
Mem\'oria Alocada = 3,353,056 bytes \\
Qualidade do Tour = Aproximadamente 19.8\% superior ao melhor tour.
\subsection{PqGreedy}
Tempo de execu\c{c}\~ao = 0.00 secs \\
Mem\'oria Alocada = 2,160,660 bytes \\
Qualidade do Tour = Aproximadamente 34.7\% superior ao melhor tour.

\section{Problema com 100 pontos (KroA100)}
        Com essa quantidade de pontos j\'a \'e poss\'ivel notar uma sens\'ivel diferen\c{c}a entre as heur\'isticas.
        Em rela\c{c}\~ao ao tempo de execu\c{c}\~ao a Frp foi a que executou mais r\'apido e utilizou a menor
        quantidade de mem\'oria. Em rela\c{c}\~ao a qualidade do tour o que obteve melhor resultado foi novamente o Greedy.
\subsection{NN}
Tempo de execu\c{c}\~ao = 0.02 secs \\
Mem\'oria Alocada = 4,595,736 bytes \\
Qualidade do Tour = Aproximadamente 26.2\% superior ao melhor tour.
\subsection{FRP}
Tempo de execu\c{c}\~ao = 0.00 secs \\
Mem\'oria Alocada = 2,182,220 bytes \\
Qualidade do Tour = Aproximadamente 63.2\% superior ao melhor tour.
\subsection{Greedy}
Tempo de execu\c{c}\~ao = 0.10 secs \\
Mem\'oria Alocada = 19,096,892 bytes \\
Qualidade do Tour = Aproximadamente 13.7\% superior ao melhor tour.
\subsection{PqGreedy}
Tempo de execu\c{c}\~ao = 0.02 secs \\
Mem\'oria Alocada = 5,007,660 bytes \\
Qualidade do Tour = Aproximadamente 26.8\% superior ao melhor tour.

\section{Problema com 105 pontos (Lin105)}
        Esse conjunto de pontos possui uma pequena diferen\c{c}a do anterior, pois eles est\~ao dispostos de uma forma
        mais linear o que torna mais interessante a analize de qualidade do tour. Em rela\c{c}\~ao ao uso de mem\'oria
        e tempo de execu\c{c}\~ao a Frp foi novamente a melhor. Em rela\c{c}\~ao a qualidade do tour o que obteve
        melhor resultado foi o PqGreedy.
\subsection{NN}
Tempo de execu\c{c}\~ao = 0.02 secs \\
Mem\'oria Alocada = 4,942,192 bytes \\
Qualidade do Tour = Aproximadamente 41.6\% superior ao melhor tour.
\subsection{FRP}
Tempo de execu\c{c}\~ao = 0.00 secs \\
Mem\'oria Alocada = 2,435,228 bytes \\
Qualidade do Tour = Aproximadamente 68.1\% superior ao melhor tour.
\subsection{Greedy}
Tempo de execu\c{c}\~ao = 0.12 secs \\
Mem\'oria Alocada = 23,663,780 bytes \\
Qualidade do Tour = Aproximadamente 16.6\% superior ao melhor tour.
\subsection{PqGreedy}
Tempo de execu\c{c}\~ao = 0.04 secs \\
Mem\'oria Alocada = 5,746,684 bytes \\
Qualidade do Tour = Aproximadamente 15.3\% superior ao melhor tour.

\section{Problema com 1002 pontos (pr1002)}
        Essa quantidade de pontos \'e boa para analisar o tempo de execu\c{c}ao do algoritmo. Em rela\c{c}\~ao ao
        uso de mem\'oria novamente o FRP foi o melhor, podemos destacar tamb\'em o excessivo comsumo de mem\'oria de
        Greedy. Em rela\c{c}\~ao ao tempo de execu\c{c}\~ao a Frp foi novamente a melhor e em rela\c{c}\~ao a
        qualidade do tour o que obteve melhor resultado foi PqGreedy.
\subsection{NN}
Tempo de execu\c{c}\~ao = 2.26 secs \\
Mem\'oria Alocada = 308,143,700 bytes \\
Qualidade do Tour = Aproximadamente 198.3\% superior ao melhor tour.
\subsection{FRP}
Tempo de execu\c{c}\~ao = 0.12 secs \\
Mem\'oria Alocada = 26,797,924 bytes \\
Qualidade do Tour = Aproximadamente 307.6\% superior ao melhor tour.
\subsection{Greedy}
Tempo de execu\c{c}\~ao = 49.48 secs \\
Mem\'oria Alocada = 9,129,186,232 bytes \\
Qualidade do Tour = Aproximadamente 192.1\% superior ao melhor tour.
\subsection{PqGreedy}
Tempo de execu\c{c}\~ao = 1.34 secs \\
Mem\'oria Alocada = 188,924,316 bytes \\
Qualidade do Tour = Aproximadamente 190.0\% superior ao melhor tour.

\section{Conclus\~ao}
        Analisando as heur\'isticas estudadas nesse trabalho, observamos que a NN \'e r\'apida, n\~ao consome muita
        mem\'oria, mas nem sempre gera um tour de qualidade, j\'a FRP \'e extremamente r\'apida, consome muito pouca
        mem\'oria, mas o tour gerado \'e p\'essimo. A Greedy \'e a mais lerda entre elas e tamb\'em a que aloca mais
        mem\'oria, entretanto a qualidade do tour gerado \'e quase sempre a melhor entre essas heur\'isticas. A mais
        interessante delas \'e a PqGreedy, que \'e uma Greedy otimizada, pois a qualidade do tour est\'a sempre pr\'oxima
        de Greedy, as vezes at\'e melhor, o tempo de execu\c{c}\~ao assim como a aloca\c{c}\~ao de mem\'oria \'e quase a
        metade da NN.
\end{document}

\nwfilename{relatorio.nw}
