\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 ne-nhu-ma co-lu-na
cons-tan-te}

\begin{document}

\vspace*{9cm}
\begin{center} \LARGE\bf
Problemas de Satisfa\c c\~ao de Restri\c c\~oes \\
(cap\'{\i}tulos 3 e 4)
\end{center}

\vfill
\ 

\pagebreak
\noindent{\Huge\bf O que \'e um CSP:}

\vspace*{1.5cm}
\begin{itemize} \LARGE
 \item {\bf Estado:} definido por \underline{vari\'aveis} $V_i$, que podem tomar
       valores de um \underline{dom\'{\i}nio} $D_i$.

       \vspace*{2mm} Dom\'{\i}nio: {\em discreto\/} ou {\em cont\'{\i}nuo\/}.
 \item {\bf Teste de meta:} conjunto de \underline{restri\c c\~oes} que devem ser
       satisfeitas pelos valores das vari\'aveis.

       \vspace*{2mm} Restri\c c\~ao: {\em un\'aria\/}, {\em bin\'aria\/}, etc.
\end{itemize}

\vspace*{1cm}
\noindent{\LARGE\bf Solu\c c\~ao de um CSP:}

\begin{itemize}\LARGE
 \item Atribui\c c\~ao de valores para todas as vari\'aveis, satisfazendo o teste
       de meta (ou seja, todas as restri\c c\~oes).
\end{itemize}

\vspace*{1cm}
\noindent{\LARGE $\Rightarrow$ Algoritmos espec\'{\i}ficos para CSP s\~ao mais
poderosos do que algoritmos de busca padr\~oes.}


\vfill
\hfill Problemas de Satisfa\c c\~ao de Restri\c c\~oes

\pagebreak
\noindent {\LARGE\bf Exemplo: 4 rainhas no tabuleiro:}

\begin{itemize}\LARGE
 \item {\bf Vari\'aveis:} $V_i$, $i=1, 2, 3, 4$: linha da rainha na col. $i$.

 \item {\bf Dom\'{\i}nios:} $D_i=\{1, 2, 3, 4\}$.

 \item {\bf Restri\c c\~oes:} Para $i\not=j$:

       \begin{itemize}
        \item $V_i\not= V_j$ (linhas distintas)

        \item $|V_i-V_j|\not=|i-j|$ (diagonais distintas)
       \end{itemize}
\end{itemize}

\vspace*{1cm}
\noindent {\LARGE Para dom\'{\i}nios discretos:}

\begin{itemize}\LARGE
 \item Cada restri\c c\~ao pode ser representada enumerando-se os valores
       permiss\'{\i}veis.

       \vspace*{2mm}
       Exemplo: $V_1\not= V_2$ e $|V_1-V_2|\not=|1-2|$
       
       \vspace*{2mm}
       $(V_1,V_2)\in\{(1,3),(1,4),(2,4),(3,1),(4,1)(4,2)\}$.
\end{itemize}

\vspace*{1cm}
\noindent {\LARGE\em Grafo de restri\c c\~oes:} {\Large cada vari\'avel \'e um nodo;
cada restri\c c\~ao (bin\'aria) um arco.}



\vfill
\hfill Problemas de Satisfa\c c\~ao de Restri\c c\~oes

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

\vspace*{.5cm}
\begin{center} \LARGE
 \verb|   S E N D| \\
 \verb| + M O R E| \\
 \verb|----------| \\
 \verb| M O N E Y|
\end{center}

\vspace*{.5cm}
\begin{itemize}\LARGE
 \item {\bf Vari\'aveis:} D, E, M, N, O, R, S, Y.

 \item {\bf Dom\'{\i}nios:} $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$.

 \item {\bf Restri\c c\~oes:}

       \begin{itemize}
        \item $M\not= 0$,  $S\not= 0$ (un\'arias)

        \item $Y=D+E \mbox{ ou } Y=D+E-10$, etc.

        \item $D\not=E$, $D\not=M$, $D\not=N$, etc.
       \end{itemize}
\end{itemize}

\vfill
\hfill Problemas de Satisfa\c c\~ao de Restri\c c\~oes

\pagebreak
\noindent {\LARGE\bf Exemplo: Colora\c c\~ao de Mapas}

\vspace*{1cm}
\begin{quote} \LARGE
 Colorir um mapa de forma que pa\'{\i}ses adjacentes n\~ao tenham a mesma cor.
\end{quote}

\begin{center}
\begin{picture}(250,200) \large
\put(10,0){\line(1,0){180}}
\put(10,0){\line(0,1){90}}
\put(190,0){\line(0,1){90}}
\put(15,5){\makebox(0,0)[bl]{$P_6$}}

\put(50,50){\line(1,0){110}}
\put(50,50){\line(0,1){40}}
\put(160,50){\line(0,1){80}}
\put(90,130){\line(1,0){70}}
\put(55,55){\makebox(0,0)[bl]{$P_5$}}


\put(190,0){\line(1,0){60}}
\put(250,0){\line(0,1){60}}
\put(250,60){\line(-1,0){60}}
\put(245,5){\makebox(0,0)[br]{$P_4$}}

\put(0,90){\framebox(90,70){}}
\put(5,155){\makebox(0,0)[tl]{$P_3$}}

\put(160,90){\line(1,0){40}}
\put(200,90){\line(0,1){100}}
\put(200,190){\line(-1,0){60}}
\put(140,190){\line(0,-1){60}}
\put(145,185){\makebox(0,0)[tl]{$P_2$}}

\put(60,160){\line(0,1){20}}
\put(60,180){\line(1,0){80}}
\put(65,175){\makebox(0,0)[tl]{$P_1$}}

\end{picture}
\end{center}

\vspace*{1cm}
\begin{itemize}\LARGE
 \item {\bf Vari\'aveis:} pa\'{\i}ses $P_i$.

 \item {\bf Dom\'{\i}nios:} $\{\mbox{\em Vermelho\/},\mbox{\em Azul\/},\mbox{\em Laranja\/}\}$.

 \item {\bf Restri\c c\~oes:} $P_1\not= P_2$, $P_1\not=P_5$, etc.

\end{itemize}

\vfill
\hfill Problemas de Satisfa\c c\~ao de Restri\c c\~oes

\pagebreak
\noindent {\LARGE\bf Busca ``padr\~ao'' para CSP's:}

\vspace*{1cm}
\begin{itemize}\LARGE
 \item \underline{Estado inicial}: conjunto das vari\'aveis sem valores.

 \item \underline{Operadores}: atribuir um valor a uma vari\'avel livre.

 \item \underline{Teste de meta}: toda vari\'avel com valor e nenhuma restri\c c\~ao
       violada.
\end{itemize}

\vspace*{1cm}
\noindent {\LARGE\bf Representa\c c\~ao de uma restri\c c\~ao:}

\begin{itemize} \LARGE
 \item {\em Explicitamente} como conjunto de valores permiss\'{\i}veis.
 \item {\em Implicitamente} como uma fun\c c\~ao que a testa.
\end{itemize}

\vspace*{1cm}
\noindent {\LARGE Exemplo: Colora\c c\~ao de Mapas}

\vfill
\hfill Problemas de Satisfa\c c\~ao de Restri\c c\~oes

\pagebreak
\noindent {\LARGE\bf Complexidade da busca ``padr\~ao'' cega:}

\vspace*{1cm}
\begin{itemize} \LARGE
 \item Profundidade m\'axima da \'arvore de busca, $m= n$ (n\'umero de vari\'aveis).
 \item Profundidade de estado meta, $d=n$.
 \item Algoritmo a usar: busca por profundidade.
 \item Fator de ramifica\c c\~ao, $b=\sum_i^n|D_i|$ (no topo da \'arvore).
\end{itemize}

\noindent {\LARGE Isto pode ser melhorado dramaticamente, levando em conta que:}

\begin{enumerate} \Large
 \item[1)] Ordem de atribui\c c\~ao de valores \'e irrelevante: muitos caminhos equivalentes.
 \item[2)] Atribui\c c\~ao de valores n\~ao corrigem uma restri\c c\~ao j\'a violada.
\end{enumerate}

\vspace*{1cm}
\noindent {\LARGE\bf Busca por profundidade \'e o algoritmo base para CSP's.} {\LARGE Mas:}

\begin{enumerate} \Large
 \item[1)] Fixar uma ordem de atribui\c c\~ao; com isto, $b=|D_i|$.

 \item[2)] Checar por viola\c c\~ao de restri\c c\~oes.

\end{enumerate}

\vspace*{.5cm}
\noindent {\LARGE $\Rightarrow$ Resolve Prob. das $n$ rainhas para $n\approx 15$.}

\vfill
\hfill Problemas de Satisfa\c c\~ao de Restri\c c\~oes

\pagebreak
\noindent {\LARGE\bf Checagem \`a frente ({\em forward checking\/})}

\vspace*{.5cm}
\noindent {\LARGE\bf Id\'eia:}

\begin{itemize} \LARGE
 \item Atualizar valores legais restantes para vari\'aveis que ainda n\~ao receberam
       valores.
 \item Terminar a busca se alguma vari\'avel n\~ao tem valor legal poss\'{\i}vel.
\end{itemize}


\vspace*{.5cm}
\noindent {\LARGE\bf Exemplo: colora\c c\~ao de mapas}

\vspace*{.5cm}
{\large
\begin{tabular}{|c|c|c|c|} \hline
       & V & A & L \\ \hline
 $P_1$ &           &            &             \\ \hline
 $P_2$ &           &            &             \\ \hline
 $P_3$ &           &            &             \\ \hline
 $P_4$ &           &            &             \\ \hline
 $P_5$ &           &            &             \\ \hline
 $P_6$ &           &            &             \\ \hline
\end{tabular}
$\longrightarrow$
\begin{tabular}{|c|c|c|c|} \hline
       & V & A & L \\ \hline
 $P_1$ & $\surd$   &            &             \\ \hline
 $P_2$ & $\times$  &            &             \\ \hline
 $P_3$ & $\times$  &            &             \\ \hline
 $P_4$ &           &            &             \\ \hline
 $P_5$ & $\times$  &            &             \\ \hline
 $P_6$ &           &            &             \\ \hline
\end{tabular}
$\longrightarrow$
\begin{tabular}{|c|c|c|c|} \hline
       & V & A & L \\ \hline
 $P_1$ & $\surd$   &            &             \\ \hline
 $P_2$ & $\times$  & $\surd$    &             \\ \hline
 $P_3$ & $\times$  &            &             \\ \hline
 $P_4$ &           &            &             \\ \hline
 $P_5$ & $\times$  & $\times$   &             \\ \hline
 $P_6$ &           & $\times$   &             \\ \hline
\end{tabular}

\begin{picture}(350,20)
 \put(300,20){\line(0,-1){10}}
 \put(300,10){\line(-1,0){250}}
 \put(50,10){\vector(0,-1){10}}
\end{picture}

\begin{tabular}{|c|c|c|c|} \hline
       & V & A & L \\ \hline
 $P_1$ & $\surd$   &            &             \\ \hline
 $P_2$ & $\times$  & $\surd$    &             \\ \hline
 $P_3$ & $\times$  & $\surd$    &             \\ \hline
 $P_4$ &           &            &             \\ \hline
 $P_5$ & $\times$  & $\times$   &             \\ \hline
 $P_6$ &           & $\times$   &             \\ \hline
\end{tabular}
$\longrightarrow$
\begin{tabular}{|c|c|c|c|} \hline
       & V & A & L \\ \hline
 $P_1$ & $\surd$   &            &             \\ \hline
 $P_2$ & $\times$  & $\surd$    &             \\ \hline
 $P_3$ & $\times$  & $\surd$    &             \\ \hline
 $P_4$ & $\surd$   &            &             \\ \hline
 $P_5$ & $\times$  & $\times$   &             \\ \hline
 $P_6$ & $\times$  & $\times$   &             \\ \hline
\end{tabular}
$\longrightarrow$
\begin{tabular}{|c|c|c|c|} \hline
       & V & A & L \\ \hline
 $P_1$ & $\surd$   &            &             \\ \hline
 $P_2$ & $\times$  & $\surd$    &             \\ \hline
 $P_3$ & $\times$  & $\surd$    &             \\ \hline
 $P_4$ & $\surd$   &            &             \\ \hline
 $P_5$ & $\times$  & $\times$   & $\surd$     \\ \hline
 $P_6$ & $\times$  & $\times$   & $\times$    \\ \hline
\end{tabular}

}

\vspace*{.5cm}
\noindent {\LARGE $\Rightarrow$ Resolve Prob. das $n$ rainhas para $n\approx 30$.}

\vfill
\hfill Problemas de Satisfa\c c\~ao de Restri\c c\~oes

\pagebreak
\noindent {\LARGE\bf Heur\'{\i}sticas para CSP's}

\vspace*{.5cm}
\begin{center}
\begin{picture}(250,200) \large
\put(10,0){\line(1,0){180}}
\put(10,0){\line(0,1){90}}
\put(190,0){\line(0,1){90}}
\put(15,5){\makebox(0,0)[bl]{$P_6$}}

\put(50,50){\line(1,0){110}}
\put(50,50){\line(0,1){40}}
\put(160,50){\line(0,1){80}}
\put(90,130){\line(1,0){70}}
\put(55,55){\makebox(0,0)[bl]{$P_5$}}


\put(190,0){\line(1,0){60}}
\put(250,0){\line(0,1){60}}
\put(250,60){\line(-1,0){60}}
\put(245,5){\makebox(0,0)[br]{$P_4$}}

\put(0,90){\framebox(90,70){}}
\put(5,155){\makebox(0,0)[tl]{$P_3$}}

\put(160,90){\line(1,0){40}}
\put(200,90){\line(0,1){100}}
\put(200,190){\line(-1,0){60}}
\put(140,190){\line(0,-1){60}}
\put(145,185){\makebox(0,0)[tl]{$P_2$}}

\put(60,160){\line(0,1){20}}
\put(60,180){\line(1,0){80}}
\put(65,175){\makebox(0,0)[tl]{$P_1$}}

\end{picture}
\end{center}

\vspace*{.5cm}
\noindent {\LARGE Dados:}

\begin{itemize}\LARGE
 \item $P_1=\mbox{V}$, $P_2=\mbox{L}$. $P_3 = ?$

       \vspace*{.5cm}
       $P_3=L$ $\Rightarrow$ {\em valor menos restringente}

 \item $P_1=\mbox{V}$, $P_2=\mbox{L}$. Que vari\'avel escolher em seguida?

       \vspace*{.5cm}
       $P_5$ $\Rightarrow$ {\em vari\'avel mais restrita}

\end{itemize}

\vspace*{.5cm}
\noindent {\LARGE $\Rightarrow$ Resolve Prob. das $n$ rainhas para $n\approx 1000$.}

\vfill
\hfill Problemas de Satisfa\c c\~ao de Restri\c c\~oes

\pagebreak
\noindent {\LARGE\bf Algoritmos Iterativos para CSP's}

\vspace*{1cm}
\noindent{\LARGE {\em Hill-climbing\/} e {\em Simulated annealing\/} s\~ao
 aplicados a estados \underline{completos} (todas as vari\'aveis com valor).}

\vspace*{1cm}
\noindent {\LARGE Para aplicar tais algoritmos a CSP's:}

\begin{itemize}\LARGE
 \item Permitir estados com restri\c c\~oes violadas.
 \item Operadores {\em reatribuem\/} valores de vari\'aveis.
\end{itemize}

\vspace*{1cm}
\noindent {\LARGE\bf Escolha de vari\'avel:}

\vspace*{.5cm}
 {\LARGE Vari\'avel que viola restri\c c\~ao.}

\vspace*{1cm}
\noindent {\LARGE\bf Escolha de novo valor para vari\'avel:}

\vspace*{.5cm}
 {\LARGE Heur\'{\i}stica de {\bf conflitos m\'{\i}nimos} ({\em min-conflicts\/}):}

\begin{itemize}\LARGE
 \item Escolha valor que viola menos restri\c c\~oes. Ou seja, $h(n)=\mbox{n\'umero de restri\c c\~oes
       violadas}$.
\end{itemize}

\vfill
\hfill Problemas de Satisfa\c c\~ao de Restri\c c\~oes

\pagebreak
\noindent {\LARGE\bf Exemplo: 4 rainhas}

\vspace*{.5cm}
\begin{itemize}\LARGE
 \item {\bf Estados:} 4 rainhas em 4 colunas ($4^4$=256 estados).
 \item {\bf Operadores:} mover rainha em uma coluna.
 \item {\bf Teste de meta:} nenhuma rainha amea\c ca outra.
 \item {\bf Fun\c c\~ao de avalia\c c\~ao:}

       \hspace*{1cm}
       $h(n)=\mbox{n\'umero de amea\c cas}$.
\end{itemize}

\vspace*{1cm}\noindent
\begin{picture}(144,124) \Large
\put(2,2){\framebox(120,120){}}
\put(0,0){\framebox(124,124){}}
\put(2,32){\line(1,0){120}}
\put(2,62){\line(1,0){120}}
\put(2,92){\line(1,0){120}}
\put(32,2){\line(0,1){120}}
\put(62,2){\line(0,1){120}}
\put(92,2){\line(0,1){120}}

\put(17,47){\makebox(0,0){$\Re$}}
\put(47,77){\makebox(0,0){$\Re$}}
\put(77,47){\makebox(0,0){$\Re$}}
\put(107,77){\makebox(0,0){$\Re$}}

\put(62,-15){\makebox(0,0){$h=5$}}
\put(136,62){\makebox(0,0){$\Rightarrow$}}
\end{picture}
\begin{picture}(144,124) \Large
\put(2,2){\framebox(120,120){}}
\put(0,0){\framebox(124,124){}}
\put(2,32){\line(1,0){120}}
\put(2,62){\line(1,0){120}}
\put(2,92){\line(1,0){120}}
\put(32,2){\line(0,1){120}}
\put(62,2){\line(0,1){120}}
\put(92,2){\line(0,1){120}}

\put(17,47){\makebox(0,0){$\Re$}}
\put(47,107){\makebox(0,0){$\Re$}}
\put(77,47){\makebox(0,0){$\Re$}}
\put(107,77){\makebox(0,0){$\Re$}}

\put(62,-15){\makebox(0,0){$h=2$}}
\put(136,62){\makebox(0,0){$\Rightarrow$}}
\end{picture}
\begin{picture}(124,124) \Large
\put(2,2){\framebox(120,120){}}
\put(0,0){\framebox(124,124){}}
\put(2,32){\line(1,0){120}}
\put(2,62){\line(1,0){120}}
\put(2,92){\line(1,0){120}}
\put(32,2){\line(0,1){120}}
\put(62,2){\line(0,1){120}}
\put(92,2){\line(0,1){120}}

\put(17,47){\makebox(0,0){$\Re$}}
\put(47,107){\makebox(0,0){$\Re$}}
\put(77,17){\makebox(0,0){$\Re$}}
\put(107,77){\makebox(0,0){$\Re$}}

\put(62,-15){\makebox(0,0){$h=0$}}
\end{picture}

\vspace*{1.5cm}
\noindent {\LARGE $\Rightarrow$ Resolve Prob. das $n$ rainhas para qualquer $n$ com alta
probabilidade (em tempo quase constante!).}

\vfill
\hfill Problemas de Satisfa\c c\~ao de Restri\c c\~oes

\pagebreak


\end{document}

