Programação de restrição

Da Wikipédia, a enciclopédia livre
Ir para a navegação Saltar para pesquisar

A programação de restrições (CP) [1] é um paradigma para resolver problemas combinatórios que se baseia em uma ampla gama de técnicas de inteligência artificial , ciência da computação e pesquisa operacional . Na programação de restrições, os usuários declaram as restrições das soluções viáveis ​​para um conjunto de variáveis ​​de decisão. As restrições diferem das primitivas comuns da programação imperativalinguagens na medida em que não especificam uma etapa ou sequência de etapas a serem executadas, mas sim as propriedades de uma solução a ser encontrada. Além das restrições, os usuários também precisam especificar um método para resolver essas restrições. Isso normalmente se baseia em métodos padrão como retrocesso cronológico e propagação de restrição , mas pode usar código personalizado como uma heurística de ramificação específica do problema .

A programação de restrição tem sua raiz e pode ser expressa na forma de programação lógica de restrição , que incorpora restrições em um programa lógico . Esta variante de programação lógica deve-se a Jaffar e Lassez, [2] que estenderam em 1987 uma classe específica de restrições que foram introduzidas no Prolog II . As primeiras implementações de programação lógica de restrição foram Prolog III , CLP(R) e CHIP .

Em vez de programação lógica, as restrições podem ser combinadas com programação funcional , reescrita de termos e linguagens imperativas . As linguagens de programação com suporte integrado para restrições incluem Oz (programação funcional) e Kaleidoscope (programação imperativa). Principalmente, as restrições são implementadas em linguagens imperativas por meio de kits de ferramentas de resolução de restrições , que são bibliotecas separadas para uma linguagem imperativa existente.

Programação lógica de restrição

A programação de restrições é uma incorporação de restrições em uma linguagem host. As primeiras linguagens de host usadas foram linguagens de programação lógica , então o campo foi inicialmente chamado de programação lógica de restrição . Os dois paradigmas compartilham muitos recursos importantes, como variáveis ​​lógicas e retrocesso . Hoje, a maioria das implementações do Prolog inclui uma ou mais bibliotecas para programação de lógica de restrição.

A diferença entre os dois está em grande parte em seus estilos e abordagens para modelar o mundo. Alguns problemas são mais naturais (e, portanto, mais simples) para escrever como programas lógicos, enquanto alguns são mais naturais para escrever como programas de restrição.

A abordagem de programação de restrições é procurar um estado do mundo no qual um grande número de restrições seja satisfeito ao mesmo tempo. Um problema é tipicamente declarado como um estado do mundo contendo um número de variáveis ​​desconhecidas. O programa de restrição procura valores para todas as variáveis.

A programação de restrição simultânea temporal (TCC) e a programação de restrição simultânea temporal não determinística (MJV) são variantes de programação de restrição que podem lidar com o tempo.

Problema de satisfação de restrições

Uma restrição é uma relação entre múltiplas variáveis ​​que limita os valores que essas variáveis ​​podem assumir simultaneamente.

Definição  —  Um problema de satisfação de restrições em domínios finitos (ou CSP) é definido por um tripletoOnde:

  • é o conjunto de variáveis ​​do problema;
  • é o conjunto de domínios das variáveis, ou seja, para todostemos;
  • é um conjunto de restrições. Uma restriçãoé definido por um conjuntode variáveis ​​e uma relaçãoque define o conjunto de valores permitidos simultaneamente para as variáveis ​​de:

Existem três categorias de restrições:

  • restrições extensionais: as restrições são definidas pela enumeração do conjunto de valores que as satisfariam;
  • restrições aritméticas: as restrições são definidas por uma expressão aritmética, ou seja, usando;
  • restrições lógicas: as restrições são definidas com uma semântica explícita, ou seja, AllDifferent , AtMost , ...

Definição  —  Uma atribuição (ou modelo)de um CSPé definido pelo casalOnde:

  • é um subconjunto de variável;
  • é a tupla dos valores tomados pelas variáveis ​​atribuídas.

Atribuição é a associação de uma variável a um valor de seu domínio. Uma atribuição parcial é quando um subconjunto das variáveis ​​do problema foi atribuído. Uma atribuição total é quando todas as variáveis ​​do problema foram atribuídas.

Propriedade  -  Dadouma atribuição (parcial ou total) de um CSP, euma restrição detal como, a atribuiçãosatisfaz a restriçãose e somente se todos os valoresdas variáveis ​​da restriçãopertence a.

Definição  —  Uma solução de um CSP é uma atribuição total que satisfaça todas as restrições do problema.

Durante a busca das soluções de um CSP, um usuário pode desejar:

  • encontrar uma solução (satisfazendo todas as restrições);
  • encontrar todas as soluções do problema;
  • comprovando a insatisfatibilidade do problema.

Problema de otimização de restrições

Um problema de otimização de restrições (COP) é ​​um problema de satisfação de restrições associado a uma função objetivo.

Uma solução ótima para um COP de minimização (maximização) é uma solução que minimiza (maximiza) o valor da função objetivo .

Durante a busca das soluções de um CSP, um usuário pode desejar:

  • encontrar uma solução (satisfazendo todas as restrições);
  • encontrar a melhor solução em relação ao objetivo;
  • comprovando a otimalidade da melhor solução encontrada;
  • comprovando a insatisfatibilidade do problema.

Modelos de Perturbação vs Refinamento

As linguagens para programação baseada em restrições seguem uma das duas abordagens: [3]

  • Modelo de refinamento: as variáveis ​​no problema são inicialmente não atribuídas e cada variável é considerada capaz de conter qualquer valor incluído em seu intervalo ou domínio. À medida que a computação progride, os valores no domínio de uma variável são podados se forem incompatíveis com os valores possíveis de outras variáveis, até que um único valor seja encontrado para cada variável.
  • Modelo de perturbação: as variáveis ​​do problema recebem um único valor inicial. Em momentos diferentes uma ou mais variáveis ​​recebem perturbações (mudanças em seu valor antigo), e o sistema propaga a mudança tentando atribuir novos valores a outras variáveis ​​que sejam consistentes com a perturbação.

A propagação de restrições em problemas de satisfação de restrições é um exemplo típico de modelo de refinamento, e planilhas são um exemplo típico de modelo de perturbação.

O modelo de refinamento é mais geral, pois não restringe as variáveis ​​a terem um único valor, podendo levar a várias soluções para o mesmo problema. No entanto, o modelo de perturbação é mais intuitivo para programadores que usam linguagens orientadas a objetos com restrições imperativas mistas. [4]

Domínios

As restrições usadas na programação de restrições são tipicamente sobre alguns domínios específicos. Alguns domínios populares para programação de restrição são:

Domínios finitos é um dos domínios mais bem-sucedidos da programação de restrições. Em algumas áreas (como pesquisa operacional ) a programação de restrições é frequentemente identificada com programação de restrições sobre domínios finitos.

Propagação de restrições

Condições de consistência local são propriedades de problemas de satisfação de restrições relacionadas à consistência de subconjuntos de variáveis ​​ou restrições. Eles podem ser usados ​​para reduzir o espaço de busca e tornar o problema mais fácil de resolver. Vários tipos de condições de consistência local são aproveitados, incluindo consistência de nó, consistência de arco e consistência de caminho .

Cada condição de consistência local pode ser imposta por uma transformação que altera o problema sem alterar suas soluções. Tal transformação é chamada de propagação de restrição . [5] A propagação de restrições funciona reduzindo domínios de variáveis, fortalecendo restrições ou criando novas. Isso leva a uma redução do espaço de busca, tornando o problema mais fácil de resolver por alguns algoritmos. A propagação de restrições também pode ser usada como um verificador de insatisfatibilidade, incompleto em geral, mas completo em alguns casos particulares.

Resolução de restrições

Existem três técnicas algorítmicas principais para resolver problemas de satisfação de restrições: busca de retrocesso, busca local e programação dinâmica. [1]

Pesquisa de retrocesso

A busca de retrocesso é um algoritmo geral para encontrar todas (ou algumas) soluções para alguns problemas computacionais , notadamente problemas de satisfação de restrições , que constrói incrementalmente candidatos para as soluções e abandona um candidato ("backtracks") assim que determina que o candidato não pode possivelmente ser completado para uma solução válida.

Pesquisa local

A busca local é um método incompleto para encontrar uma solução para um problema . Baseia-se em melhorar iterativamente uma atribuição das variáveis ​​até que todas as restrições sejam satisfeitas. Em particular, os algoritmos de busca local normalmente modificam o valor de uma variável em uma atribuição em cada etapa. A nova atribuição está próxima da anterior no espaço de atribuição, daí o nome pesquisa local .

Programação dinâmica

A programação dinâmica é um método de otimização matemática e um método de programação de computador. Refere-se à simplificação de um problema complicado, dividindo-o em subproblemas mais simples de maneira recursiva . Embora alguns problemas de decisão não possam ser separados dessa maneira, as decisões que abrangem vários pontos no tempo geralmente se separam recursivamente. Da mesma forma, na ciência da computação, se um problema pode ser resolvido de forma ótima dividindo-o em subproblemas e, em seguida, encontrando recursivamente as soluções ótimas para os subproblemas, diz-se que ele tem subestrutura ótima .

Exemplo

A sintaxe para expressar restrições sobre domínios finitos depende do idioma do host. O seguinte é um programa Prolog que resolve o quebra-cabeça alfamético clássico SEND+MORE=MONEY na programação de lógica de restrição:

% Este código funciona tanto no YAP quanto no SWI-Prolog usando a 
biblioteca de solucionador de restrições % CLPFD fornecida pelo ambiente. Pode exigir pequenas modificações para funcionar 
% em outros ambientes Prolog ou usando outros solucionadores de restrições. 
:-  use_module ( biblioteca ( clpfd )). 
sendmore ( Digits )  :- 
   Digits  =  [ S , E , N , D , M , O , R , Y ],    % Criar variáveis 
   ​​Digits  ins  0..9 ,                % Associar domínios a variáveis 
   ​​S  #\=  0 ,                         % Restrição: S deve ser diferente de 0 
   M  #\=  0 , 
   all_different ( Digits ),           % todos os elementos devem ter valores diferentes 
                1000 * S  +  100 * E  +  10 * N  +  D      % Outras restrições 
              +  1000 * M  +  100 * O  +  10 * R  +  E 
   #=  10000 * M  +  1000* O  +  100 * N  +  10 * E  +  Y , 
   etiqueta ( Dígitos ).                   % Iniciar a pesquisa

O intérprete cria uma variável para cada letra do quebra-cabeça. O operador insé usado para especificar os domínios dessas variáveis, de forma que elas alcancem o conjunto de valores {0,1,2,3, ..., 9}. As restrições S#\=0e M#\=0significa que essas duas variáveis ​​não podem assumir o valor zero. Quando o interpretador avalia essas restrições, ele reduz os domínios dessas duas variáveis ​​removendo o valor 0 delas. Em seguida, a restrição all_different(Digits)é considerada; ele não reduz nenhum domínio, por isso é simplesmente armazenado. A última restrição especifica que os dígitos atribuídos às letras devem ser tais que "SEND+MORE=MONEY" seja mantido quando cada letra for substituída por seu dígito correspondente. A partir desta restrição, o solver infere que M=1. Todas as restrições armazenadas envolvendo a variável M são despertadas: neste caso,a propagação da restrição na all_differentrestrição remove o valor 1 do domínio de todas as variáveis ​​restantes. A propagação de restrições pode resolver o problema reduzindo todos os domínios a um único valor, pode provar que o problema não tem solução reduzindo um domínio ao conjunto vazio, mas também pode terminar sem provar satisfatibilidade ou insatisfatibilidade. Os literais de rótulo são usados ​​para realmente realizar a pesquisa de uma solução.

Veja também

Referências

  1. ^ a b Rossi, Francesca; Beek, Peter Van; Walsh, Toby (2006-08-18). Manual de programação de restrições . Elsevier. ISBN 9780080463803.
  2. ^ Jaffar, Joxan e JL. Lassez. " Programação lógica de restrição ." Anais do 14º simpósio ACM SIGACT-SIGPLAN sobre Princípios de linguagens de programação. ACM, 1987.
  3. ^ Mayoh, Brian; Tyugu, Enn; Penjam, Jaan (1993). Programação de restrições . Springer Science+Business Media . pág. 76. ISBN 9783642859830.
  4. ^ Lopez, G., Freeman-Benson, B., & Borning, A. (1994, janeiro). Caleidoscópio: Uma linguagem de programação imperativa de restrição. Em Programação de Restrições (pp. 313-329). Springer Berlim Heidelberg.
  5. Bessiere, Christian (2006), "Constraint Propagation", Handbook of Constraint Programming , Foundations of Artificial Intelligence, vol. 2, Elsevier, pp. 29–83, doi : 10.1016/s1574-6526(06)80007-6 , ISBN 9780444527264

Links externos