Domnios FinitosA eficincia das programas em domnios finitos (incluindo booleanos) podem ainda ser melhoradas pelo uso deAlgoritmos de Propagao adequadosHeursticas para escolha da varivel e do valorAntes de investigarmos estes aspectos, nomeadamente a propagao de restries, convm formalizar alguns conceitos tais comorestries e rede de restriessolues parciais e totaissatisfao e consistncia

Domnios FinitosDefinio (Domnio de Varivel):O domnio de uma varivel o conjunto (finito) de valores que podem ser atribudos a uma varivel.Dada uma varivel X, o seu domnio ser normalmente denotado por dom(X) ou simplesmente Dx.Exemplo:O Problema das n rainhas pode ser modelado atravs de n variveis X1 a Xn, todas com domnio de 1 a n.Dom(Xi) = {1,2, ..., n} ou Xi :: 1..n.

Domnios FinitosDefinio (Etiqueta):Uma etiqueta um par Varivel-Valor, sendo o valor um dos elementos do domnio da varivel.Com a definio de etiqueta pretende-se formalizar a atribuio do valor varivel.Definio (Etiqueta Composta):Uma etiqueta composta um conjunto de etiquetas referentes a variveis distintas.Com a definio de etiqueta pretende-se formalizar a noo de soluo (parcial), em que algumas (todas) variveis do problema tm valor atribudo.

Domnios FinitosDefinio (Restrio):Dado um conjunto de variveis, uma restrio um conjunto de etiquetas compostas definidas nessas variveis. De facto, uma restrio pode ser vista como um subconjunto do produto cartesiano dos domnios das variveis envolvidas na restrio.Por exemplo, para qualquer restrio Rijk envolvendo as variveis Xi, Xj e Xk, teremos Rijk dom(Xi) x dom(Xj) x dom(Xk)

Domnios FinitosDada uma restrio R, o conjunto de variveis da restrio ser denotado por Vars(R).De uma forma simtrica, o conjunto de restries em que participa a varivel X denotado por cons(X).De notar ainda que sendo a restrio uma relao (no um a funo) temos que Rij = Rji.As restries podem ser especificadas porExtenso: atravs da enumerao das etiquetas permitidas; ouInteno: atravs de um predicado (procedimento) que determina as etiquetas permitidas

Domnios FinitosPor exemplo, dadas as variveis X1 e X3 do problema das 4 rainhas, existe uma restrio entre elas, R13, que pode ser especificada Por extenso: R13 = {{X1-1, X3-2}, {X1-1, X3-4}, {X1-2, X3-1}, {X1-2, X3-3}, {X1-3, X3-2}, {X1-3, X3-4}, {X1-4, X3-1}, {X1-4, X3-3}}ou, omitindo as variveisR13 = {, , , , , , , } Por inteno: R13 = (X1 X3) (1+X1 3+X3) (3+X1 1+X3)

Domnios FinitosDefinio (Aridade de uma Restrio):A aridade de uma restrio R o nmero de variveis sobre as quais a restrio definida, ou seja a cardinalidade do conjunto vars(R).Apesar das restries poderem ter uma aridade arbitrria, um subconjunto muito importante de restries constitudo pelas restries binrias.A importncia dessas restries advm de queTodas as restries podem ser convertidas em restries binrias. Existem conceitos e algoritmos apropriados para essas restries.

Domnios FinitosConverso para Restries Binrias Uma restrio n-ria, R, constituda por k etiquetas compostas nas suas variveis X1 a Xn, equivalente a n restries binrias, Bi, atravs da adio de uma varivel adicional, Z, que tem como domnio os valores de 1 a k.Com efeito, as k etiquetas n-rias podem ser arbitrariamente ordenadas.Cada uma das n restries binrias Bi relaciona uma das n variveis Xi com a nova varivel Z.A etiqueta composta {Xi-vi, Z-z} pertence restrio Bi sse Xi-vi pertencer z-sima etiqueta composta que define R.

Domnios FinitosExemplo: Dadas as variveis X1 a X3, com domnios 1 a 3, converter em restries binrias a restrio R que impe valores diferentes para as trs variveis.R(X1, X2, X3) = {,,, ,,} Associemos a cada etiqueta composta um valor de 1 a 61 : , 2 : , ... 6: As restries binrias equivalentes restrio inicial soB1(Z, X1) = {, , , , , } B1(Z, X1) = {, , , , , }B1(Z, X1) = {, , , , , }

Domnios FinitosDefinio (Satisfao de Restrio 1):Uma etiqueta composta satisfaz um restrio se as suas variveis (da etiqueta e da restrio) forem as mesmas e se a etiqueta for um elemento da restrio.Na prtica, conveniente generalizar a satisfao a situaes em que as etiquetas compostas contm estritamente as variveis da restrio.Definio (Satisfao de Restrio 2 ):Uma etiqueta composta satisfaz um restrio se as suas variveis incluirem as da restrio e se a sua (da etiqueta) projeco para as variveis da restrio fr um elemento da restrio.

Domnios FinitosDefinio (Problema de Satisfao de Restries):Um problema de satisfao de restries um triplo em que V o conjunto das variveis do problemaD o domnio das variveisR o conjunto das restries do problemaDefinio (Soluo dum Problema):Uma soluo de um problema de satisfao de restries P = uma etiqueta composta sobre as variveis V do problema que satisfaz todas as restries R.

Domnios FinitosEm muitas situaes conveniente considerar as vrias restries de um problema sob a forma de um grafo.Definio (Grafo ou Rede de Restries):O grafo ou rede de restries de um problema de restries binrias tem como ns as variveis do problema. Para cada restrio no-trivial do problema envolvendo uma ou duas variveis, o grafo contm um arco ligando os ns correspondentes a essas variveisQuando os problemas contm restries com aridade arbitrria, elas podem ser convertidas nas suas equivalentes binrias.

Domnios FinitosQuando por algum motivo no seja conveniente converter as restries n-rias em binrias, o problema pode ser representado por um hiper-grafo.Definio (Hiper-Grafo de Restries):Qualquer problema de restries n-rias arbitrrias pode ser representado atravs de um hiper-grafo, cujos ns so as variveis do problema. Para cada restrio do problema, o grafo contm um hiper-arco ligando os ns correspondentes s variveis envolvidas na restrio.Como bvio, se o problema s contm restries binrias, o hiper-grafo de restries degenera num grafo.

Domnios FinitosExemplo: O problema das 4 rainhas pode ser definido pelo seguinte grafo:{, , , , , , , }

Domnios FinitosDefinio (Grafo de Restries Completo):Um grafo de restries completo quando existem arcos ligando qualquer par de ns (isto , quando existe uma restrio sobre qualquer par de variveis).O problema das 4 rainhas tem um grafo completo. No entanto, esse no sempre o caso, podendo os grafos ser esparsos por no conterem alguns arcos potenciais. Nesse caso importa definir a densidade de um grafo.Definio (Densidade de um Grafo de Restries):A densidade de um grafo de restries corresponde razo entre o nmero de arcos e o nmero de arcos de um grafo completo com o mesmo nmero de ns.

Domnios FinitosEm princpio, a dificuldade de um problema de restries est relacionada com a densidade do seu grafo. Intuitivamente, quanto mais denso fr o grafo, mais difcil o problema, j que h mais oportunidades de invalidar uma etiqueta composta.No confundir a dificuldade de um problema com a dificuldade de resolver um problema. Em particular, um problema pode ser trivialmente verificado como impossvel!A dificuldade de um problema est tambm relacionada com a dificuldade de cada restrio. Essa dificuldade pode ser avaliada atravs do seu grau de aperto (tightness).

Domnios FinitosDefinio (Grau de Aperto de uma Restrio):Dada uma restrio R sobre as variveis X1 ... Xn, com domnios D1 a Dn, o grau de aperto da restrio R dado pela razo entre o nmero de etiquetas que a definem e a cardinalidade do produto cartesiano D1 x D2 x .. Dn.Por exemplo, a restrio R13 no problemas das 4 rainhas, definida sobre as variveis X1 e X3 com domnios 1..4R13 = {, , , , , , , } tem um grau de aperto de 8/(4*4) = 1/2.Este conceito pode ser generalizado para o problema como um todo.

Domnios FinitosDefinio (Grau de Aperto de um Problema):O grau de aperto de um problema definido nas variveis X1 ... Xn, obtido pela razo entre o nmero das suas solues e a cardinalidade do produto cartesiano D1 x D2 x .. Dn.Por exemplo, o problema das 4 rainhas que admite as solues e

tem um grau de aperto de 2/4*4*4*4 = 1/128.

Domnios FinitosA dificuldade de resolver um problema de restries est relacionada quer com a densidade do seu grafo, quer com o seu grau de aperto.Na realidade, para testar algoritmos de resoluo de problemas de restries so criadas aleatoriamente instncias de problemas parametrizadas pelos valores escolhidos para a densidade e grau de aperto das restries.O estudo destes aspectos levou a concluir sobre a existncia de uma transio de fase, entre os problemas trivialmente satisfazveis e trivialmente insatisfazveis, que necessrio ter em conta quando se testam algoritmos de resoluo.

Domnios FinitosUm outro aspecto a considerar na dificuldade de resolver um problema de restries est relacionada com a existncia de valores e etiquetas redundantes em restries.Definio (Valor Redundante):Um valor do domnio de uma varivel redundante, se no aparece em nenhuma soluo do problema.Definio (Etiqueta Redundante):Uma etiqueta composta de uma restrio redundante se ela no a projeco para as variveis da restrio de qualquer soluo do problema.

Domnios FinitosExemplo: O problema das 4 rainhas s admite as solues e . Desta forma os valores 1 e 4 so redundantes no domnio das variveis X1 e X4, e os valores 2 e 3 so redundantes no domnio das variveis X2 e X3.Por outro lado, as etiquetas e so redundantes na restrio R13.

Domnios FinitosExemplo: O problema das 4 rainhas que s admite as solues e pode ser simplificado por eliminao dos valores e etiquetas redundantes.

Domnios FinitosOs problemas inicial e simplificado so equivalentes.Definio (Problemas Equivalentes):Dois problemas P1 = e P2 = so equivalentes sse tm as mesmas variveis (i.e. V1 = V2) e o mesmo conjunto de solues.A simplificao pode igualmente ser formalizadaDefinio (Problema Reduzido):Um problema P= reduzido para P= se P e P so equivalentes;os domnios Dx esto includos em Dx; eas restries R so igualmente ou mais restritivas que as restries de R.

Resoluo Construtiva em Domnios FinitosComo se viu antes, e independentemente de se poder reduzir o problema, um processo de gerao e teste muito ineficiente. Assim prefervel utilizar um processo de resoluo construtivo e incremental. Neste processo, uma etiqueta composta vai sendo completada (aspecto construtivo), varivel a varivel (aspecto incremental), at se atingir uma soluo. No entanto h que garantir que em cada passo de completamento da etiqueta composta, a etiqueta resultante ainda tem potencial para atingir uma soluo.

Resoluo Construtiva em Domnios FinitosIdealmente, uma etiqueta composta dever ser a projeco de uma soluo do problema. Infelizmente, num processo de resoluo do problema, no se conhecem (geralmente) as solues!Assim, pode recorrer-se a uma noo mais fraca, nomeadamente a noo de soluo parcialDefinio (Soluo Parcial-k):Uma soluo parcial de um problema de satisfao de restries P = uma etiqueta composta sobre um subconjunto de k das variveis V do problema que satisfaz todas as restries de R definidas completamente por essas variveis.

Resoluo Construtiva em Domnios FinitosEste o princpio de resoluo dos problemas de restries de domnios finitos atravs do retrocesso. Este processo pode ser visto como uma pesquisa em rvore, em que as solues parciais correspondem aos ns da rvore e as solues s suas folhas.

Resoluo Construtiva em Domnios FinitosQuanto mais reduzido fr um problema mais fcil ser, em princpio resolv-lo.Com efeito, dado um problema P= com n variveis (i.e. V = {X1,..,Xn}) o espao de pesquisa potencial onde se podero encontrar solues (ou seja as folhas da rvore de pesquisa onde se encontram etiquetas compostas do tipo {, ..., }), tem uma cardinalidade#S = #D1 * #D2 * ... * #Dn Sendo a cardinalidade dos domnios idnticas (#Di = d) o espao de pesquisa#S = d n exponencial na dimenso n do problema.

Resoluo Construtiva em Domnios FinitosSe em vez de cardinalidade d do problema inicial, se trabalhar num problema reduzido em que a cardinalidade dos domnios fr d (

Resoluo Construtiva em Domnios FinitosNa prtica, esta reduo potencial do espao de pesquisa tem um custo, correspondente computao dos valores (e etiquetas) redundantes. Uma anlise detalhada do processo extremamente complexa de uma forma geral, pois o processo depende muito da instncia do problema em causa. No entanto, em geral, podemos considerar que o esforo computacional na reduo de domnios no proporcional reduo obtida tornando-se cada vez menos eficiente. Assim, a partir de um certo ponto a reduo do espao de pesquisa j no compensa, pois acarreta um maior aumento da computao para atingir essa reduo!

Resoluo Construtiva em Domnios FinitosQualitativamente, este processo pode ser apresentado atravs do seguinte grfico

Resoluo Construtiva em Domnios FinitosO esforo de reduo de domnios deve ser entendida no esquema de resoluo de problema que alterna enumerao com propagao.Com efeito, na especificao de um programa (em Programao em Lgica com Restries) o lanamento das restries antecede a enumerao das variveis.Problema ( Vars):- Declarao de Variveis e Domnios, Lanamento das Restries, Enumerao das Variveis.No entanto o esquema de execuo alterna a enumerao com a propagao (reduo do problema) durante o completar de uma soluo parcial.

Resoluo Construtiva em Domnios FinitosAssim dado um problema com n variveis X1 a Xn o esquema de execuo segue o seguinte padro: Declarao de Variveis e Domnios, Lanamento das Restries, indomain(X1),% escolha com retrocesso propagao indomain(X2), % escolha com retrocesso propagao, ... indomain(Xn-1) % escolha com retrocesso propagao indomain(Xn) % escolha com retrocessoH pois que balancear o esforo na reduo com os resultados obtidos na reduo dos domnios.

Reduo de DomniosApesar de se ter definido formalmente a reduo de um problema de restries no foi apresentada nenhum procedimento para o obter.Pior, nem sequer foi definido um procedimento para reconhecer se um problema uma reduo do problema inicial.Com efeito, a definio pressupe que o problema reduzido seja equivalente ao inicial, isto que tenha as mesmas solues. No entanto, essas solues no so, em geral, conhecidas!Assim, o que se pode estudar so critrios que permitam garantir que no processo de reduo no se perdem solues.

Reduo de DomniosEsses critrios de consistncia permitem estabelecer valores redundantes nos domnios das variveis, de uma forma indirecta, isto , sem requerer o conhecimento dos valores que pertencem a solues do problema.Mais exactamente, a manuteno destes critrios durante a resoluo do problema permite a eliminao destes valores redundantes.Em problemas de restries binrias, os critrios mais comuns so, com complexidade crescente, os seguintesConsistncia dos NConsistncia dos ArcoConsistncia dos Caminho

Reduo de DomniosDefinio (Consistncia de N):Um problema de restries tem os ns consistentes, se nenhum valor no domnio das variveis violar as restries unrias.Este critrio pode parecer bvio e intil. Ningum vai especificar domnios para as variveis que no satisfaam partida as restries unrias!No entanto, este critrio deve ser entendido no contexto do completar de uma soluo parcial, tal como discutido atrs.

Reduo de DomniosExemplo: Aps o lanamento das restries, a rede de restries do problema das 4 rainhas a seguinte:Aps a enumerao da varivel X1, com a escolha de X1=1, as restries R12, R13 e R14 tornam-se unrias!

Reduo de DomniosA manuteno da consistncia dos ns dever retirar do domnio das variveis os valores apropriados. Consegue-se assim uma reduo de domnios semelhante que se conseguia no caso das restries booleanas.

Reduo de DomniosManuteno de Consistncia de NsDada a simplicidade do critrio de consistncia de ns, o algoritmo para proceder sua manuteno bastante simples e de baixa complexidade. Um possvel algoritmo para manter a consistncia de ns o algoritmo NC-1procedimento NC-1(V, D, R); para X in V para v in Dx fazer se no satisfaz(X-v, Cx) ento Dx

Reduo de DomniosComplexidade espacial do algoritmo NC-1Havendo n variveis no problema, cada qual com d valores no seu domnio, e assumindo-se uma representao por extenso dos domnios das variveis, necessrio um espao de nd para guardar os domnios das variveis.Por exemplo, o domnio inicial 1..4 das variveis Xi do problema das 4 rainhas, representado pelos vectores booleanos Xi = [1,1,1,1] ou 1111. Aps a enumerao X1=1 e a manuteno de coerncia de ns, os domnios ficamX1 = 1000, X2 = 0011, X3 = 0101 e X4 = 0110O algoritmo NC-1 no requer espao adicional, pelo que tem uma complexidade espacial O(nd).

Reduo de DomniosComplexidade temporal do algoritmo NC-1Havendo n variveis no problema, cada qual com d valores no seu domnio, e tendo em conta que cada valor avaliado uma vez, fcil concluir que o algoritmo tem uma complexidade O(nd).Em geral, a baixa complexidade temporal e espacial permite que o procedimento NC-1 seja utilizado muito eficientemente na propagao de restries.No entanto, a manuteno de consistncia de ns, no permite detectar todas as redues possveis dos domnios das variveis.

Reduo de DomniosUm critrio mais exigente (e complexo) que a consistncia de ns o de Consistncia de ArcosDefinio (Consistncia de Arco):Um problema de restries tem os arcos consistentes, (est numa forma consistente de arcos) se, Tiver todos os ns consistentes; ePara qualquer etiqueta Xi-vi de qualquer varivel Xi, e para todas as restries Rij, envolvendo as variveis Xi e Xj, deve existir um valor vj de suporte, isto , tal que a etiqueta composta {Xi-vi, Xj-vj} satisfaz a restrio Rij.

Reduo de DomniosExemplo: Aps a enumerao da varivel X1, com a escolha de X1=1, a rede de restries do problema das 4 rainhas, e os domnios das suas variveis so os seguintes:No entanto a etiqueta X2-3 no tem suporte na varivel X3, j que nem a etiqueta composta {X2-3 , X3-2} nem a etiqueta {X2-3 , X3-4} satisfazem a restrio R23.Assim, o valor 3 pode ser removido do domnio de X2.

Reduo de DomniosNa realidade, nenhum dos valores de X3 tem suporte nas variveis X2 e X4! Com efeito,a etiqueta X3-4 no tem suporte na varivel X2, j que nenhuma das etiquetas {X2-3, X3-4} e {X2-4, X3-4} satisfazem a restrio R23.a etiqueta X3-2 no tem suporte na varivel X4, j que nenhuma das etiquetas {X3-2, X4-2} e {X3-2, X4-3} satisfazem a restrio R34.

Reduo de DomniosComo nenhum dos valores de X3 tem suporte nas variveis X2 e X4, a manuteno de arco deve tornar vazio o domnio de X3!Assim, a simples manuteno de consistncia de arco no s reduz o domnio das variveis como tambm antecipa a deteco de insatisfazibilidade.Desta forma, o retrocesso de X1=1 pode ser iniciado, sem se terem atribudo (e retrocedido) valores s restantes variveis, nomeadamente varivel X2.

Reduo de DomniosManuteno de Consistncia de ArcosUm algoritmo muito simples para impr a consistncia de arcos o algoritmo AC-1, descrito abaixoprocedimento AC-1(V, D, R); NC-1(V,D,R);% impe a consistncia de ns Q = {aij | Rij R Rji R }; % ver nota repetir alterado

Reduo de DomniosManuteno de Consistncia de Arcos (cont.)O predicado rev_dom(aij,V,D,R) sucede se eliminar valores do domnio das variveis (como um efeito lateral).

predicado rev_dom(aij,V,D,R): Booleano; sucede

Reduo de DomniosComplexidade temporal do algoritmo AC-1Assumindo n variveis no problema, cada com d valores no seu domnio, e sendo os arcos em nmero de a, no pior caso, o predicado rev_dom, verifica d2 pares de valores.O nmero de arcos aij na fila Q de 2a (para cada restrio Rij so considerados arcos dirigidos aij e aji). Por cada valor removido, rev_dom chamado 2a vezes.No pior caso, por cada ciclo removido um valor de uma s varivel, pelo que o ciclo pode ser executado nd vezes.Tendo em conta estes factores, a complexidade temporal do AC-1 , no pior caso, O( d2 * 2a * nd), i.e. O(nad3)

Reduo de DomniosComplexidade espacial do algoritmo AC-1O algoritmo AC-1 tem de manter uma fila Q, com comprimento mximo de 2a. Assim a complexidade espacial inerente do algoritmo AC-1 O(a).A este espao h que acrescentar o espao destinado representao dos domnios O(nd) e para representar as restries do problema. Existindo a restries e d valores no domnio de cada varivel o espao necessrio de O(ad2), sendo o total de O(nd + ad2).Para redes de restries densas, a n2/2. Pelo que este termo domina a complexidade espacial total que O(ad2).

Reduo de DomniosIneficincia do algoritmo AC-1Cada vez que um valor vi removido do domnio de uma varivel Xi, pelo predicado rev_dom(aij,V,D,R), todos os arcos so reexaminados. Na realidade, apenas os arcos aki (para k i e k j ) deveriam ser reexaminados.Com efeito, a remoo de vi pode eliminar o suporte de um valor vk de uma varivel Xk para a qual existe uma restrio Rki (ou Rik).Essa ineficincia eliminada no algoritmo AC-3.

Reduo de Domnios

procedimento AC-3(V, D, R); NC-1(V,D,R); % impe a consistncia de ns Q = {aij | Rij R Rji R }; enquanto Q fazer Q = Q \ {aij} % remove um elemento de Q se rev_dom(aij,V,D,R) ento Q = Q {aki | Rki R k i k j} at no alteradofim procedimento

Como intuitivo, e para alm de uma melhor complexidade tpica, a complexidade para o pior caso do algoritmo AC-3 melhor que a do AC-1.

Reduo de DomniosComplexidade temporal do algoritmo AC-3Cada arco aki s inserido quando um valor vi eliminado do domnio de Xi. No total, cada um dos 2a arcos pode ser inserido (e removido) d vezes da fila Q.Cada vez que removido um arco, chamado o predicado rev_dom, que verifica no mximo d2 pares de valores.Tendo em conta todos estes, e em contraste com o algoritmo AC-1 de complexidade temporal O(nad3), a complexidade temporal do algoritmo AC-3, pior caso, O(2ad * d2), ou seja O(ad3)