\documentclass{article}
\usepackage{noweb}
\usepackage{geometry}
\geometry{verbose,a4paper,tmargin=30mm,bmargin=30mm,lmargin=20mm,rmargin=20mm}
\title{Tecnicas de Busca e Ordena\c{c}\~ao (TBO) - Trabalho Zero\\
Travel Salesman Problem (TSP)}
\author{Lucas Secchin Sampaio \\
	Vin\'icius Gazzoli Rangel\\
	Ci\^encia da Computa\c{c}\~ao - UFES\\
}

\def\nn{\emph{nn }}
\def\frp{\emph{frp }}
\def\greedy{\emph{greedy }}
\def\pqgreedy{\emph{pqgreedy }}

\begin{document}
\maketitle
  
   Este documento apresenta compara\c{c}\~oes de desempenho de mem\'oria e tempo de execu\c{c}\~ao entre as
   heur\'isticas \emph{NN}, \emph{FRP}, \emph{GREEDY} e \emph{PQGREEDY} para os seguintes pontos: \emph{att48},
   \emph{kroA100}, \emph{lin318}, \emph{pr1002} e \emph{nrw1379}.
  


\begin{tabular}{|c|c|c|c|c| l|}

\multicolumn{6}{c}{\textbf}{Tabela de compara\c{c}\~ao de mem\'oria (bytes)}\\
\hline

  HEUR\'ISTICAS & Pontos att48 & Pontos kroA100 & Pontos lin318 & Pontos pr1002 & Pontos nrw 1379\\
\hline
\hline
  NN & 1,535,632 & 4,685,116 & 35,116,224 & 312,660,380 & 581,419,408\\
\hline
  FRP & 1,760,664  & 5,300,128 & 42,895,328 & 369,754,792 & 834,775,940\\
\hline
   GREEDY & 5,147,036 & 28,672,528 & 520,379,620 & 18,289,901,684 & 28,727,639,424\\
\hline
   PQGREEDY & 3,793,324 & 14,244,688 & 117,665,504 & 1,126,102,568 & 2,162,311,424\\
 \hline

\end{tabular}

\begin{tabular}{|c|c|c|c|c| l|}

\multicolumn{6}{c}{\textbf}{Tabela de compara\c{c}\~ao de tempo }\\
\hline

  HEUR\'ISTICAS & Pontos att48 & Pontos kroA100 & Pontos lin318 & Pontos pr1002 & Pontos nrw 1379\\
\hline
\hline
  NN & 0m0.166s & 0m0.176s & 0m1.025s & 0m6.572s & 0m11.890s\\
\hline
  FRP & 0m0.101s & 0m0.152s & 0m0.722s & 0m9.398s & 0m29.250s\\
\hline
   GREEDY & 0m0.209s & 0m0.552s & 0m7.697s & 5m45.137s & 13m34.681s \\
\hline
   PQGREEDY & 0m0.188s & 0m0.309s & 0m2.358s & 0m21.108s & 0m40.301s\\
 \hline

\end{tabular}



\section{Pontos att48}

 Para esses pontos a \emph{Heur\'istica NN} gastou 0,166 segundos e 1,535,632 bytes de mem\'oria para compilar e rodar,
 a \emph{Heur\'istica FRP} gastou 0,101 segundos e 1,760,664 bytes, a \emph{Heur\'istica GREEDY} gastou 0,209 segundos
 e 5,147,036 bytes, a \emph{Heur\'istica PQGREEDY} gastou 0,188 segundos e 3,793,324 bytes. O melhor tour produzido
 foi da \emph{Heur\'istica GREEDY}, seguida da \emph{Heur\'istica PQGREEDY}, \emph{Heur\'istica NN} e por \'ultima a
 \emph{Heur\'istica FRP}.



\section{Pontos kroA100}

 Para esses pontos a \emph{Heur\'istica NN} gastou 0,176 segundos e 4,685,116 bytes de mem\'oria para compilar e rodar,
 a \emph{Heur\'istica FRP} gastou 0,152 segundos e 5,300,128 bytes, a \emph{Heur\'istica GREEDY} gastou 0,552 segundos
 e 28,672,528 bytes, a \emph{Heur\'istica PQGREEDY} gastou 0,309 segundos e 14,244,688 bytes. O melhor tour produzido
 foi da \emph{Heur\'istica GREEDY}, seguida da \emph{Heur\'istica PQGREEDY}, \emph{Heur\'istica NN} e por \'ultima a
 \emph{Heur\'istica FRP}.
 
 


\section{Pontos lin318}

 Para esses pontos a \emph{Heur\'istica NN} gastou 1,025 segundos e 35,116,224 bytes de mem\'oria para compilar e rodar,
 a \emph{Heur\'istica FRP} gastou 0,722 segundos e 42,895,328 bytes, a \emph{Heur\'istica GREEDY} gastou 7,697 segundos
 e 520,379,620 bytes, a \emph{Heur\'istica PQGREEDY} gastou 2,358 segundos e 117,665,504 bytes. O melhor tour produzido
 foi da \emph{Heur\'istica GREEDY}, seguida da \emph{Heur\'istica PQGREEDY}, \emph{Heur\'istica NN} e por \'ultima a
 \emph{Heur\'istica FRP}.



\section{Pontos pr1002}

 Para esses pontos a \emph{Heur\'istica NN} gastou 6,572 segundos e 312,660,380 bytes de mem\'oria para compilar e rodar,
 a \emph{Heur\'istica FRP} gastou 9,398 segundos e 369,754,792 bytes, a \emph{Heur\'istica GREEDY} gastou 5 minutos e 
 45,137 segundos e 18,289,901,684 bytes, a \emph{Heur\'istica PQGREEDY} gastou 21,108 segundos e 1,126,102,568 bytes.
 O melhor tour produzido foi da \emph{Heur\'istica GREEDY}, seguida da \emph{Heur\'istica PQGREEDY}, \emph{Heur\'istica NN} 
 e por \'ultima a \emph{Heur\'istica FRP}.




\section{Pontos nrw 1379}

 Para esses pontos a \emph{Heur\'istica NN} gastou 11,890 segundos e 581,419,408 bytes de mem\'oria para compilar e rodar,
 a \emph{Heur\'istica FRP} gastou 9,398 segundos e 369,754,792 bytes, a \emph{Heur\'istica GREEDY} gastou 5 minutos e 
 45,137 segundos e 18,289,901,684 bytes, a \emph{Heur\'istica PQGREEDY} gastou 21,108 segundos e 1,126,102,568 bytes.
 O melhor tour produzido foi da \emph{Heur\'istica GREEDY}, seguida da \emph{Heur\'istica PQGREEDY}, \emph{Heur\'istica NN} 
 e por \'ultima a \emph{Heur\'istica FRP}.

  


\section{Conclus\~ao }

Podemos concluir que, se uma m\'aquina n\~ao possuir uma quantidade boa de mem\'oria a melhor Heur\'istica \'e
a \emph{Heur\'istica NN}, pois ela \'e r\'apida, n\~ao requer muita mem\'oria e produz um \emph{tour} satisfat\'orio.
A \emph{Heur\'istica GREEDY} foi a que apresentou o melhor \emph{tour}, por\'em requer muita mem\'oria e tempo. 
A heur\'istica que mais se destacou foi a \emph{PQGREEDY}, pois produziu um \emph{tour} pr\'oximo do da 
\emph{GREEDY}, entretanto com um tempo notavelmente menor e com menos mem\'oria. A \emph{Heur\'istica FRP}, apesar
de apresentar resultados satisfat\'orios em rela\c{c}\~ao ao consumo de mem\'oria e tempo gasto, ela produz o pior
\emph{tour} na maioria dos testes, sendo considerada a pior \emph{Heur\'istica}.



  
\end{document}


