\documentclass[12pt, a4paper]{article}
 
\newcounter{conta}
\newcounter{conta2}

\hyphenation{ha-bi-li-da-de es-pe-cia-li-za-das e-xem-plo pro-je-to
com-ple-xi-da-de de-sa-pa-re-ce a-bor-da-gem to-ma-da su-ces-so
in-te-li-gen-tes a-gen-te co-nhe-ci-men-to ra-i-nhas e-fei-tos
al-go-rit-mo o-pe-ra-do-res ta-bu-lei-ro co-mo}

\begin{document}

\vspace*{9cm}
\begin{center} \LARGE\bf
Cap\'{\i}tulo 4: M\'etodos de Busca Heur\'{\i}stica
\end{center}

\vfill
\ 

\pagebreak
\noindent{\Huge\bf Busca pela Melhor Escolha ({\em best-first})}

\vspace*{1.5cm}
\begin{itemize} \LARGE
 \item {\bf Fun\c c\~ao de avalia\c c\~ao:} avalia um nodo segundo certo
       ``crit\'erio'' (resultado: um {\em n\'u\-me\-ro\/}).
 \item Em cada passo, expande o nodo n\~ao expandido com ``melhor''
       avalia\c c\~ao.
\end{itemize}

\vspace*{2.5cm}
\begin{center}
 Figura 4.1
\end{center}

\vspace*{2.5cm}
\noindent{\LARGE\bf Duas abordagens:}

\begin{itemize}\LARGE
 \item Busca gulosa
 \item $A^*$
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 4: M\'etodos de Busca Heur\'{\i}stica

\pagebreak
\noindent {\LARGE\bf Busca gulosa:}

\vspace*{1cm}
\begin{itemize}\LARGE
 \item Minimizar {\bf custo estimado} para atingir a meta.
 \item Expandir o nodo cujo estado \'e previsto como o {\bf mais perto de uma meta}.
\end{itemize}

\vspace*{1cm}
\noindent{\LARGE\bf Fun\c c\~ao heur\'{\i}stica:}

\begin{enumerate}\Large
 \item[\ ] $h(n) = $ custo estimado do caminho mais barato do estado $n$ a uma meta.
 \item[\ ] $h(n) = 0$ se $n$ \'e meta.
\end{enumerate}

\vspace*{1.5cm}
\noindent\fbox{\parbox{14cm}{{\bf function} GREEDY-SEARCH({\em problem})
 {\bf returns} a solution or failure \\
\hspace*{1cm} {\bf return} BEST-FIRST-SEARCH({\em problem},$h$) }}

\vfill
\hfill Cap\'{\i}tulo 4: M\'etodos de Busca Heur\'{\i}stica

\pagebreak
\noindent{\LARGE\bf Um Exemplo de Busca Gulosa:}

\vspace*{1.5cm}
\begin{enumerate}\Large
 \item[\ ] $h_{DLR}(n) = $ dist\^ancia em linha reta de $n$ \`a meta.
\end{enumerate}

\vspace*{5cm}
\begin{center}
 Figura 4.2
\end{center}

\vfill
\hfill Cap\'{\i}tulo 4: M\'etodos de Busca Heur\'{\i}stica

\pagebreak
\noindent{\LARGE\bf Est\'agios em uma pesquisa gulosa por Bucharest
usando $h_{DLR}$:}

\vspace*{6cm}
\begin{center}
 Figura 4.3
\end{center}

\vspace*{6cm}
\noindent{\Large\bf Solu\c c\~ao encontrada:}
\begin{itemize} \Large
 \item Arad$\rightarrow$Sibiu$\rightarrow$Fagaras$\rightarrow$Bucharest
\end{itemize}

\noindent{\Large\bf Solu\c c\~ao \'otima:}
\begin{itemize} \Large
 \item Arad$\rightarrow$Sibiu$\rightarrow$Rimnicu Vilcea$\rightarrow$Pitesti
       $\rightarrow$Bucharest
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 4: M\'etodos de Busca Heur\'{\i}stica

\pagebreak
\noindent{\LARGE\bf Propriedades da Busca Gulosa:}

\begin{itemize}\LARGE
 \item Completo: n\~ao (pode entrar em {\em loop\/}). \\
       Ex: Iasi$\rightarrow$Neamt$\rightarrow$Iasi$\rightarrow\cdots$
 \item Tempo: $O(b^m)$. \\
       Boa fun\c c\~ao $h$ \'e essencial para melhorar o desempenho.
 \item Espa\c co: $O(b^m)$. \\
       Boa fun\c c\~ao $h$ \'e essencial para melhorar o desempenho.
 \item \'Otimo: n\~ao.
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 4: M\'etodos de Busca Heur\'{\i}stica

\pagebreak
\noindent{\LARGE\bf Busca $A^*$}

\vspace*{.5cm}
\begin{itemize}\LARGE
 \item Combina busca por custo uniforme e busca gulosa.
 \item Fun\c c\~ao de avalia\c c\~ao: $f(n)=g(n)+h(n)$.
 
       \begin{enumerate}
        \item[\ ] $g(n)$: custo {\bf real} do caminho do estado inicial
                  at\'e $n$.
        \item[\ ] $h(n)$: custo {\bf estimado} do caminho mais barato de
                  $n$ at\'e um estado meta.
        \item[\ ] $f(n)$: custo {\bf estimado} do caminho mais barato do
                  estado inicial at\'e um estado meta.
       \end{enumerate}
\end{itemize}

\vspace*{1cm}
\noindent{\Large\bf $A^*$ usa {\bf Heur\'{\i}stica Admiss\'{\i}vel}:}

\begin{enumerate} \Large
 \item[\ ] $h$ tal que $h(n)\leq h^*(n)$ para todo $n$.
 \item[\ ] ($h^*(n)$ d\'a o custo {\bf real} de $n$ at\'e uma meta.)
 \item[\ ] Ex: $h_{DLR}$.
\end{enumerate}

\vspace*{1cm}
\noindent\fbox{\parbox{14cm}{{\bf function} $A^*$-SEARCH({\em problem})
 {\bf returns} a solution or failure \\
\hspace*{1cm} {\bf return} BEST-FIRST-SEARCH({\em problem},$g+h$) }}

\vfill
\hfill Cap\'{\i}tulo 4: M\'etodos de Busca Heur\'{\i}stica

\pagebreak
\noindent{\LARGE\bf Est\'agios em uma pesquisa $A^*$ por Bucharest
usando $h_{DLR}$:}

\vspace*{6cm}
\begin{center}
 Figura 4.4
\end{center}

\vspace*{6cm}
\begin{enumerate} \Large
 \item[\ ] $\Rightarrow$ Busca $A^*$ \'e \'otima!
\end{enumerate}

\vfill
\hfill Cap\'{\i}tulo 4: M\'etodos de Busca Heur\'{\i}stica

\pagebreak
\noindent{\LARGE\bf Equa\c c\~ao pathmax:}

\begin{enumerate}\LARGE
 \item[\ ] Seja $n'$ um sucessor de $n$. Ent\~ao:

           \begin{center}
           \fbox{\parbox{10cm}{$f(n')=\mbox{\em max\/}(g(n')+h(n'),f(n))$}}
           \end{center}
 \item[\ ] Assim, $f$ \'e {\bf monot\^onica}.
\end{enumerate}

\vspace*{.5cm}
\noindent{\LARGE\bf Justificando por meio de um exemplo:}

\vspace*{1cm}
\begin{picture}(300,80) \Large
 \put(20,70){\oval(20,20){\makebox(0,0){$n$}}}
 \put(17,40){\makebox(0,0)[r]{$1$}}
 \put(20,10){\oval(20,20){\makebox(0,0){$n'$}}}

 \put(20,60){\vector(0,-1){40}}

 \put(35,70){\makebox(0,0)[l]{$g(n)=5$, $h(n)=4$ $\Rightarrow$ $f(n)=9$}}
 \put(35,10){\makebox(0,0)[l]{$g(n')=6$, $h(n')=2$ $\Rightarrow$ $f(n')=8$}}
\end{picture}

\vspace*{1cm}
\begin{itemize}\Large
 \item Como $h$ \'e {\bf admiss\'{\i}vel} e $f(n)=9$, o custo de um caminho 
       solu\c c\~ao passando por $n$ \'e $\geq 9$.
 \item Logo, o custo de um caminho solu\c c\~ao passando por $n'$ tamb\'em
       \'e $\geq 9$!
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 4: M\'etodos de Busca Heur\'{\i}stica

\pagebreak
\noindent{\LARGE\bf Otimalidade de $A^*$ -- Intui\c c\~ao:}

\vspace*{6cm}
\begin{center}
 Figura 4.5
\end{center}

\vfill
\hfill Cap\'{\i}tulo 4: M\'etodos de Busca Heur\'{\i}stica

\pagebreak
\noindent{\LARGE\bf Otimalidade de $A^*$ -- Prova:}

\vspace*{3cm}
\begin{center}
 Figura 4.6
\end{center}

\vspace*{3cm}
\begin{enumerate} \Large
 \item[\ ] $G_2$: {\bf meta sub-\'otima} ainda n\~ao expandida.
 \item[\ ] $n$: nodo n\~ao expandido no caminho at\'e {\bf meta \'otima} $G$.
 \item[\ ] 
 \item[\ ] \begin{tabbing}
            $f(G_2)$\=$=xxxxxx$\= \kill
            $f(G_2)$\>$=g(G_2)$   \> pois $h(G_2)=0$ \\
                    \>$>g(G)$     \> pois $G_2$ \a'e sub-\a'otima \\
                    \>$\geq f(n)$ \> pois $h$ \a'e admiss\a'{\i}vel \\
           \end{tabbing}
 \item[\ ] 
 \item[\ ] Como $f(G_2)>f(n)$, $A^*$ n\~ao seleciona $G_2$ para expans\~ao!
\end{enumerate}

\vfill
\hfill Cap\'{\i}tulo 4: M\'etodos de Busca Heur\'{\i}stica

\pagebreak
\noindent{\LARGE\bf Propriedades de $A^*$:}

\vspace*{.5cm}
\begin{itemize}\LARGE
 \item Completo: sim. \\
       Grafo com fator de ramifica\c c\~ao finito e
        nodo com custo $\geq \delta$.
 \item Tempo: exponencial. \\
       (A menos que $|h(n)-h^*(n)|\leq O(\log h^*(n))$.)
 \item Espa\c co: exponencial. \\
       Mant\'em todos os nodos na mem\'oria.
 \item \'Otimo: sim.
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 4: M\'etodos de Busca Heur\'{\i}stica

\pagebreak
\noindent{\Huge\bf Fun\c c\~oes Heur\'{\i}sticas}

\vspace*{1cm}
\noindent{\LARGE\bf Ex: 8-puzzle/heur\'{\i}sticas admiss\'{\i}veis}

\vspace*{3.5cm}
\begin{center}
 Figura 4.7
\end{center}

\vspace*{3cm}
\begin{itemize}\LARGE
 \item $h_1(n)$: n\'umero de ladrilhos fora de lugar.
 \item $h_2(n)$: {\em dist\^ancia Manhattan\/} total.
 \end{itemize}

\noindent{\LARGE Para o exemplo acima:}

\begin{itemize}\LARGE
 \item $h_1(S)=7$
 \item $h_2(S)=2+3+3+2+4+2+0+2=18$
 \end{itemize}

\vfill
\hfill Cap\'{\i}tulo 4: M\'etodos de Busca Heur\'{\i}stica

\pagebreak
\noindent{\LARGE\bf Domin\^ancia}

\vspace*{1cm}
\begin{enumerate} \Large
 \item[\ ] Sejam $h_1$ e $h_2$ admiss\'{\i}veis. \\
           $h_2$ {\bf domina} $h_1$ se
           $h_2(n)\geq h_1(n)$ para todo $n$.\\
           $\Rightarrow h_2$ \'e ``melhor''.
\end{enumerate}

\begin{enumerate} \Large
 \item[\ ] Quando $h$ tende para $h^*$, o fator de ramifica\c c\~ao m\'edio
           tende para 1.
\end{enumerate}

\begin{enumerate} \Large
 \item[\ ] Custos t\'{\i}picos para 8-puzzle:

\vspace*{1cm}
           \begin{center}
           \begin{tabular}{|r||r|r|r||c|c|c|} \hline
               & \multicolumn{3}{c||}{\em Custo da busca} & \multicolumn{3}{c|}{\em F. de R. m\'edio} \\ \hline
            $d$ & IDS & $A^*(h_1)$ & $A^*(h_2)$ & IDS & $A^*(h_1)$ & $A^*(h_2)$ \\ \hline
             4  & 112 & 13 & 12         & 2.87 & 1.48 & 1.45 \\
             10 & 47.127 & 93 & 39      & 2.79 & 1.38 & 1.22 \\
             14 & 3.473.941 & 539 & 113 & 2.83 & 1.44 & 1.23 \\
             20 & boom & 7.226 & 676    & $--$ & 1.47 & 1.27 \\
             24 & boooom & 39.135 & 1.641 & $--$ & 1.48 & 1.26 \\ \hline
           \end{tabular}
           \end{center}
\end{enumerate}

\vfill
\hfill Cap\'{\i}tulo 4: M\'etodos de Busca Heur\'{\i}stica

\pagebreak
\noindent{\LARGE\bf Criando fun\c c\~oes heur\'{\i}sticas}

\vspace*{1cm}
\begin{enumerate} \Large
 \item[\ ] Heur\'{\i}sticas admiss\'{\i}veis podem ser obtidas de {\em
        solu\c c\~oes exatas\/} de {\bf vers\~oes relaxadas} do problema.
\end{enumerate}

\vspace*{1cm}
\noindent{\LARGE Exemplos para {\em 8-puzzle\/}:}

\begin{itemize}\Large
 \item Um ladrilho pode ser movido para {\em qualquer posi\c c\~ao\/}.

       $\Rightarrow$ {\bf Heur\'{\i}stica:} $h_1(n)$.

 \item Um ladrilho pode ser movido para {\em qualquer posi\c c\~ao adjacente\/}.

       $\Rightarrow$ {\bf Heur\'{\i}stica:} $h_2(n)$.
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 4: M\'etodos de Busca Heur\'{\i}stica

\pagebreak
\begin{itemize}\LARGE
 \item Sejam $h_1$, $h_2$, \ldots, $h_m$ heur\'{\i}sticas admiss\'{\i}veis.
       \begin{enumerate}
        \item[\ ] $\Rightarrow$ $h(n)=\mbox{\em max\/}(h_1(n),h_2(n),\ldots,h_m(n))$ \\
                  \ \\
                  {\bf domina} todas.
       \end{enumerate}

 \item Usando-se problemas de {\em treinamento\/}, pode-se obter informa\c c\~oes
       {\bf estat\'{\i}sticas} para ajustar $h$.

 \item Fun\c c\~ao (n\~ao) linear de {\bf caracter\'{\i}sticas} do estado.

 \item {\bf Custo} para calcular a fun\c c\~ao heur\'{\i}stica \'e muito importante.

\end{itemize}


\vfill
\hfill Cap\'{\i}tulo 4: M\'etodos de Busca Heur\'{\i}stica

\pagebreak
\noindent{\Huge\bf Algoritmos de Aperfei\c coamento Iterativo}

\vspace*{1.5cm}
\begin{itemize} \LARGE
 \item O algoritmo mant\'em apenas o {\bf \'ultimo estado} gerado.
 \item Para gerar o pr\'oximo estado, modifica ({\em aperfei\c coa\/}) o estado atual.
\end{itemize}

\vspace*{1cm}
\noindent {\LARGE Aplic\'avel em situa\c c\~oes onde:}

\begin{itemize} \LARGE
 \item O {\em caminho\/} do estado inicial at\'e o atual \'e irrelevante:
       o estado atual cont\'em toda informa\c c\~ao necess\'aria para orientar a busca.
\end{itemize}

\vspace*{1cm}
\noindent {\LARGE $\Rightarrow$ Espa\c co constante!}

\vspace*{1cm}
\noindent{\LARGE Exemplos:}

\begin{itemize}\Large
 \item Problema do Caixeiro Viajante.

 \item $n$ Rainhas.
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 4: M\'etodos de Busca Heur\'{\i}stica

\pagebreak
\noindent {\LARGE A id\'eia: encontrar um pico na superf\'{\i}cie de estados.}

\vspace*{5cm}
\begin{center}
 Figura 4.13
\end{center}

\vspace*{5cm}
\noindent {\LARGE $\Rightarrow$ Escalando o Everest com forte neblina, com amn\'esia...}

\vspace*{1cm}
\noindent {\LARGE Dois tipos de algoritmos de aperfei\c coamento i\-te\-ra\-ti\-vo:}

\begin{itemize} \Large
 \item {\em Hill-climbing}
 \item {\em Simulated annealing}
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 4: M\'etodos de Busca Heur\'{\i}stica

\pagebreak
\noindent {\LARGE\bf Hill-climbing}

\vspace*{4cm}
\begin{center}
 Figura 4.14
\end{center}

\vspace*{4cm}
\noindent {\Large {\bf Problema:} m\'aximos locais.}

\vfill
\hfill Cap\'{\i}tulo 4: M\'etodos de Busca Heur\'{\i}stica

\pagebreak
\noindent {\LARGE\bf Simulated annealing}

\vspace*{1.5cm}
\noindent {\Large\bf Id\'eia:}
\begin{itemize} \Large
 \item Escapar de m\'aximos locais permitindo alguns movimentos ``ruins'', {\em mas\/}
       diminuindo progressivamente sua amplitude e freq\"u\^encia.
\end{itemize}

\vspace*{5cm}
\begin{center}
 Figura 4.15
\end{center}

\vspace*{5cm}
\noindent {\Large Se a ``temperatura'' T {\em decresce devagar\/}, atinge o melhor estado.}

\vspace*{1cm}
\noindent {\Large Aplica\c c\~es pr\'aticas em: leioute de VLSI, escalonamento, etc.}

\end{document}
