\begin{center}
\htmladdnormallink{TSLIB: site sobre problemas NP-completo}
{http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/}
\end{center}

Segundo Trabalho Pr\'{a}tico - 27/05/03 


\begin{enumerate}
\item Apresente pelo menos um exemplo pr\'atico (e n\~ao mais do que tr\^es)
que possa ser modelado atrav\'es dos seguintes problemas:
\begin{list}{\alph{cont2})}{\usecounter{cont2}}
\item {\em Bin packing}
\item Cobertura de v\'ertices ({\em vertex cover})
\item Mochila ({\em knapsack})
\item {\em Subset sum}
\item Problema do caixeiro viajante
\end{list}

\bigskip
\item
{\bf Problema}:
Dados um conjunto de cidades $C=\{c_1, c_2, \cdots, c_n\}$ e uma 
dist\^ancia $d(c_i,c_j)$ para cada par de cidades $c_i, c_j \in C$,
encontre o ``roteiro'' para todas as cidades em $C$
cujo comprimento total seja o menor poss\'{\i}vel.
Este problema \'e conhecido na literatura como o problema do caixeiro viajante (PCV).
%Uma vers\~ao um pouco diferente \'e o {\em problema do caixeiro viajante assim\'etrico (PCVA)},
%o qual pode ser descrito como: dados um conjunto de $n$ cidades e dist\^ancias para cada
%par de cidades, encontre um roteiro de comprimento m\'{\i}nimo visitando cada cidade
%exatamente uma vez. No caso do PCVA, a dist\^ancia da cidade $i$ para a cidade  $j$
%e a dist\^ancia da cidade $j$ para a cidade  $i$ podem ser diferentes.

\noindent
{\bf O que fazer}

\begin{list}{\alph{cont2})}{\usecounter{cont2}}
\item
Prove que este problema \'e $\cal NP$-Completo.

\item
Implemente um algoritmo capaz de obter a solu\c{c}\~ao \'otima para este
problema.
Informe o tamanho do maior problema que voc\^e conseguiu obter
a solu\c{c}\~ao \'otima.
Comente o resultado indicando o motivo da limita\c{c}\~ao e faca uma
estimativa do tempo necess\'ario no caso de termos uma entrada 10 vezes maior
 que a do maior problema que voce resolveu.

\item
Implemente uma heur\'{\i}stica (ou aproxima\c{c}\~ao) que resolva
este problema eficientemente e produza ``boas'' solu\c{c}\~oes sob o
ponto de vista pr\'atico.
Apresente uma an\'alise de complexidade de tempo da sua heur\'{\i}stica.
\htmladdnormallink{Use a matriz dispon\'{\i}vel aqui.}{matriz-de-entrada}
Imprima o caminho obtido e seu custo.
As melhores solu\c{c}\~{o}es v\~{a}o ser premiadas com pontos extras. Mais 
especificamente, as 5 melhores solu\c{c}\~{o}es que sejam at\'{e} 
10\% piores (em termos do custo do caminho encontrado) que a melhor obtida.

\item Apresente uma an\'alise indicando o quanto a solu\c{c}\~ao
 heur\'{\i}stica fornecida aproxima-se do resultado \'otimo (voce pode
explicar resultados encontrados na literatura ou ainda apresentar sua
pr\'opria demonstra\c{c}\~ao).

\item Realize testes com entradas escolhidas aleatoriamente e
compare os resultados com a an\'alise de efici\^encia apresentada no item
anterior. Comente os resultados obtidos e discuta o qu\~ao pr\'oxima a
an\'alise te\'orica est\'a da realidade.

\item Submeta eletronicamente a implementa\c{c}\~ao da solu\c{c}\~ao \'otima
utilizando como entrada de dados a seguinte matriz:

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
    -  & 3 &  5 & 48 & 48 &  8 &  8 \\ \hline 
    3  & - &  3 & 48 & 48 &  8 &  8 \\ \hline 
    5  & 3 &  - & 72 & 72 & 48 & 48 \\ \hline 
   48  &48 & 72 &  - &  O &  6 &  6 \\ \hline 
   48  &48 & 72 &  O &  - &  6 &  6 \\ \hline 
    8  & 8 & 48 &  6 &  6 &  - &  O \\ \hline 
    8  & 8 & 48 &  6 &  6 &  O &  - \\ \hline 
\end{tabular}
\end{center}

\item Apresente a documenta\c{c}\~ao das implementa\c{c}\~oes realizadas
(veja aqui maiores detalhes sobre
\htmladdnormallink{instru\c{c}\~oes para a entrega de trabalhos praticos).}{../entrega}
\end{list}

\end{enumerate}

\bigskip\noindent
{\bf Refer\^encias\/:}
[CLR], [HS], [GJ], [L], [S], [Z]

\end{document}