\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{Trabalho de TBO}

\begin{document}

\maketitle

\section{Testes comparativos}

As se\c c\~oes \ref{sec:kd} e \ref{sec:tsp} deste documento apresentam testes comparativos para as estruturas KD-Tree e \'Arvore bin\'aria de prioridade, e para as heur\'isticas estudadas do Problema do Caixeiro Viajante (TSP). Os testes foram executados em uma m\'aquina Pentium 4, com processador de 2.6GHz e mem\'oria RAM de 1 Gb.

\section{KD-Tree}
\label{sec:kd}

Executamos o algoritmo KDTree para alguns conjuntos de pontos a fim de obter uma tabela com os tempos de execu\c c\~ao de cada conjunto e a quantidade de mem\'oria usada por cada conjunto. Os resultados s\~ao apresentados na tabela \ref{tab0}.\\


\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c|c|} \hline
\multicolumn{3}{|c|}{\textbf{KDTree}} \\
\hline N.ptos & \textbf{Tempo} & \textbf{Mem\'oria} ($10^{5}$ bytes) \\
\hline \hline \textbf{att48} & 0m0.018s   & 8,363 \\
\hline \textbf{kroA100}      & 0m0.027s   & 17,000  \\
\hline \textbf{lin318}       & 0m0.060s   &  54,347 \\
\hline \textbf{pr1002}       & 0m0.154s   & 177,806 \\
\hline \textbf{nrw1379}      & 0m0.212s   & 241,071 \\
\hline \textbf{pla7397}      & 0m1.255s   & 1.415,285 \\
\hline \textbf{pla33810}     & 0m6.165s   & 6.682,207 \\
\hline \textbf{pla85900}     &  0m16.313s & 17,505.565 \\
\hline
\end{tabular}
\caption{Tempo e uso de mem\'oria do m\'odulo KDTree}
\label{tab0}
\end{center}
\end{table}

\section{Heur\'isticas do TSP}
\label{sec: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.012s & 0m0.011s & 0m0.021s & 0m0.018s\\
\hline \textbf{kroA100} & 0m0.019s & 0m0.017s & 0m0.088s & 0m0.031s \\
\hline \textbf{lin105} & 0m0.020s & 0m0.018s & 0m0.091s & 0m0.033s \\
\hline \textbf{lin318} & 0m0.051s & 0m0.042s & 0m1.552s & 0m0.097s \\
\hline \textbf{linhp318} & 0m0.052s & 0m0.042s & 0m1.550s & 0m0.098s \\
\hline \textbf{pr1002} & 0m0.156s & 0m0.125s & 0m37.874s & 0m0.348s \\
\hline \textbf{nrw1379} & 0m0.208s & 0m0.170s & 1m37.220s & 0m0.532s \\
\hline \textbf{C1k} & 0m0.208s & 0m0.170s & 0m39.417s & 0m0.348s \\
\hline \textbf{pla33810} & 0m15.481s & 0m4.978s & (stack overflow) & 2m43.592s \\
\hline
\end{tabular}
\caption{Tempo das heur\'isticas do TSP}
\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 & 2,33 & 2,11 \\
\hline \textbf{kroA100} & 2,40 & 2,40 & 10,84 & 4,80 \\
\hline \textbf{lin105} & 2,57 & 2,57 & 11,62 & 5,22 \\
\hline \textbf{lin318} & 8,38 & 8,38 & 186,83 & 17,90 \\
\hline \textbf{linhp318} & 8,38 & 8,38 & 186,83 & 17,90 \\
\hline \textbf{pr1002} & 27,97 & 27,97 & 4,629,28 & 70,61 \\
\hline \textbf{nrw1379} & 38,32 & 38,32 & 4,629,28 & 103,04 \\
\hline \textbf{Clk} & 30,58 & 30,58 & 4,585,17 & 66,41 \\
\hline \textbf{pla33810} & 1.818,74 & 1.818,74 & (stack overflow) & (stack overflow) \\
\hline
\end{tabular}
\caption{Uso de mem\'oria das heur\'isticas do TSP, 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.2801 \\
\hline \textbf{kroA100} & 1.2617 & 1.8874 & 1.1368 & 1.3600 \\
\hline \textbf{lin105} & 1.4158 & 1.9016 & 1.1661 & 1.1363 \\
\hline \textbf{pr1002} & 2.9926 & 5.0329 & 2.9218 & 2.8999 \\
\hline
\end{tabular}
\caption{Qualidade do tour das heur\'isticas do TSP (raz\~ao entre o melhor tour poss\'ivel e o tour da fun\c c\~ao correspondente)}
\label{tab3}
\end{center}
\end{table}


\section{Conclus\~oes sobre os testes}

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 uso de mem\'oria. Seus valores s\~ao bem parecidos, pois ambas utilizam a estrutura KD-Tree, seja simplesmente como forma de otimiza\c c\~ao (no caso do \emph{NN}), seja como estrutura b\'asica da heur\'istica (\emph{FRP}).

J\'a em rela\c c\~ao ao tour produzido, a heur\'istica \emph{Greedy } foi relativamente melhor do que as outras. Apesar disso, \'e a pior delas em rela\c c\~ao ao tempo e uso de mem\'oria, uma vez que possui como estrutura b\'asica a ordena\c c\~ao de todas as arestas, produzindo um tempo quadr\'atico.

Ou seja, n\~ao foi poss\'ivel obtermos em uma s\'o heur\'istica o melhor tempo e o melhor tour. Talvez, dentre as destacadas, a melhor seja o \emph{PQGreedy}, j\'a que possui tempo e uso de mem\'oria acess\'iveis, e ainda assim, produzem um tour relativamente bom.


\section{Testes de corre\c c\~ao do M\'odulo Binpq}

Esta se\c c\~ao mostra testes de corre\c c\~ao dos operadores utilizados no m\'odulo \textit{Binpq}. Para isso, realizamos diversos testes, de forma a cobrir todas as possibilidades de entrada do programa.

Operadores:
\begin{itemize}
\item{findmin}
\item{delmin}
\item{merge}
\item{insertBinpq}
\end{itemize}

\subsection{Operador \textit{findmin}}

Para o teste do operador \textit{findmin}, utilizamos um conjunto de 5 \'arvores de prioridade: \\
\begin{itemize}
\item{(NodePQ 2 (NodePQ 3 LeafPQ LeafPQ) (NodePQ 4 LeafPQ LeafPQ))}
\item{(NodePQ 2 (NodePQ 3 LeafPQ LeafPQ) LeafPQ)}
\item{(NodePQ 2 LeafPQ (NodePQ 4 LeafPQ LeafPQ))}
\item{(NodePQ 2 LeafPQ LeafPQ)}
\item{LeafPQ}
\end{itemize}

Os resultados foram:

\begin{verbatim}
Binpq> findmin (NodePQ 2 (NodePQ 3 LeafPQ LeafPQ) (NodePQ 4 LeafPQ LeafPQ))
Just 2
Binpq> findmin (NodePQ 2 (NodePQ 3 LeafPQ LeafPQ) LeafPQ)
Just 2
Binpq> findmin (NodePQ 2 LeafPQ (NodePQ 4 LeafPQ LeafPQ))
Just 2
Binpq> findmin (NodePQ 2 LeafPQ LeafPQ)
Just 2
Binpq> findmin LeafPQ
Nothing
\end{verbatim}

Os resultados foram os previstos.

\subsection{Operador \textit{delmin}}

Os mesmos par\^ametros utilizados acima tamb\'em cobrem todas as possibilidades de entrada do operador \textit{delmin}. Vamos aos testes: \\

\begin{verbatim}
*Binpq> delmin (NodePQ 2 (NodePQ 3 LeafPQ LeafPQ) (NodePQ 4 LeafPQ LeafPQ))
NodePQ 3 (NodePQ 4 LeafPQ LeafPQ) LeafPQ
*Binpq> delmin (NodePQ 2 (NodePQ 3 LeafPQ LeafPQ) LeafPQ)
NodePQ 3 LeafPQ LeafPQ
*Binpq> delmin (NodePQ 2 LeafPQ (NodePQ 4 LeafPQ LeafPQ))
NodePQ 4 LeafPQ LeafPQ
*Binpq> delmin (NodePQ 2 LeafPQ LeafPQ)
LeafPQ
*Binpq> delmin LeafPQ
LeafPQ
\end{verbatim}

Obtemos os resultados corretos.

\subsection{Operador \textit{merge}}

Aplicamos as diversas varia\c c\~oes poss\'iveis para \textit{merge} e, como visto no resultado abaixo, as opera\c c\~oes foram conclu\'idas com \^exito.

\begin{verbatim}
*Binpq> merge LeafPQ LeafPQ
LeafPQ
*Binpq> merge LeafPQ (NodePQ 2 LeafPQ LeafPQ)
NodePQ 2 LeafPQ LeafPQ
*Binpq> merge (NodePQ 2 LeafPQ LeafPQ) LeafPQ
NodePQ 2 LeafPQ LeafPQ
*Binpq> merge (NodePQ 2 LeafPQ LeafPQ) (NodePQ 10 LeafPQ LeafPQ)
NodePQ 2 (NodePQ 10 LeafPQ LeafPQ) LeafPQ
*Binpq> merge (NodePQ 10 LeafPQ LeafPQ) (NodePQ 2 LeafPQ LeafPQ)
NodePQ 2 (NodePQ 10 LeafPQ LeafPQ) LeafPQ
*Binpq> merge (NodePQ 2 (NodePQ 3 LeafPQ LeafPQ) LeafPQ) (NodePQ 10 LeafPQ LeafPQ)
NodePQ 2 (NodePQ 10 LeafPQ LeafPQ) (NodePQ 3 LeafPQ LeafPQ)
*Binpq> merge (NodePQ 2 LeafPQ (NodePQ 3 LeafPQ LeafPQ)) (NodePQ 10 LeafPQ LeafPQ)
NodePQ 2 (NodePQ 3 (NodePQ 10 LeafPQ LeafPQ) LeafPQ) LeafPQ
*Binpq> merge (NodePQ 2 (NodePQ 3 LeafPQ LeafPQ) (NodePQ 4 LeafPQ LeafPQ))
        (NodePQ 10 LeafPQ LeafPQ)
NodePQ 2 (NodePQ 4 (NodePQ 10 LeafPQ LeafPQ) LeafPQ) (NodePQ 3 LeafPQ LeafPQ)
*Binpq> merge (NodePQ 10 (NodePQ 13 LeafPQ LeafPQ) LeafPQ) (NodePQ 2 LeafPQ LeafPQ)
NodePQ 2 (NodePQ 10 (NodePQ 13 LeafPQ LeafPQ) LeafPQ) LeafPQ
*Binpq> merge (NodePQ 10 LeafPQ (NodePQ 13 LeafPQ LeafPQ)) (NodePQ 2 LeafPQ LeafPQ)
NodePQ 2 (NodePQ 10 LeafPQ (NodePQ 13 LeafPQ LeafPQ)) LeafPQ
*Binpq> merge (NodePQ 10 (NodePQ 13 LeafPQ LeafPQ) (NodePQ 14 LeafPQ LeafPQ))
        (NodePQ 2 LeafPQ LeafPQ)
NodePQ 2 (NodePQ 10 (NodePQ 13 LeafPQ LeafPQ) (NodePQ 14 LeafPQ LeafPQ)) LeafPQ
*Binpq> merge (NodePQ 2 LeafPQ LeafPQ) (NodePQ 10 (NodePQ 3 LeafPQ LeafPQ) LeafPQ)
NodePQ 2 (NodePQ 10 (NodePQ 3 LeafPQ LeafPQ) LeafPQ) LeafPQ
*Binpq> merge (NodePQ 2 LeafPQ LeafPQ) (NodePQ 10 LeafPQ (NodePQ 3 LeafPQ LeafPQ))
NodePQ 2 (NodePQ 10 LeafPQ (NodePQ 3 LeafPQ LeafPQ)) LeafPQ
*Binpq> merge (NodePQ 2 LeafPQ LeafPQ) (NodePQ 10 (NodePQ 3 LeafPQ LeafPQ)
        (NodePQ 4 LeafPQ LeafPQ))
NodePQ 2 (NodePQ 10 (NodePQ 3 LeafPQ LeafPQ) (NodePQ 4 LeafPQ LeafPQ)) LeafPQ
*Binpq> merge (NodePQ 10 LeafPQ LeafPQ) (NodePQ 2 (NodePQ 3 LeafPQ LeafPQ) LeafPQ)
NodePQ 2 (NodePQ 10 LeafPQ LeafPQ) (NodePQ 3 LeafPQ LeafPQ)
*Binpq> merge (NodePQ 10 LeafPQ LeafPQ) (NodePQ 2 LeafPQ (NodePQ 3 LeafPQ LeafPQ))
NodePQ 2 (NodePQ 3 (NodePQ 10 LeafPQ LeafPQ) LeafPQ) LeafPQ
*Binpq> merge (NodePQ 10 LeafPQ LeafPQ) (NodePQ 2 (NodePQ 3 LeafPQ LeafPQ)
        (NodePQ 4 LeafPQ LeafPQ))
NodePQ 2 (NodePQ 4 (NodePQ 10 LeafPQ LeafPQ) LeafPQ) (NodePQ 3 LeafPQ LeafPQ)
*Binpq> merge (NodePQ 2 (NodePQ 3 LeafPQ LeafPQ) (NodePQ 4 LeafPQ LeafPQ))
         (NodePQ 10 (NodePQ 11 LeafPQ LeafPQ) (NodePQ 12 LeafPQ LeafPQ))
NodePQ 2 (NodePQ 4 (NodePQ 10 (NodePQ 11 LeafPQ LeafPQ) (NodePQ 12 LeafPQ LeafPQ))
         LeafPQ) (NodePQ 3 LeafPQ LeafPQ)
*Binpq> merge (NodePQ 10 (NodePQ 13 LeafPQ LeafPQ) (NodePQ 14 LeafPQ LeafPQ))
         (NodePQ 2 (NodePQ 11 LeafPQ LeafPQ) (NodePQ 12 LeafPQ LeafPQ))
NodePQ 2 (NodePQ 10 (NodePQ 12 (NodePQ 14 LeafPQ LeafPQ) LeafPQ)
         (NodePQ 13 LeafPQ LeafPQ)) (NodePQ 11 LeafPQ LeafPQ)
\end{verbatim}

\subsection{Operador \textit{insertBinpq}}
Este operador insere um elemento em uma \'arvore de prioridade. Seja o seguinte conjunto de entrada: \\

\begin{itemize}
\item LeafPQ  3
\item (NodePQ 3 LeafPQ LeafPQ) 10
\item (NodePQ 3 (NodePQ 4 LeafPQ LeafPQ) LeafPQ) 10
\item (NodePQ 3 LeafPQ (NodePQ 4 LeafPQ LeafPQ) 10
\item (NodePQ 3 (NodePQ 4 LeafPQ LeafPQ) (NodePQ 5 LeafPQ LeafPQ)) 10
\end{itemize}

Veja os resultados obtidos a partir dessas entradas:

\begin{verbatim}
*Binpq> insertBinpq LeafPQ  3
NodePQ 3 LeafPQ LeafPQ
*Binpq> insertBinpq (NodePQ 3 LeafPQ LeafPQ) 10
NodePQ 3 (NodePQ 10 LeafPQ LeafPQ) LeafPQ
*Binpq> insertBinpq (NodePQ 3 (NodePQ 4 LeafPQ LeafPQ) LeafPQ) 10
NodePQ 3 (NodePQ 10 LeafPQ LeafPQ) (NodePQ 4 LeafPQ LeafPQ)
*Binpq> insertBinpq (NodePQ 3 LeafPQ (NodePQ 4 LeafPQ LeafPQ)) 10
NodePQ 3 (NodePQ 4 (NodePQ 10 LeafPQ LeafPQ) LeafPQ) LeafPQ
*Binpq> insertBinpq (NodePQ 3 (NodePQ 4 LeafPQ LeafPQ) (NodePQ 5 LeafPQ LeafPQ)) 10
NodePQ 3 (NodePQ 5 (NodePQ 10 LeafPQ LeafPQ) LeafPQ) (NodePQ 4 LeafPQ LeafPQ)
\end{verbatim}

Os resultados foram os esperados.

\end{document}
