Busca com Satisfação de Restrições

Inteligência Artificial

Pontifícia Universidade Católica de Campinas

Prof. Dr. Denis M. L. Martins

Objetivos de Aprendizagem

• Formalizar e modelar CSPs: Identificar variáveis, domínios e restrições em problemas.
• Compreender técnicas de busca em CSP (força bruta, backtracking, etc.)
• Aplicar heurísticas em CSP paraotimizar a ordem de escolha das variáveis e valores.
• Avaliar desempenho: Medir tempo, backtracks e profundidade.

Exemplo de Motivação

Exemplo de Motivação (cont.)

• Variáveis:
• Domínio:
• Restrições:
• Solução:
  • Uma solução possível

Fonte da Imagem: Resumos LEIC-A.

Busca com Satisfação de Restrições (CSP)

• CSP (Constraint Satisfaction Problem): Problema onde se busca uma atribuição de valores a variáveis que satisfaça todas as restrições.
• Componentes principais:
  • Estado : conjunto de variáveis
  • Domínio : domínio discreto da variável
  • Restrições : conjunto de restrições
    • Unárias: sobre uma única variável
    • Binárias: sobre duas variáveis
    • N-árias: sobre várias variáveis

• Solução: atribuição tal que todas as são satisfeitas.

N-Queens: Exemplo clássico de CSP

Vamos jogar o N-Queens Puzzle:

https://www.n-queens.com/

CSP no Cotidiano: Aplicações Práticas

Sudoku: Mais um exemplo de CSP

Sudoku: Exemplo

Fonte da Imagem: Wikipedia.

Sudoku: Formalização

• Variáveis: para . Total de variáveis.
• Domínios: (ou o valor já dado no enunciado).
• Restrições Binárias:
  • Linha: para todos .
  • Coluna: para todos .
  • Bloco : se ambos pertencem ao mesmo bloco.
• Restrições N‑Árias:
  • Equivalentemente, cada conjunto (linha/coluna/bloco) deve conter valores distintos – pode ser expressa como restrição "todos diferentes".
• Problema de Busca:
  

Sukodu: Modelagem

• Domínio:

• Restrição de Linha:
• Restrição de Coluna:
• Restrição de Bloco: Para bloco com :
• Solução:

Algoritmo por Força Bruta

Backtracking

• DFS não considera informações sobre restrições: continua percorrendo o grafo de busca mesmo que uma restrição já tenha sido violada.
  • Exploração inútil
  • Pode ser aplicado a CSPs sem modificações, porém a taxa de sucesso depende fortemente da ordem de atribuição.

• Backtracking: Variante especializada do DFS que incorpora checagem de consistência no momento da atribuição.
  • Ao detectar violação de restrição, revira imediatamente para o nível anterior (backtrack), evitando a exploração de sub‑árvores inviáveis.
  • Integra heurísticas de escolha de variável e valor (MRV, LCV) que reduzem drasticamente o espaço de busca em CSPs típicos.
  • Exige manutenção adicional de estruturas de dados (domínios restritos, histórico de escolhas), aumentando a sobrecarga de memória.

Backtracking N-Queens

Backtracking: Sudoku

• Procedimento recursivo: escolhe uma variável, tenta um valor do domínio e verifica restrições locais.
• Se falhar, volta ("backtrack") ao passo anterior.

function BACKTRACK_SUDOKU(board):
    if board is complete: return board
    (r,c) = select_unassigned_cell(board)   // MRV + LCV
    for val in order_domain_values(r,c,board): // LCV
        if consistent(r,c,val,board):
            board[r][c] = val
            result = BACKTRACK_SUDOKU(board)
            if result != failure: return result
            board[r][c] = 0          // undo
    return failure

Backtracking: Colorir Mapa

Fonte da Imagem: Resumos LEIC-A.

Forward Checking (FC)

• Após atribuir , elimina de cada vizinho valores incompatíveis com .
• Se algum domínio ficar vazio → falha imediata.

Complexidade amortizada: (onde ).

Heurísticas de Seleção

Restrições Leves (Soft Constraints)

• Também é possível definir restrições que podem ser quebradas
• Geralmente associadas a um custo ou preferências
• Ex.: Priorizar o uso das cores na ordem vermelho, verde, azul
• Pode ser resolvido associando custos à cada valor do domínio, podendo ser tratado como problema de otimização
• Também pode ser resolvido ordenando a expansão da busca

Resumo e Próximos Passos

Perguntas e Discussão

• Qual a diferença fundamental entre backtracking puro e forward checking? Em que situações o custo adicional do forward checking vale a pena?
• Como a heurística MRV (Minimum Remaining Values) influencia a profundidade da árvore de busca? Pode haver casos em que escolher a variável com mais valores restantes seja mais vantajoso?
• Como a escolha do modelo de domínio (por exemplo, representar cada linha como uma variável vs. usar variáveis binárias para cada célula) afeta a eficiência das técnicas de CSP? Quais trade‑offs surgem na modelagem de problemas com muitos valores distintos por variável?
• Quais são os principais desafios ao adaptar algoritmos de CSP para domínios contínuos ou híbridos (contínuo + discreto)?