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

\author{D\'ebora Zupeli Bossois \\ Jo\~ao Olavo Bai\~ao de Vasconcelos}

\title{Tours}

\begin{document}

\maketitle

\section{Testes comparativos TSP}
Nesta se\c c\~ao, realizamos testes comparativos para as heur\'isticas \emph{Nearest Neighbor}, \emph{FRP}, \emph{Greedy } e \emph{PQGreedy}. Dividimos em tr\^es tabelas distintas, que informam o tempo (Tabela \ref{tab1}) e a mem\'oria gastos (Tabela \ref{tab2}), e a qualidade do tour (Tabela \ref{tab3}).

\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c|c|c|c|} \hline
&\multicolumn{4}{|c|}{Fun\c c\~ao} \\
\hline Conj. de ptos & \textbf{NN} & \textbf{FRP} & \textbf{Greedy} & \textbf{PQGreedy} \\
\hline \hline \textbf{att48} & 0m0.039s & 0m0.038s & 0m0.052s & 0m0.046s \\
\hline \textbf{kroA100} & 0m0.051s & 0m0.050s & 0m0.147s & 0m0.071s \\
\hline \textbf{lin105} & 0m0.052s & 0m0.050s & 0m0.154s & 0m0.073s \\
\hline \textbf{lin318} & 0m0.086s & 0m0.085s & 0m3.482s & 0m0.246s \\
\hline \textbf{linp318} & 0m0.080s & 0m0.084s & 0m3.446s & 0m0.238s \\
\hline \textbf{pr1002} & 0m0.222s & 0m0.238s & 1m7.729s & 0m0.635s \\
\hline \textbf{nrw1379} & 0m0.315s & 0m0.332s & 3m46.173s & 0m1.309s \\
\hline \textbf{pla33810} & 0m25.161s & 0m24.585s & (stack overflow) & (stack overflow) \\
\hline
\end{tabular}
\caption{Tempo}
\label{tab1}
\end{center}
\end{table}

\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c|c|c|c|} \hline
&\multicolumn{4}{|c|}{Fun\c c\~ao} \\
\hline Conj. de ptos & \textbf{NN} & \textbf{FRP} & \textbf{Greedy} & \textbf{PQGreedy} \\
\hline \hline \textbf{att48} & 1,11 & 1,11 & 3,01 & 2,70 \\
\hline \textbf{kroA100} & 2,40 & 2,40 & 15,75 & 6,77 \\
\hline \textbf{lin105} & 2,57 & 2,57 & 17,54 & 7,56 \\
\hline \textbf{lin318} & 8,38 & 8,38 & 322,469,132 b & 30,066,568 b \\
\hline \textbf{linp318} & 8,376,768 b & 8,376,768 b & 322,469,132 b & 30,066,568 b \\
\hline \textbf{pr1002} & 27,966,400 b & 27,966,400 b & 8,751,621,964 b & 110,927,624 b \\
\hline \textbf{nrw1379} & 38,321,168 b & 38,321,168 b & 21,729,092,080 b & 151,630,216 b \\
\hline \textbf{pla33810} & 1,818,744,456 bytes & 1,818,744,456 bytes & (stack overflow) & (stack overflow)  \\
\hline
\end{tabular}
\caption{Uso de mem\'oria, dado em $10^{6}$ bytes}
\label{tab2}
\end{center}
\end{table}

\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c|c|c|c|} \hline
&\multicolumn{4}{|c|}{Fun\c c\~ao} \\
\hline Conj. de ptos & \textbf{NN} & \textbf{FRP} & \textbf{Greedy} & \textbf{PQGreedy} \\
\hline \hline \textbf{att48} & 1.2089 & 1.8216 & 1.1980 & 1.1980 \\
\hline \textbf{kroA100} & 1.2617 & 1.8874 & 1.1368 & 1.1368 \\
\hline \textbf{lin105} & 1.4158 & 1.9016 & 1.1661 & 1.1661 \\
\hline \textbf{pr1002} & 2.9926 & 5.0329 & 2.9218 & 2.9594 \\
\hline
\end{tabular}
\caption{Qualidade do tour (raz\~ao entre o melhor tour poss\'ivel e o tour da fun\c c\~ao correspondente)}
\label{tab3}
\end{center}
\end{table}

% \hline \hline \textbf{att48} & 1.20888836171914 & 1.82164812170158 & 1.19796914883162 & 1.19796914883162 \\
% \hline \textbf{kroA100} & 1.26172560101985 & 1.88744756129475 & 1.13679974385868 & 1.13679974385868 \\
% \hline \textbf{lin105} & 1.41575215007234 & 1.90159629747978 & 1.16608712817508 & 1.16608712817508 \\
% \hline \textbf{pr1002} & 2.99256461981464 & 5.03290263101157 & 2.92180784014924 & 2.95944628835971 \\


\section{Conclus\~oes}

A partir da an\'alise dos testes, podemos observar que as heur\'isticas \emph{Nearest Neighbor } e \emph{FRP } s\~ao as melhores em rela\c c\~ao ao tempo e mem\'oria.

\end{document}

% \begin{tabular}{|c||c|c|c|c|c|c|c|c|} \hline
% &\multicolumn{8}{|c|}{N\'umero de pontos} \\
% \hline & \textbf{att48} & \textbf{kroA100} & \textbf{lin105} & \textbf{lin318} & \textbf{pr1002} & \textbf{nrw1379} & \textbf{rl1889} & \textbf{pla7397} \\
% \hline \hline \textbf{NN} & 0m0.046s &  &  &  & &  & & \\
% \hline \textbf{FRP} &  &  &  &  &  &  & & \\
% \hline \textbf{GREEDY} &  &  & &  & &  & & \\
% \hline \textbf{PQGREEDY} &  &  &  & & &  & & \\
% \hline
