\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{Evandro Ferreira de Oliveira}

\begin{document}
\maketitle
  Estes algoritmos for\~ao desenvolvidos pelas Heuristicas
   propostas pelo professor
  na especifica\c{c}\~ao do trab01.
  \\A analise de complexidade de um algoritmo juntamente com
  o estudo de rendimento
  e desempenho do um programa levanos a tirar comclu\c{c}\~oes,
  sobre como e qual a
  melhor forma de estabelecermos uma determinada estrutura.


\section{Analise}


  Este documento foi organizado de maneira em que seja expl\'icito
  como foi
  feita toda a an\'alise dos c\'odigos em quest\~ao.



\section{Pr\'ologo}

Aqui vamos ter uma relat\'orio dos teste feitos com as
fun\c{c}\~oes :


	nn       [Point a] \\
	frp      [Point a] \\
	greedy   [Point a] \\
	pqgreedy [Point a] \\

Usamos para comparar as fun\c{c}\~oes os seguintes crit\'erios: \\

	1- Compara\c{c}\~ao usando o teste que o professor
        disponibilizou na p\'agina dele; \\
	2- Peso das fun\c{c}\~oes com um determinado conjunto
         de pontos, o que nos da, o tamanho do tour; \\
	2- Uso de bytes: quantidade de bytes que s\~ao
        usados para executar toda a fun\c{c}\~ao (interpretada); \\
	3- Tempo com que as fun\c{c}\~oes  sao executadas
         em um Pc comum. \\

O conjunto de Testes formado pelos seguinte pontos: \\


pontos = definido como sendo 48 pontos aleat\'orios; \\
pontos2 = definido como sendo 168 pontos escolhidos
aleat\'oraimente; \\
pontos280 = definido como sendo 279 pontos escolhidos
aleat\'oraimente; \\
pontos1000 = definido como sendo 1002 pontos escolhidos
aleat\'oraimente; \\

E tamb\'em pela fun\c{c}\~ao que calcula o peso do tour,
que ser\'a dada por: \\



\section{Resultado da vers\~ao interpretada}


 Dos testes realizados apresentamos os seguintes resultados: \\


\begin{center}
\begin{tabular}{|l||c|c|c|c|c|}
\hline
\multicolumn{3}{|c|}{\textbf{Ponto}} \\
\hline
Parametros    &peso do Tour  &tempo do Tour   &Memoria\\
\hline\hline
nn            &70329550      &0,09 s   &4860872 bytes \\
\hline
frp           &50864877      &0,10 s   &5328092 bytes \\
\hline
greedy        &339365412     &0,19 s   &4409360 bytes \\
\hline
pqgreedy      &465737800     &0,12 s   &263640 bytes \\
\hline
\end{tabular}
\end{center}



\begin{center}
\begin{tabular}{|l||c|c|c|c|c|}
\hline
\multicolumn{3}{|c|}{\textbf{Ponto 2}}\\
\hline
Parametros    &peso do Tour  &tempo do Tour   &Memoria\\
\hline\hline
nn            &76886049      &1,21 s  &62720456 bytes\\
\hline
frp           &77079562      &1,58 s  &76921396 bytes\\
\hline
greedy        &883810059     &3,79 s  &125701876 bytes\\
\hline
pqgreedy      &1050793086    &0,02 s  &658940 bytes\\
\hline
\end{tabular}
\end{center}

 \begin{center}
\begin{tabular}{|l||c|c|c|c|c|}
\hline
\multicolumn{3}{|c|}{\textbf{Ponto 280}}\\
\hline
Parametros    &peso do Tour  &tempo do Tour   &Memoria\\
\hline\hline
nn      &67096    &4,28 s      &210137792 bytes\\
\hline
frp   &73200    &4,72 s        &228066216 bytes\\
\hline
greedy     &675896  &16,01 s   &685817964 bytes\\
\hline
pqgreedy     &1575160  &0,03 s &1072780 bytes\\
\hline
\end{tabular}
\end{center}

 \begin{center}
\begin{tabular}{|l||c|c|c|c|c|}
\hline
\multicolumn{3}{|c|}{\textbf{Ponto 1000}}\\
\hline
Parametros    &peso do Tour  &tempo do Tour  &Memoria\\
\hline\hline
nn            &234639822     &89,78 s   & -\\
\hline
frp           &324341602     &81,35 s  & -\\
\hline
greedy        &13910035312   &538,9 s  & -\\
\hline
pqgreedy      &25458159762   &0,12 s  &5122312 bytes\\
\hline
\end{tabular}
\end{center}

\subsection{Testes de corre\c{c}\~ao da Kdtree}

\begin{center}
\begin{tabular}{|l||c|c|c|c|c|}
\hline
\multicolumn{3}{|c|}{\textbf{Corre\c{c}\~ao}} \\
\hline
Parametros    &Resultado  &Tempo  &Memoria \\
\hline\hline
pontos        &True     &0.00 s   &301708 bytes \\
\hline
pontos2       &True     &0.01 s   &563788 bytes \\
\hline
pontos280     &True     &0.02 s   &770672 bytes \\
\hline
pontos1000    &True     &0.10 s   &4171556 bytes \\
\hline
\end{tabular}
\end{center}


\section{Vers\~ao compilada e teste comparativos}

  Na vers\~ao compilada, o peso dos Tour's permanece
   o mesmo, no entanto \\
o tempo de execucao de uma fun\c{c}\~ao e reduzido,
 como podemos ver a seguir: \\


\begin{center}
\begin{tabular}{|l||c|c|c|c|c|}
\hline
\multicolumn{2}{|c|}{\textbf{Ponto}}\\
\hline
Parametros &tempo de execu\c{c}\~ao  &rela\c{c}\~ao com o interpretado \\
\hline\hline
nn           &0.08 s       &11\% a menos \\
\hline
frp           &0.07 s       &30\% a menos \\
\hline
greedy        &0.07 s       &63\% a menos \\
\hline
pqgreedy      &0.004s       &96,6\% a menos \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|l||c|c|c|c|c|}
\hline
\multicolumn{2}{|c|}{\textbf{Ponto 2}}\\
\hline
Parametros &tempo de execu\c{c}\~ao &rela\c{c}\~ao com o interpretado \\
\hline\hline
nn            &0.49 s          &59,5\% a menos \\
\hline
frp           &0.62 s          &60,7\% a menos \\
\hline
greedy        &0.98 s          &74,1\% a menos \\
\hline
pqgreedy      &0.023s          &15,0\% a menos \\
\hline
\end{tabular}
\end{center}

 \begin{center}
\begin{tabular}{|l||c|c|c|c|c|}
\hline
\multicolumn{2}{|c|}{\textbf{Ponto 280}}\\
\hline
Parametros &tempo de execu\c{c}\~ao &rela\c{c}\~ao com o interpretado \\
\hline\hline
nn              &1.72 s          &59,8\% a menos\\
\hline
frp             &1.95 s          &58,7\% a menos \\
\hline
greedy          &5.97 s          &62,7\% a menos \\
\hline
pqgreedy        &0.017s          &43,3\% a menos \\
\hline
\end{tabular}
\end{center}

 \begin{center}
\begin{tabular}{|l||c|c|c|c|c|}
\hline
\multicolumn{2}{|c|}{\textbf{Ponto 1000}}\\
\hline
Parametros &tempo de execu\c{c}\~ao  &rela\c{c}\~ao com o interpretado \\
\hline\hline
nn            &37.958s                &57,7\% a menos \\
\hline
frp           &32.060s                &60,6\% a menos \\
\hline
greedy        &2m.52,3s               &68,0\% a menos \\
\hline
pqgreedy      &0.083s                 &30,8\% a menos \\
\hline
\end{tabular}
\end{center}




\section{Conclus\~oes}
Das Heuristicas usadas para calcular o Tour vamos obter
as seguintes conclus\~oes:


1- Na heuristica nn podemos observar que para o conjunto
 "pontos" o tour obtido é um tour com o peso consider\'avel,
  bem como o teste com "pontos2" e com "pontos1000", no
  entanto o teste com "pontos280" nos d\'a um tour muito
   bom em rela\c{c}\~ao aos demais testes feitos.
   O que nos leva a concluir que a heuristica nn do jeito
   que foi empregada ser\'a melhor utilizada no calculo
de um conjunto de 100 a 900 pontos, sendo que h\'a uma
margem de erro nesse calculo estimado. \\

2- Na heuristica frp podemos observar que para o conjunto
"pontos" o tour obtido é um tour com o peso consider\'avel,
 bem como o teste com "pontos2" e com "pontos1000", no entanto o
teste com "pontos280" nos d\'a um tour muito bom em
rela\c{c}\~ao aos demais testes feitos. O que nos leva
a concluir que a heuristica frp do jeito que foi empregada
 ser\'a melhor utilizada no calculo de um conjunto
 de 100 a 900 pontos, sendo que h\'a uma margem de erro
 nesse calculo estimado. \\

3- Na heuristica greedy podemos observar que para
 o conjunto "pontos" o tour obtido é um tour com o
  peso consider\'avel, bem como o teste com "pontos2"
   e com "pontos1000", no entanto o teste com "pontos280"
    nos d\'a um tour muito bom em rela\c{c}\~ao aos
    demais testes feitos. O que nos leva a concluir
    que a heuristica greedy do jeito que foi empregada
     ser\'a melhor utilizada no calculo de um conjunto
      de 100 a 900 pontos, sendo que h\'a uma margem de
       erro nesse calculo estimado. \\

4- Na heuristica pqgreedy podemos observar que para o
conjunto "pontos" o tour obtido é um tour com o peso
consider\'avel, bem como o teste com "pontos2" e com
 "pontos1000", no entanto o teste com "pontos280" nos
  d\'a um tour muito bom em rela\c{c}\~ao aos demais
  testes feitos. O que nos leva a concluir que a heuristica
   pqgreedy do jeito que foi empregada ser\'a melhor utilizada
    no calculo de um conjunto de 100 a 900 pontos, sendo
     que h\'a uma margem de erro nesse calculo estimado.
      Devemos tamb\'e relatar que a pqgreedy n\~ao atingiu
       os objetivos por nos pretendidos. \\

\section{Tabela de relacionamentos}


\begin{center}
\begin{tabular}{|l||c|c|c|c|c|}
\hline
\multicolumn{3}{|c|}{\textbf{Ponto 1000}}\\
\hline
Parametros    &pontos para pontos2   &pontos2 para pontos280   &pontos280 para pontos1000 \\
\hline\hline
nn            &piora de 9,32\%       &melhora de 99,91\%       &piora de 99,97\% \\
\hline
frp           &piora de 34,00\%      &melhora de 99,90\%       &piora de 99,97\% \\
\hline
greedy        &piora de 61,60\%      &melhora de 99,92\%       &piora de 93,65\% \\
\hline
pqgreedy      &piora de 55,67\%      &melhora de 99,85\%       &piora de 99,99\% \\
\hline
\end{tabular}
\end{center}


\end{document}
