\documentclass[12pt, a4paper]{report}

\pagestyle{empty}
\begin{document}
 
\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill DCC/ICEx/UFMG
 
\noindent {\it Intelig\^encia Artificial}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2001
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent {\bf Segunda Lista de Exerc\'{\i}cios} \hfill Devolu\c c\~ao: 19/02/02

\vspace*{3mm}
Programar e verificar o desempenho do algoritmo $A^*$, com v\'arias fun\c c\~oes heur\'{\i}sticas,
aplicado ao quebra-cabe\c cas de 8 pe\c cas, {\em 8-puzzle\/}. \`Aqueles que preferirem programar em
Prolog recomendo aproveitar o c\'odigo da Figura 12.6, p\'aginas 271-273, do livro texto de Prolog, o
qual pode ser conseguido em www.booksites.net/bratko.

Nos testes considere, pelo menos, os seguintes estados iniciais:

\begin{enumerate}
\item[\ ]
\begin{picture}(94,94) \Large
\put(2,2){\framebox(90,90){}}
\put(0,0){\framebox(94,94){}}
\put(2,32){\line(1,0){90}}
\put(2,62){\line(1,0){90}}
\put(32,2){\line(0,1){90}}
\put(62,2){\line(0,1){90}}

\put(17,77){\makebox(0,0){2}}
\put(47,77){\makebox(0,0){8}}
\put(77,77){\makebox(0,0){3}}
\put(17,47){\makebox(0,0){1}}
\put(47,47){\makebox(0,0){6}}
\put(77,47){\makebox(0,0){4}}
\put(17,17){\makebox(0,0){7}}
\put(77,17){\makebox(0,0){5}}
\end{picture}
\hspace*{1cm}
\begin{picture}(94,94) \Large
\put(2,2){\framebox(90,90){}}
\put(0,0){\framebox(94,94){}}
\put(2,32){\line(1,0){90}}
\put(2,62){\line(1,0){90}}
\put(32,2){\line(0,1){90}}
\put(62,2){\line(0,1){90}}

\put(17,77){\makebox(0,0){2}}
\put(47,77){\makebox(0,0){1}}
\put(77,77){\makebox(0,0){6}}
\put(17,47){\makebox(0,0){4}}
\put(77,47){\makebox(0,0){8}}
\put(17,17){\makebox(0,0){7}}
\put(47,17){\makebox(0,0){5}}
\put(77,17){\makebox(0,0){3}}
\end{picture}
\end{enumerate}

Al\'em das heur\'{\i}sticas
\begin{itemize}
 \item $h_0(n)=0$
 \item $h_1(n)=\mbox{\em n\'umero de pe\c cas fora de lugar}$
 \item $h_2(n)=\mbox{\em dist\^ancia Manhattan total}$
\end{itemize}
considere a heur\'{\i}stica $h_3$ descrita abaixo e tamb\'em alguma outra que
voc\^e encontrar na literatura, na Internet, ou onde quer que seja.

A heur\'{\i}stica $h_3$, introduzida por Nilsson (1971), \'e constitu\'{\i}da de 
2 termos: \[h_3(n)=h_2(n)+s(n)\mbox{,}\]
onde $s(n)=\sum_{i=1}^8\delta_i(n)$, sendo $\delta_i(n)=1$ se a pe\c ca $i$ est\'a no centro; se
a pe\c ca n\~ao est\'a no centro, $\delta_i(n)=0$ se a pe\c ca \'e seguida, no sentido hor\'ario,
pela sua sucessora\footnote{{\em Sucessora} no estado estado meta. Assim, 2 \'e sucessora de 1,
3 \'e sucessora de 2, \ldots, 8 \'e sucessora de 7, e 1 \'e sucessora de 8.}, e $\delta_i(n)=2$
se a pe\c ca n\~ao \'e seguida pela sua sucessora. Esta heur\'{\i}stica, ao contr\'ario das
anteriores, n\~ao \'e admiss\'{\i}vel, mas o autor diz que ela \'e melhor, em geral, do que
$h_2$.

\pagebreak
Por exemplo, para o primeiro estado acima tem-se:
\begin{itemize}
 \item $h_0(n)=0$
 \item $h_1(n)=4$
 \item $h_2(n)=1+1+0+0+0+1+0+2=5$
 \item $h_3(n)=5+0+2+0+0+2+1+2+2=14$
\end{itemize}

Para comparar o desempenho das heur\'{\i}sticas, fa\c ca uma tabela no estilo daquela da Figura 4.8,
p\'agina 103, do livro texto. Explicite suas conclus\~oes.

\vspace*{1cm}
\noindent{\large\bf Refer\^encia}

\begin{enumerate}
 \item Nillson, N.J. {\em Problem-Solving Methods in Artificial Intelligence\/},
       McGraw-Hill, 1971.
\end{enumerate}

\end{document}
 
