%\documentclass[dvips,12pt]{amsart}
\documentclass[pdftex,12pt]{amsart}
\usepackage{amsmath}
\usepackage[portuges]{babel}
\usepackage{enumerate}

\usepackage{hyperref}
\def\hbref#1#2#3{\href{#1#2}{#3}}

\def\crseurl{http://www.inf.ufes.br/~raulh/ufes/teaching/courses/lpii}

\def\cwurl{\crseurl/page/cw/1/}

\input{defport}
\input{deflogic}
\input{defseqs}
\input{deftrees}
\def\stb#1#2{\ensuremath{st.#1.b.#2}}
\def\xstb#1#2#3{\ensuremath{\stb#1#2=\langle#3\rangle}}
\def\xoldstb#1#2#3{\ensuremath{#1\in\stb#2#3}}

\def\stdin{\emph{stdin}}
\def\stdout{\emph{stdout}}
\def\tarball{\emph{tarball}}
\def\mailto#1{\href{mailto:#1}{#1}}
\title{Trabalho 1: \\ Busca combinatorial \\
       Draft 0}

\author{Raul H.C. Lopes}
\def\radixsort{\emph{radix sort}}
\def\splitter{\emph{splitter}}
\def\quicksort{\emph{quick sort}}
\def\mergesort{\emph{merge sort}}
\def\prefsum{prefix sum}
\def\real{Real}


\def\scref#1{sc. \ref{#1}}
\def\exref#1{ex. \ref{ex:#1}}
\def\tabref#1{tab. \ref{tab:#1}}

\begin{document}

\maketitle

\section{Preliminares}
\def\tsp{\textbf{TSP}}
\def\tour{\textbf{tour}}
Neste trabalho voc\^e exercitar\'a o seu conhecimento de busca em \'arvores 
combinatoriais de pesquisa. O objetivo consistir\'a em implementar uma
heur\'{\i}stica para melhorar um  \tour\ solu\c{c}\~ao de um \tsp.

Este trabalho \'e estritamente individual.

\def\xpair#1#2{\ensuremath{(#1,#2)}}
\def\xdist#1#2{\ensuremath{dist(#1,#2)}}

\section{O Problema do Caixeiro Viajante}\label{graphs:tsp}
Os exerc\'{\i}cios deste trabalho lidam com o \emph{Problema do Caixeiro
Viajante}, \emph{Traveling Salesman Problem}, de agora em diante chamado \tsp.
Este problema demanda encontrar o caminho mais curto para visitar cada cidade
de um conjunto dado exatamente uma vez e retornar ao ponto de partida. Para 
representar cidades, usaremos uma abstra\c{c}\~ao: um grafo n\~ao dirigido.

Um grafo n\~ao dirigido \'e um par \xpair VE, onde $V$ \'e um conjunto de pontos
e $E$ \'e um conjunto de pares de pontos, cada par de pontos sendo chamado de 
arestas. Para nosso trabalho valem as seguintes restri\c{c}\~oes:
\begin{itemize}
	\item uma aresta \xpair uv indica que existe uma conex\~ao direta do
		ponto $u$ ao ponto $v$;
	\item o grafo \'e geom\'etrico: os pontos s\~ao elementos 
		de um espa\c{c}o 
		Euclideano de duas dimens\~oes;
	\item as coordenadas dos pontos s\~ao pares de inteiros positivos;
	\item para qualquer par de pontos $u$ e $v$ do grafo existe uma  aresta 
		\xpair uv, que tem um custo associado
		dado pela dist\^ancia entre $u$ e $v$;
	\item o grafo \'e n\~ao direcionado e a exist\^encia de uma aresta 
		\xpair uv indica a exist\^encia de outra aresta \xpair vu com
		mesmo custo que a primeira.
\end{itemize}

Um caminho em um grafo \'e uma seq\"u\^encia de pontos do mesmo. Um circuito
Hamiltoniano $C$
\'e uma seq\"u\^encia de pontos com as seguintes restri\c{c}\~oes:
\begin{itemize}
	\item cada ponto do grafo inicial figura exatamente uma vez no circuito;
	\item o circuito indica a seq\"u\^encia de pontos a visitar para sair
		de um v\'ertice inicial, o primeiro da seq\"u\^encia dado, ir
		at\'e o \'ultimo v\'ertice da seq\"u\^encia, visitando todos os
		outros na ordem dada por $C$, e voltar ao ponto de partida.
\end{itemize}

Um circuito Hamiltoniano, que chamaremos simplemente de \tour,
consiste em uma
permuta\c{c}\~ao do conjunto de pontos de grafo dado. Assumindo que $C!i$ denote
o i-\'esimo elemento do tour $C$, o custo do tour \'e dado por:
$$ cost.C = \bnd{+}{i}{\lelt 0i{n-1}}{\xdist{C!i}{C!(i+1)}}+\xdist{C!(n-1)}{C!0}$$

onde $\xdist uv$ \'e a dist\^ancia geom\'etrica de $u$ a $v$.

O problema do \tsp, como colocado neste trabalho, consiste, ent\~ao, em
determinar o \tour\ de menor custo.


\def\hrefstspds#1{\href{http://portal.acm.org/citation.cfm?id=313668}#1}


\def\kopt{\emph{k-opt}}
\def\SC{\textbf{Senhor do Castelo}}
A heur\'{\i}stica \kopt\ usa como passo b\'asico a retirada de $k$ arestas 
n\~ao consecutivas de um \tour\ previamente
constru\'{\i}do e inser\c{c}\~ao de $k$ novas arestas, produzindo um novo \tour\
de peso menor do que o inicial. Esse passo \'e repetido at\'e explorar todas
as alternativas de remo\c{c}\~ao de $k$ arestas que possam melhorar o \tour.
Note que:
\begin{itemize}
	\item o valor de $k$ permanece fixo durante uma execu\c{c}\~ao completa
		de \kopt.
	\item um conjunto de arestas s\'o \'e removido para a inser\c{c}\~ao de
		novas arestas se o novo \tour\ for melhor.
\end{itemize} 

O \hrefstspds{artigo} descreve a heur\'{\i}stica \kopt\ e apresenta sugest\~oes
de estruturas para implement\'a-la de forma eficiente.


\section{Os exerc\'{\i}cios}\label{exs}

\begin{ex}
	\label{ex:kopt} Implemente em Haskell um programa para c\'alculo de
	\tour\ do \tsp\ que use a heur\'{\i}stica \kopt.
\end{ex}

\begin{ex}
	\label{ex:monad}
	Implemente em Haskell, usando \emph{monads} ou \emph{threads} para
	sincronizar a busca na \'arvore, um programa para c\'alculo de
	\tour\ do \tsp\ que use a heur\'{\i}stica \kopt.
\end{ex}

\begin{ex}
	\label{ex:test} Apresente testes comparativos sobre:
	\begin{itemize}
		\item melhora da qualidade de \tour\ obtida;
		\item efici\^encia comparada das duas heur\'{\i}sticas.
	\end{itemize}
\end{ex}

\section{Defini\c{c}\~ao do n\'umero de cr\'editos}\label{credits}

O n\'umero de cr\'editos atribu\'{\i}dos a cada exerc\'{\i}cio est\'a definido 
na \tabref{credits}. Note que os cr\'editos atribu\'{\i}dos aos exerc\'{\i}cios
de teste de desempenho e corre\c{c}\~ao das diferentes estruturas depender\~ao
da apresenta\c{c}\~ao de artigo em \LaTeX, apresentando tabelas comparativas 
e conclus\~oes dos experimentos realizados por cada grupo. N\~ao hesite em
discutir com outros colegas (de outros grupos) o tipo de teste a realizar. N\~ao
ser\'a considerado pl\'agio mais de um grupo apresentar extamente os mesmos
testes e at\'e estrutura de artigo. Ser\'a certamente pl\'agio coincid\^encia
em excesso nos resultados de testes! Em resumo, d\^e desde o in\'{\i}cio do
trabalho \^enfase especial \`a escrita do artigo.

\def\exval#1#2{\exref{#1} & $#2$}
\begin{table}
	\centering
	\begin{tabular}{|l|r|}\hline
		Tarefa & Valor \\ \hline
		\exval{kopt}{40} \\
		\exval{monad}{20}\\
		\exval{test}{20}\\
		desempenho & 20 \\\hline
	\end{tabular}\\[\baselineskip]
	\caption{Tabela de Cr\'editos por Tarefa}
	\label{tab:credits}
\end{table}

O \'ultimo item da tabela refere-se \`a qualidade que ser\'a aferida usando
os seguintes princ\'{\i}pios:
\begin{itemize}
	\item cada aluno indicar\'a no respectivo artigo o programa $P$ 
		em que quer ser avaliado;
	\item $P$ receber\'a um cr\'edito de qualidade em uma s\'erie de testes
		definidos pelo \SC;
	\item o cr\'edito de qualidade de um teste ser\'a dado pela divis\~ao
		do tempo gasto no teste pelo valor da melhora da qualidade do
		\tour\ obtido;
	\item $P$ receber\'a como valor final de qualidade a m\'edia dos
		cr\'editos de qualidade obtidos;
	\item o aluno melhor classificado receber\'a $20$ cr\'editos de
		desempenho; os outros receber\~ao cr\'editos proporcionais
		\`a raz\~ao da qualidade respectiva pela qualidade
		do melhor trabalho.
\end{itemize}


\section{A submiss\~ao para corre\c{c}\~ao}\label{submit}
\def\exref#1{exerc\'{\i}cio \ref{ex:#1}}
\def\haskell{\textbf{Haskell}}
\def\makefile{\textbf{Makefile}}
\def\frp{\textbf{frp}}

Submeta seu trabalho por \href{mailto:raulh@inf.ufes.br}{e-mail} entre os dias
05/08/05 e/ou 06/08/05. Trabalhos submetidos fora dessa data ser\~ao
considerados nulos.

A mensagem de submiss\~ao do seu trabalho dever\'a conter:
\begin{itemize}
	\item \textbf{Subject:} \textbf{lpii.tp1}
	\item \textsl{Attachment}: \textbf{tp1.tar.bz2}
\end{itemize}

O corpo da mensagem ser\'a desprezado. O arquivo anexado dever\'a ser
obrigatoriamente denominado 

\centerline{\textbf{tp1.tar.bz2}}

e conter\'a todo os fontes necess\'arios para compilar  seu trabalho pr\'atico,
incluindo fontes em \LaTeX, \haskell, \makefile e arquivo de
identifica\c{c}\~ao. 

As seguintes regras devem ser rigorosamente seguidas:
\begin{itemize}
	\item Nenhum compilado deve ser enviado.
	\item O \tarball\ do seu trabalho conter\'a a seguinte estrutura:
		\begin{itemize}
			\item arquivo de \textbf{id}

				Conter\'a uma linha inicial com \emph{e-mail}
				de contato do grupo e, depois, uma linha de
				identifica\c{c}\~ao para elemento do grupo,
				contendo n\'umero de matr\'{\i}cula e nome
				completo separados por '\textbf{:}' (dois
				pontos.) Por exemplo:

				\begin{verbatim}
				jolero@gmail.com
				99900089:Ze' do lero 
				\end{verbatim}
			\item arquivo \textbf{Makefile}
			\item diret\'orio \textbf{doc}

				Conter\'a os fontes de toda a documenta\c{c}\~ao 
				do trabalho.
		\end{itemize}
	\item seu \tarball\ ser\'a aberto e compilado com as seguintes linhas:

		\begin{verbatim}
		tar -jxf tp0.tar.bz2
		make all
		\end{verbatim}

		Essas linhas gerar\~ao os seguintes arquivos:

		\begin{itemize}
			\item \textbf{kopt}

				Execut\'avel que implementa heur\'{\i}stica do
				\exref{kopt}.
			\item \textbf{monad}

				Execut\'avel que implementa heur\'{\i}stica do
				\exref{monad}.
			\item \textbf{artigo.pdf}

				Artigo em formato \textbf{PDF}, que avalia 
				qualidade de \tour\ e desempenho dos algoritmos.

		\end{itemize}
\end{itemize}

\end{document}

