\documentclass[11pt]{article}
\usepackage[brazil]{babel}
\title{T\'ecnicas de Busca e Ordena\c{c}\~ao\\ Trabalho 0 2004/02\\
Analise de Algoritmo e Analise de Desempenho }
\author{Paulo Sergio dos Santos Junior \and Cleverton Lopes Silva}

\begin{document}
\maketitle
Neste documento contem os testes de desempenho das heuristicas apresentadas no trabalho.  

\section{Teste de desempenho das Heuristicas}

Abaixo temos o conjunto de tabelas que representam a nossa analise de desempenho para cada heuristica desenvolvida
no trabalho.

\begin{center}
\begin{tabular}{|l||c|c|c|c|c|}
\hline
\multicolumn{5}{|c|}{\textbf{Analise feita sobre o arquivo att48.tsp.gz}}\\
\hline
Heuristicas    &Nn  &Frp &Greedy &PqGreedy \\
\hline\hline
Razao      &1,2989    &1,6181    &1,2815  & 1,2186  \\
\hline
Tempo (s)   &0,273    &0,528    &0,226    &0,541   \\
\hline
\end{tabular}
\end{center}


\begin{center}
\begin{tabular}{|l||c|c|c|c|c|}
\hline
\multicolumn{5}{|c|}{\textbf{Analise feita sobre o arquivo a280.tsp.gz}}\\
\hline
Heuristicas    &Nn  &Frp &Greedy &PqGreedy \\
\hline\hline
Razao      &1,232    &1,869    &1,21  & -  \\
\hline
Tempo (s)   &0,796    &0,343    &1,485   -   \\
\hline
\end{tabular}
\end{center}


\begin{center}
\begin{tabular}{|l||c|c|c|c|c|}
\hline
\multicolumn{5}{|c|}{\textbf{Analise feita sobre o arquivo pr1002.tsp.gz}}\\
\hline
Heuristicas    &Nn  &Frp &Greedy &PqGreedy \\
\hline\hline
Razao      &3,127    &4,771    &3,154  & -  \\
\hline
Tempo (s)   &5,087    &0,6    &28,874    & -   \\
\hline
\end{tabular}
\end{center}


\begin{center}
\begin{tabular}{|l||c|c|c|c|c|}
\hline
\multicolumn{5}{|c|}{\textbf{Analise feita sobre o arquivo lin105.tsp.gz}}\\
\hline
Heuristicas    &Nn  &Frp &Greedy &PqGreedy \\
\hline\hline
Razao      &1,415    &1,978    &1,527  & -  \\
\hline
Tempo (s)   &0,25    &0,239    &0,293    & -   \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|l||c|c|c|c|c|}
\hline
\multicolumn{5}{|c|}{\textbf{Analise feita sobre o arquivo kroA100.tsp.gz}}\\
\hline
Heuristicas    &Nn  &Frp &Greedy &PqGreedy \\
\hline\hline
Razao      &1,245    &1,804    &1,364  & 1,4310  \\
\hline
Tempo (s)   &0,18    &0,223    &0,304    &0,307   \\
\hline
\end{tabular}
\end{center}


\section{Testes de Correcao}
Testes de correcao das estruturas contidas no trabalho.
\subsection{KDtree} 
Teste relacionado a kdtree  - exercicio 3.
Abaixo temos possiveis arvores: 
\begin{itemize}
\item Arvore1 = Null 
\item Arvore2 = Leaf [Ponto (1,0) True,Ponto (2,2) False] 
\item Arvore3 = Node True 2 True (Node False 2 True (Leaf [Ponto (1,0) True,Ponto (2,2) False]) Null) (Node False 2 True (Leaf [Ponto (3,0) True,Ponto (4,1) False]) Null) 
\item Arvore4 = Node True 2 True (Leaf [Ponto (1,0) True,Ponto (2,2) False]) (Leaf [Ponto (3,0) True,Ponto (1,2) False])
\item Arvore5 = build pr1002
\item Arvore6 = build a280
\item Arvore7 = build att48
\end{itemize}


\begin{center}
\begin{tabular}{|l||c|c|c|c|c|}
\hline
\multicolumn{3}{|c|}{\textbf{Analise feita  pelo iskdtree}}\\
\hline
Arvores    &False  &True \\
\hline\hline
Arvore1      &   &X    \\
\hline
Arvore2   &    &X    \\
\hline
Arvore3     &     &X      \\
\hline
Arvore4     & X    &      \\
\hline
Arvore5     &     & X     \\
\hline
Arvore6     &     & X     \\
\hline
Arvore7     &     & X     \\
\hline


\end{tabular}
\end{center}




\subsection{Binpq} 
\subsubsection{Teste da isBinpq} 
Teste relacionado a Binpq  - exercicio 6.
Valores Assumidos para o teste na funcao isbinpq.
Abaixo temos possiveis arvores: 

\begin{itemize}
\item tree1 = Vazio
\item tree2 = No 2 Vazio Vazio
\item tree3 = No 2 (No 3 Vazio Vazio) (No 4 Vazio Vazio)
\item tree4 = No 2 (No 3 Vazio Vazio) (No 1 Vazio Vazio)
\item tree5 = build pr1002
\item tree6 = build a280
\item tree7 = build att48
\end{itemize}


\begin{center}
\begin{tabular}{|l||c|c|c|c|c|}
\hline
\multicolumn{3}{|c|}{\textbf{Analise feita  pelo iskdtree}}\\
\hline
Arvores    &False  &True \\
\hline\hline
tree1      &   &X    \\
\hline
tree2   &    &X    \\
\hline
tree3     &     &X      \\
\hline
tree4     & X    &      \\
\hline
tree5     &     & X     \\
\hline
tree6     &     & X     \\
\hline
tree7     &     & X     \\
\hline

\end{tabular}
\end{center}

\subsubsection{Teste das Funcoes} 
Teste relacionado as funcoes Binpq. 


\begin{center}
\begin{tabular}{|l||c|c|c|c|c|}
\hline
\multicolumn{2}{|c|}{\textbf{Funcao insert }}\\
\hline
Tempo (s)   &0,01     \\
\hline
Memoria &531548  (bytes)     \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|l||c|c|c|c|c|}
\hline
\multicolumn{2}{|c|}{\textbf{Funcao delmin }}\\
\hline
Tempo (s)   &0,01     \\
\hline
Memoria &531548  (bytes)     \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|l||c|c|c|c|c|}
\hline
\multicolumn{2}{|c|}{\textbf{Funcao merge }}\\
\hline
Tempo (s)   &0,01     \\
\hline
Memoria &  799700 (bytes)     \\
\hline
\end{tabular}
\end{center}


\begin{center}
\begin{tabular}{|l||c|c|c|c|c|}
\hline
\multicolumn{2}{|c|}{\textbf{Funcao findmin }}\\
\hline
Tempo (s)   &0,01     \\
\hline
Memoria &531548  (bytes)     \\
\hline
\end{tabular}
\end{center}


\subsection{Tour} 
Teste relacionado a isTout .
Abaixo temos possiveis arvores: 

\begin{itemize}
\item nn(a280)
\item nn(pr1002)
\end{itemize}


\begin{center}
\begin{tabular}{|l||c|c|c|c|c|}
\hline
\multicolumn{3}{|c|}{\textbf{Analise do IsTour}}\\
\hline
Tour    &False  &True \\
\hline\hline
nn(a280)      &   &X    \\
\hline
nn(pr1002)    &    &X    \\
\hline
\end{tabular}
\end{center}

\end{document}
