\documentclass[11pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}
\usepackage{pifont}
\setlength{\textheight}{8.5in}
\setlength{\textwidth}{6.5in}
\setlength{\evensidemargin}{0pt}
\setlength{\oddsidemargin}{0pt}
\setlength{\topmargin}{-30pt}

\def\risonho{{$\bigcirc\!\!\!\!\!\lower.02cm\hbox{\vbox{\offinterlineskip\hbox{$\>\!..$}\vskip.07cm\hbox{$\scriptscriptstyle\smile$}}}$}}
\def\tristonho{{$\bigcirc\!\!\!\!\!\lower.02cm\hbox{\vbox{\offinterlineskip\hbox{$\>\!..$}\vskip.07cm\hbox{$\scriptscriptstyle\frown$}}}$}}


\begin{document}
\noindent
{\footnotesize {\sc MAC--IME--USP}} \hfill {\footnotesize {\sc Carlos Eduardo Ferreira}}

\vspace{-1mm}
\hfill {\footnotesize {\sc Sala 297A Tel.: 818 6140}}

\vspace{-1mm}
\hfill {\footnotesize {\sc e-mail} cef@ime.usp.br}

\vspace{1cm}

\begin{center}
{\large\bf MAC 323 -- Estruturas de Dados}
\end{center}

\begin{center}
{\bf Primeiro semestre de 1998}
\end{center}

\begin{center}
{\large  Exercício-Programa 5 (e último!!) -- Entrega: {\bf 22 de junho}}

\vspace{0.3cm}
TSP: Tomando Sem Parar
\end{center}

Cacá, Bruno e Tiago estavam com um problema terrível. Reunidos no fim da tarde
na lanchonete do Sandrinho, eles olhavam desolados para os convites de festas
que tinham recebido. O CAMAT havia recebido convites de
vários centros acadêmicos convidando os alunos do IME para participar de
festas que ocorreriam no campus. Só que, em um cúmulo de falta de organização
entre os diversos CA's (e também em mais demonstração da verdade da Lei de
Murphy), todas as festas ocorriam no mesmo dia. 

Preocupados em garantir a presença dos alunos do IME em todas as 30 festas
(eram festas em vários institutos!!) os três começaram a tentar pensar no
melhor jeito de sair do IME, passar por todas as festas (sem repetição!) 
e chegar (inteiro, já
que sóbrio seria difícil de garantir) de volta ao IME
fazendo o caminho mais curto possível (economizando assim o tempo gasto no 
caminho entre as festas). 

Depois de perguntar a vários colegas, que logo perceberam o interesse
acadêmico da questão {\risonho } nossos intrépidos colegas começaram a
perceber que um algoritmo para resolver tal problema poderia ter várias outras
aplicações. Por exemplo, os engravatados Denis e Clayton logo disseram que 
poderiam usar o algoritmo para percorrer todas as aulas que eles tinham de
frequentar no dia, mais seus locais de trabalho e a volta. Outros, como o
Jojô, AB', Atchim, Klot, Marcio  
e o Telmo já pensaram em usar o programa para implementar alguma tática
inovadora em handebol, futsal, basquete ou vôlei, que pudesse salvar alguma
de nossas equipes do fracasso total da Copa União. 

O pessoal do truco também se interessou, afinal poderiam economizar tempo no
caminho entre as diversas salas ``visitadas'' durante as aulas e poderiam se
concentrar mais no jogo que os alunos do IME levam quase à perfeição (os
professores continuam imbatíveis, é claro). O Masaishi e Daniel, da IME{\it
jr}, viram as possibilidades de projetos conjuntos que poderiam surgir, e
ficaram muito intere{\$\$}ados. 

Enfim, a discussão se espalhou pela classe, e o Wagner, Elisângela, Debora 
e Marcelo 
dando uma olhada, disseram em uníssono: ``Ah, isso aí tem a ver com 
Otimização Combinatória\footnote{Interessante área da Computação coberta na
disciplina MAC325, que será oferecida no próximo semestre \risonho.}''. Isso
despertou uma lembrança na cabeça do Bruno: ``O Batata, Eduardo e o 
Cassio {\bf dizem que} estudam isso
aí!!''. 

Primeiro eles conseguiram encontrar o Batata, que ao ouvir o problema disse
que ele sabia resolvê-lo usando algoritmos geriátricos, digo genéticos, mas
agora ele não tinha tempo porque tinha de ir para o trabalho. Quando eles
finalmente acharam o Cassio e o Eduardo, entre uma fase e 
outra do compilador, estes
disseram que o problema que eles estavam querendo resolver era o TSP (Traveling
Salesman Problem), mais especificamente no caso euclidiano (em que a distância
de ir de $a$ para $b$ é sempre menor do que ir de $a$ para $c$ e depois daí
para $b$). Eles comentaram que muita gente já tinha trabalhado no problema, e
tinha um monte de algoritmos escritos para o mesmo. Só para dar uma idéia eles
sugeriram que os três dessem uma olhada nos livros: 
\begin{quote}
E.L.~Lawler, J.K.~Lenstra, A.H.G.~Rinnooy Kan e  D.B.~Shmoys (eds.), \\
{\em The Traveling Salesman Problem}, \\
Wiley, New York, 1985. \\ \\ \\
G. Reinelt, \\
{\em The Traveling Salesman. Computational Solutions for TSP Applications}, \\
Lecture Notes in Computer Science 840, Springer, 1994. 
\end{quote}
onde diversas abordagens eram mostradas, com muitas heurísticas para resolver
o problema. 

Sem tempo de implementar alguma coisa descrita no livro (afinal eles tinham de
fazer os EPs de Estruturas), os três procuraram o
Carlinhos para perguntar se ele tinha algo pronto. Este achou a idéia ótima, e
pensou que poderia fazer um quinto (e último!!) EP com esta estória. 

A idéia deste exercício-programa é implementar alguma heurística ou mesmo
algoritmo exato para a solução do TSP. Você deve fazer um pequeno relatório
descrevendo que estruturas de dados você está usando para armazenar os locais
de festas, que algoritmo você está implementando e que estruturas estão sendo
necessárias para implementar tal algoritmo. O arquivo de entrada terá o número
de locais a serem visitados seguido das coordenadas destes locais. Estarão
disponíveis na área
\begin{quote}
{\tt http://www.ime.usp.br/$\sim$cef/mac323/eps/} 
\end{quote}
algumas instâncias de testes para as quais você poderá testar seu programa. O
melhor programa (que obtiver a melhor solução para as instâncias testadas)
receberá um valioso prêmio. 

\vspace{2cm}
\begin{center}
\begin{tabular}{|c|}
\hline
{\bf Esta é uma obra de ficção. Nomes, locais e datas semelhantes} \\
{\bf com a vida real terão sido mera coincidência. {\risonho} }\\ \\ 
{\Large {\bf Boas férias!}} \\
\hline
\end{tabular}
\end{center}
\end{document}