\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 ci-clos}

\begin{document}

\vspace*{9cm}
\begin{center} \LARGE\bf
Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca
\end{center}

\vfill
\ 

\pagebreak
\noindent{\Huge\bf Agente Solucionador de Problemas}

\vspace*{1cm}
\begin{enumerate} \LARGE
 \item[\ ] {\bf Agente baseado em meta} cujo objetivo \'e encontrar uma {\bf
       sequ\^encia de a\c c\~oes} que leva a um estado desejado.       
\end{enumerate}

\vspace*{1cm}
\begin{itemize} \LARGE
 \item {\bf Formula\c c\~ao do problema:} defini\c c\~ao do mesmo como um
       problema de busca em um espa\c co de {\bf estados}.
 \item Deve-se definir:
       \begin{itemize}
        \item {\bf estados}: representa\c c\~oes do ``mundo''.
        \item {\bf Operadores}: causam transi\c c\~oes entre estados.
       \end{itemize}
 \item Para ativar o processo de busca por uma solu\c c\~ao, deve-se
       especificar estados {\bf inicial} e {\bf meta}.
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

\pagebreak
\noindent{\LARGE\bf Um exemplo:}

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

\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

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

\begin{itemize}\LARGE
 \item processo de pesquisa pela ``melhor'' se\-qu\^en\-cia de a\c c\~oes que leve a
       um estado meta.
\end{itemize}

\vspace*{1cm}
\noindent{\LARGE\bf Algoritmo de busca:}

\begin{itemize}\LARGE
 \item Recebe como entrada um problema e retorna uma solu\c c\~ao (sequ\^encia de
       a\c c\~oes).
\end{itemize}

\vspace*{1cm}
\noindent{\LARGE\bf Fase de execu\c c\~ao:}

\begin{itemize}\LARGE
 \item Execu\c c\~ao da solu\c c\~ao proposta pelo algoritmo de busca.
\end{itemize}

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

\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

\pagebreak
\noindent {\huge\bf Formula\c c\~ao de Problemas:}

\vspace*{1cm}
\noindent{\LARGE H\'a 4 tipos de problemas:}

\begin{itemize}\LARGE
 \item De \'unico estado.
 \item De m\'ultiplos estados.
 \item De conting\^encias.
 \item De explora\c c\~ao.
\end{itemize}

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

\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

\pagebreak
\noindent{\LARGE\bf Problemas de \'unico estado}

\vspace*{1cm}
\begin{enumerate}\LARGE
 \item[\ ] Ao executar uma a\c c\~ao, o agente sabe o estado resultante (tem sensores
       suficientes).

       Exemplo:

       \begin{picture}(300,70)
        \put(50,30){\oval(26,26){}}
        \put(50,30){\makebox(0,0){5}}
        \put(63,30){\vector(1,0){80}}
        \put(103,33){\makebox(0,0)[b]{\large Right}}
        \put(156,30){\oval(26,26){}}
        \put(156,30){\makebox(0,0){6}}
        \put(169,30){\vector(1,0){80}}
        \put(209,33){\makebox(0,0)[b]{\large Suck}}
        \put(262,30){\oval(26,26){}}
        \put(262,30){\makebox(0,0){8}}
       \end{picture}

\end{enumerate}

\vspace*{1cm}
\noindent{\LARGE\bf Problemas de m\'ultiplos estados}

\vspace*{1cm}
\begin{itemize}\LARGE
 \item Ao executar uma a\c c\~ao, o agente tem conhecimento incompleto sobre o estado
       resultante (os sensores n\~ao captam tudo).
       Exemplo:

       \begin{picture}(300,70)
        \put(0,30){\makebox(0,0)[l]{\{1,2,\ldots,8\}}}
        \put(93,30){\vector(1,0){60}}
        \put(123,33){\makebox(0,0)[b]{\large Right}}
        \put(156,30){\makebox(0,0)[l]{\{2,4,6,8\}}}
        \put(232,30){\vector(1,0){60}}
        \put(262,33){\makebox(0,0)[b]{\large Suck}}
        \put(295,30){\makebox(0,0)[l]{\{4,8\}}}
        \put(316,15){\vector(0,-1){30}}
        \put(319,0){\makebox(0,0)[l]{\large Left}}
        \put(295,-30){\makebox(0,0)[l]{\{3,7\}}}
        \put(292,-30){\vector(-1,0){60}}
        \put(262,-27){\makebox(0,0)[b]{\large Suck}}
        \put(229,-30){\makebox(0,0)[r]{\{7\}}}
       \end{picture}
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

\pagebreak
\noindent{\LARGE\bf Problemas de conting\^encias}

\vspace*{1cm}
\begin{itemize}\LARGE
 \item O agente requer uso de sensor durante a exe\-cu\-\c c\~ao: busca e
       execu\c c\~ao alternadas.
\end{itemize}

\vspace*{3cm}
\noindent{\LARGE\bf Problemas de explora\c c\~ao}

\vspace*{1cm}
\begin{itemize}\LARGE
 \item O agente desconhece completamente os efeitos de suas a\c c\~oes:
       aprendizagem requerida.
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

\pagebreak
\noindent{\LARGE\bf Formula\c c\~ao de problemas de \'unico estado}

\vspace*{.5cm}
\begin{flushleft}\LARGE
 \item Um problema \'e definido especificando-se:
\end{flushleft}

\begin{itemize}\Large
 \item {\bf Estado inicial}. Ex: ``in Arad''.
 \item {\bf Operadores}. Ex: Arad$\rightarrow$Zerind, Arad$\rightarrow$Sibiu, etc.
 \item {\bf Teste de meta} expl\'{\i}cito (ex: ``in Bucharest'') ou impl\'{\i}cito
       (ex: nodirt($x$)).
 \item {\bf Fun\c c\~ao de custo de caminhos}. Ex: somas das dist\^ancias.
\end{itemize}

\vspace*{2cm}
\noindent{\Huge\bf Problemas Exemplo}

\vspace*{1cm}
\begin{itemize}\LARGE
 \item {\em Toy problem\/} $\times$ problema real

       \hspace*{1.5cm} $\downarrow$

       mais f\'acil

       mais conciso

       descri\c c\~ao exata

       f\'acil comparar algoritmos alternativos
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

\pagebreak
\noindent{\LARGE\bf O quebra-cabe\c cas de 8} {\LARGE ({\em 8-puzzle})}

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

\vspace*{5cm}
\noindent{\LARGE\bf Formula\c c\~ao:}

\begin{itemize}\LARGE
 \item Estado: locais dos ladrilhos e do vazio.
 \item Operadores: mover {\bf vazio} para esquerda, direita, para cima ou para baixo.
 \item Teste de meta: estado meta dado.
 \item Custo de caminho: 1 para cada movimento.
\end{itemize}

\vspace*{.5cm}
\noindent {\Large Obs: solu\c c\~ao \'otima de problemas da fam\'{\i}lia
 {\em $n$-puzzle\/} \'e NP-dif\'{\i}cil.}

\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

\pagebreak
\noindent{\LARGE\bf O problema das 8 rainhas} {\LARGE ($n$ rainhas)}

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

\vspace*{4cm}
\noindent{\LARGE\bf Formula\c c\~ao:}

\begin{itemize}\LARGE
 \item Teste de meta: 8 rainhas n\~ao amea\c cadas no tabuleiro.
 \item Custo de caminho: 0.
\end{itemize}

\vspace*{1cm}
\noindent {\LARGE $\Rightarrow$ V\'arias alternativas para estados e operadores.}

\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

\pagebreak
\noindent{\LARGE \underline{Alternativa 1}:}

\begin{itemize}\LARGE
 \item Estado: um arranjo qualquer de 0 a 8 rainhas no tabuleiro.
 \item Operadores: adicione uma rainha ao tabuleiro.
\end{itemize}

\vspace*{.5cm}
{\LARGE $\Rightarrow$ $64^8$ sequ\^encias a investigar.}

\vspace*{2cm}
\noindent{\LARGE \underline{Alternativa 2}:}

\begin{itemize}\LARGE
 \item Estado: um arranjo qualquer de 0 a 8 rainhas sem amea\c cas.
 \item Operadores: adicione uma rainha na coluna desocupada mais \`a esquerda,
       de forma que ela n\~ao seja amea\c cada.
\end{itemize}

\vspace*{.5cm}
{\LARGE $\Rightarrow$ $2057$ sequ\^encias a investigar.}

\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

\pagebreak
\noindent{\LARGE\bf Criptoaritm\'etica}

\vspace*{1cm}
\begin{center}\LARGE
 \verb|FORTY| \\
 \verb|+ TEN| \\
 \verb|+ TEN| \\
 \verb|-----| \\
 \verb|SIXTY|
\end{center}

\vspace*{1cm}
\noindent{\Large {\bf Solu\c c\~ao}: F=2, O=9, R=7, T=8, Y=6, E=5, N=0, S=3,
 I=1, X=4.}

\vspace*{2cm}
\noindent{\LARGE\bf Formula\c c\~ao:}

\begin{itemize}\LARGE
 \item Estado: esquema com algumas letras subs\-ti\-tu\'{\i}\-das por n\'umeros.
 \item Operadores: substituir toda ocorr\^encia de uma letra por um d\'{\i}gito
       ainda n\~ao utilizado.
 \item Teste de meta: toda letra foi substitu\'{\i}da.
 \item Custo de caminho: 0.
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

\pagebreak
\noindent{\LARGE\bf O mundo do aspirador}

\vspace*{1cm}
\noindent{\LARGE\bf Formula\c c\~ao com percep\c c\~ao total:}

\begin{itemize}\LARGE
 \item Estado: um dos 8 mostrados na figura.
 \item Operadores: ir para a esquerda, ir para a direita, aspirar.
 \item Teste de meta: nenhum lugar tem sujeira.
 \item Custo de caminho: 1 para cada a\c c\~ao.
\end{itemize}

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

\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

\pagebreak
\noindent{\large\bf Formula\c c\~ao com percep\c c\~ao nula:}
\begin{itemize}\large
 \item Estado: um subconjunto dos 8.
 \item Operadores: ir para a esquerda, ir para a direita, aspirar.
 \item Teste de meta: nenhum lugar em qualquer estado do conjunto tem sujeira.
 \item Custo de caminho: 1 para cada a\c c\~ao.
\end{itemize}

\vspace*{8cm}
\begin{center}
 Figura 3.7
\end{center}
\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

\pagebreak
\noindent{\LARGE\bf Mission\'arios e canibais}

\vspace*{1cm}
\noindent{\LARGE\bf Formula\c c\~ao:}

\begin{itemize}\LARGE
 \item Estado: $(m,c,b)$, onde:
       \begin{itemize}
        \item $m$: n\'umero de mission\'arios na margem de partida;
        \item $c$: n\'umero de canibais na margem de partida;
        \item $b$: n\'umero de barcos na margem de partida.
       \end{itemize}
 \item Operadores: atravessar:
       \begin{itemize}
        \item 1 mission\'ario; ou
        \item 1 canibal; ou
        \item 2 mission\'arios; ou
        \item 2 canibais; ou
        \item 1 mission\'ario e 1 canibal.
       \end{itemize}
 \item Teste de meta: atingiu o estado $(0,0,0)$.
 \item Custo de caminho: n\'umero de cruzamentos.
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

\pagebreak
\noindent{\LARGE\bf Problemas reais:}

\vspace*{1cm}
\begin{itemize}\LARGE
 \item Determina\c c\~ao de rotas.\\
       Exemplo: redes de computadores, planejamento de viagens a\'ereas.
 \item O problema do caixeiro-viajante.
 \item Leiaute de VLSI.
 \item Navega\c c\~ao de rob\^os.
 \item Montagem por rob\^os.
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

\pagebreak
\noindent{\Huge\bf Buscando Solu\c c\~oes}

\vspace*{.5cm}
\begin{itemize} \Large
 \item {\bf Expans\~ao} de um estado: gera\c c\~ao de seus sucessores.
 \item {\bf Estrat\'egia} de busca: determina a \underline{ordem} das expans\~oes.
 \item {\bf \'Arvore de busca}:
\end{itemize}

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

\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

\pagebreak
\noindent{\LARGE\bf Estrutura de um algoritmo de busca:}

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

\vspace*{3cm}
\noindent{\LARGE\bf Componentes de um {\bf nodo} de uma \'ar\-vo\-re de busca:}

\begin{itemize}\LARGE
 \item estado;
 \item ender\^e\c co do nodo pai;
 \item ender\^e\c cos dos nodos filhos;
 \item operador usado na gera\c c\~ao do estado;
 \item profundidade do nodo;
 \item custo do caminho desde a raiz.
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

\pagebreak
\noindent{\LARGE\bf Algoritmo de pesquisa:}

\vspace*{2cm}
\begin{itemize}\LARGE
 \item Id\'eia b\'asica: expans\~ao sucessiva de nodos da \'arvore de busca.
\end{itemize}

\vspace*{2cm}
\begin{center}
 Figura 3.10
\end{center}

\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

\pagebreak
\noindent{\Huge\bf Estrat\'egias de Busca}

\vspace*{1.5cm}
\noindent{\LARGE\bf Crit\'erios para avalia\c c\~ao:}

\begin{itemize}\LARGE
 \item {\bf Completeza}: sempre encontra uma so\-lu\-\c c\~ao quando existe uma?
 \item {\bf Complexidade de tempo}: n\'umero de nodos gerados/expandidos.
 \item {\bf Complexidade de espa\c co}: n\'umero m\'a\-xi\-mo de nodos na mem\'oria.
 \item {\bf Otimalidade}: sempre encontra uma so\-lu\-\c c\~ao de menor custo?
\end{itemize}

\vspace*{1.5cm}
\noindent{\LARGE\bf Complexidades de tempo e espa\c co medidas em termos de:}

\begin{itemize}\LARGE
 \item $b$: fator de ramifica\c c\~ao m\'aximo da \'arvore de busca.
 \item $d$: profundidade da solu\c c\~ao de menor custo.
 \item $m$: profundidade m\'axima (pode ser $\infty$).
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

\pagebreak
\noindent{\LARGE\bf Busca cega (n\~ao informada)}:

\begin{itemize}\LARGE
 \item s\'o usa informa\c c\~oes obtidas diretamente da formula\c c\~ao do problema.
\end{itemize}

\vspace*{1.5cm}
\noindent{\LARGE\bf Busca heur\'{\i}stica (informada)}:

\begin{itemize}\LARGE
 \item usa informa\c c\~oes ``aproximadas'', usualmente relacionadas a custos.
\end{itemize}

\vspace*{1.5cm}
\noindent{\LARGE\bf Estrat\'egias de busca n\~ao informadas}:

\begin{itemize}\LARGE
 \item Busca por amplitude ({\em breadth-first\/})
 \item Busca por custo uniforme
 \item Busca por profundidade ({\em depth-first\/})
 \item Busca por profundidade limitada
 \item Busca por aprofundamento iterativo ({\em iterative deepening\/})
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

\pagebreak
\noindent{\LARGE\bf Busca por amplitude}

\begin{itemize}\LARGE
 \item Expande um nodo de menor profundidade.
\end{itemize}

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

\vspace*{3cm}
\noindent\fbox{\parbox{14cm}{{\bf function} BREADTH-FIRST-SEARCH({\em problem})
 {\bf returns} a solution or failure \\
\hspace*{1cm} GENERAL-SEARCH({\em problem},ENQUEUE-AT-END) }}

\vspace*{1cm}
\noindent{\LARGE\bf Propriedades:}

\begin{itemize}\LARGE
 \item Completo: sim (se $b$ \'e finito).
 \item Tempo: $1+b+b^2+\cdots+b^d=O(b^d)$. \\
       $\Rightarrow$ exponencial
 \item Espa\c co: $O(b^d)$. \\
       (nodos do \'ultimo n\'{\i}vel na mem\'oria)
 \item \'Otimo: sim, se custo fixo por expans\~ao.
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

\pagebreak
\noindent{\LARGE\bf Busca por custo uniforme}

\begin{itemize}\LARGE
 \item Expande nodo $n$ de menor custo ($g(n)$) associado.
\end{itemize}

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

\vspace*{4.5cm}
\noindent{\LARGE\bf Propriedades:}

\begin{itemize}\LARGE
 \item Completo: sim, se custo por passo $\geq\epsilon$.
 \item Tempo: $|\{n\,\,|\,\,g(n)\leq \mbox{ custo da solu\c c\~ao \'otima}\}|$.
 \item Espa\c co: idem.
 \item \'Otimo: sim, se $\forall n\,\,g(\mbox{\em suc}(n))\geq g(n)$.
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

\pagebreak
\noindent{\LARGE\bf Busca por profundidade}

\begin{itemize}\LARGE
 \item Expande nodo de maior n\'{\i}vel.
\end{itemize}

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


\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

\pagebreak

\noindent\fbox{\parbox{13.5cm}{{\bf function} DEPTH-FIRST-SEARCH({\em problem})
 {\bf returns} a solution or failure \\
\hspace*{1cm} GENERAL-SEARCH({\em problem},ENQUEUE-AT-FRONT) }}

\vspace*{2cm}
{\Large Outra op\c c\~ao: {\bf algoritmo recursivo}}.

\vspace*{2cm}
\noindent{\LARGE\bf Propriedades:}

\begin{itemize}\LARGE
 \item Completo: n\~ao. \\
       pode falhar se a \'arvore tem ramos infinitos. \\
       evitar estados repetidos...
 \item Tempo: $O(b^m)$. \\
       O problema \'e se $m>>d$...
 \item Espa\c co: $O(bm)$; linear!
 \item \'Otimo: n\~ao.
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

\pagebreak
\noindent{\LARGE\bf Busca por profundidade limitada}

\begin{itemize}\LARGE
 \item Busca por profundidade com limite de profundidade $l$.
 \item {\bf Implementa\c c\~ao:} nodos de profundidade $l$ n\~ao t\^em
       sucessores.
\end{itemize}

\vspace*{2cm}
\noindent{\LARGE\bf Propriedades:}

\begin{itemize}\LARGE
 \item Completo: n\~ao.
 \item Tempo: $O(b^l)$.
 \item Espa\c co: $O(bl)$.
 \item \'Otimo: n\~ao.
\end{itemize}

\vspace*{2cm}
\noindent{\LARGE{\bf Problema:} descobrir $l$.}

\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

\pagebreak
\noindent{\LARGE\bf Busca por aprofundamento iterativo}

\begin{itemize}\LARGE
 \item Busca por profundidade com limites de profundidade $0,1,2,\ldots$
\end{itemize}

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

\vspace*{2cm}
\noindent{\LARGE\bf Propriedades:}

\begin{itemize}\LARGE
 \item Completo: sim. \\
       $\Rightarrow$ como busca por amplitude.
 \item Tempo: $(d+1)b^0+db^1+(d-1)b^2+\cdots+b^d=O(b^d)$.
 \item Espa\c co: $O(bd)$. \\
       $\Rightarrow$ como busca por profundidade!
 \item \'Otimo: sim, se custo fixo por expans\~ao. \\
       $\Rightarrow$ como busca por amplitude. \\
       como modific\'a-lo para ``custo uniforme''?
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

\pagebreak
\noindent{\LARGE\bf Busca bidirecional}

\begin{itemize}\LARGE
 \item Busca simult\^anea para frente e para tr\'as.
\end{itemize}

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

\vspace*{4.5cm}
\noindent{\LARGE\bf Propriedades:}

\begin{itemize}\LARGE
 \item Completo: sim.
 \item Tempo: $2O(b^{d/2})=O(b^{d/2})$.
 \item Espa\c co: $O(b^{d/2})$.
 \item \'Otimo: sim.
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

\pagebreak
\noindent{\LARGE\bf Comparando as estrat\'egias:}

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

\vspace*{3cm}
\noindent{\Huge\bf Evitando Estados Repetidos}

\vspace*{1cm}
\noindent{\LARGE\bf Como lidar com estados repetidos:}

\begin{itemize}\LARGE
 \item Ger\'a-los (se existirem).
 \item N\~ao gerar nodo sucessor com mesmo estado que o pai.
 \item N\~ao gerar nodo sucessor com mesmo estado que ancestral (n\~ao
       criar caminhos com ciclos).
 \item N\~ao gerar nodo com estado j\'a gerado.
 \end{itemize}

\vfill
\hfill Cap\'{\i}tulo 3: Solu\c c\~ao de Problemas por Busca

%\pagebreak
%\noindent{\Huge\bf Evitando Estados Repetidos}

%\vspace*{1cm}
%\noindent{\Large\bf $\Rightarrow$Evitar expandir estados j\'a expandidos.}

%\vspace*{1cm}
%\noindent{\LARGE Exemplo extremo:}

%\vspace*{3cm}
%\begin{center}
% Figura 3.19
%\end{center}

%\vspace*{3cm}
%\noindent{\LARGE 3 maneiras de lidar com estados repetidos:}

%\begin{itemize}\LARGE
% \item N\~ao gerar nodo sucessor com mesmo estado que o pai.
% \item N\~ao gerar nodo sucessor com mesmo estado que ancestral (n\~ao criar ciclo).
% \item N\~ao gerar nodo sucessor com mesmo estado que outro nodo.
%\end{itemize}


\end{document}






