Agentes que resolvem
problemas
Resolução de Problemas
o Como é que um agente pode
definir os seus objectivos e traçar
sequências de acções que o
podem levar a atingir esses
mesmos objectivos ?
o O objectivo e o conjunto de meios
necessários para o atingir é
designado por problema e o
processo levado a cabo para
explorar esses meios é designado
por pesquisa.
© Noel de Jesus Mendonça Lopes
o Um agente pode deliberar o que fazer
considerando para tal os resultados das
sequências de acções que pode tomar.
o Estes agentes (problem-solving agents) são
um tipo especifico dos agentes baseados
em objectivos.
o Decidem o que fazer através da procura de
sequências de acções que levem a estados
desejáveis.
o A formulação do objectivo, baseando-nos
na situação actual, é o primeiro passo para
a resolução de um problema.
1
© Noel de Jesus Mendonça Lopes
Objectivo
Objectivo
o Nesta fase consideramos o objectivo como
sendo um conjunto de estados do mundo,
em que determinado critério é satisfeito.
o As acções podem ser vistas como sendo
responsáveis pelas transições entre
estados, pelo que o agente deverá
encontrar a sequência de acções que
permitem chegar a um dos estados do
mundo onde o objectivo é satisfeito.
o Antes de procurar a sequência de
acções que permitem atingir o
objectivo, o agente deverá decidir
quais os estados e as acções que
deve considerar.
o Formulação do problema –
Processo de decisão das acções e dos
estados a considerar (passo seguinte
à formulação do objectivo).
© Noel de Jesus Mendonça Lopes
3
© Noel de Jesus Mendonça Lopes
2
4
1
Pesquisa
o Um agente que disponha de várias opções
imediatas, cujo resultado é desconhecido,
pode decidir o que fazer através da análise
de diferentes sequências de acções que
levam a estados cujo resultado é
conhecido.
o O agente pode posteriormente escolher a
sequência de acções que o beneficia mais.
o Um algoritmo de pesquisa tem como
entrada um problema e como saída uma
solução, na forma de uma sequência de
acções.
© Noel de Jesus Mendonça Lopes
5
Formular, procurar e executar
6
Agentes que resolvem problemas
o Uma vez encontrada uma solução, o
agente pode levar a cabo a sequência
de acções associada. Esta fase é
designada por execução.
© Noel de Jesus Mendonça Lopes
© Noel de Jesus Mendonça Lopes
function AgenteSimpleResolucaoProblemas(p) returns accao
inputs : p, percepções
static : a, uma sequência de acções inicialmente vazia
estado, descrição do estado do mundo actual
o, um objectivo, inicialmente nulo
problema, a formulação de um problema
estado ← ActualizaEstado(estado, p)
if a is empty then
o ← FormulaObjectivo(estado)
problema ← FormulaProblema(estado, o)
a ← Pesquisa(problema)
end
accao ← Recomendada(a, estado)
a ← Resto(a, estado)
return accao
7
© Noel de Jesus Mendonça Lopes
8
2
Aspirar o lixo
1
2
Tipos de problemas
3
o Estado único (single-state)
4
n Ambiente acessível;
n Agente sabe as consequências das suas
acções.
o Estados múltiplos (multiple-state)
5
6
7
n Ambiente inacessível;
n Agente sabe as consequências das suas
acções.
8
© Noel de Jesus Mendonça Lopes
9
Ignorância dos efeitos das
acções
© Noel de Jesus Mendonça Lopes
10
Ignorância dos efeitos das
acções
Problema de estados múltiplos
2
Lei de Murphy
Ambiente estocástico
Aspirar
Direita
Aspirar
6
(não deteministico
deteministico))
8
© Noel de Jesus Mendonça Lopes
11
© Noel de Jesus Mendonça Lopes
12
3
Ignorância dos efeitos das
acções
Problemas de contingência
Impede o agente de encontrar uma sequência de acções
que garanta uma solução para o problema.
1
2
4
?
© Noel de Jesus Mendonça Lopes
8
o Se o agente dispuser de um sensor
que lhe indique se a sala onde se
encontra está limpa, poderá aspirar
apenas se esta tiver lixo.
o É necessário obter informações a
partir dos sensores durante a fase de
execução.
o Problemas reais a previsão exacta é
impossível.
13
© Noel de Jesus Mendonça Lopes
14
Problemas de exploração
Problemas
o Tipo de problema mais difícil para um
agente, já que este não dispõe de nenhum
conhecimento sobre os efeitos das suas
acções.
o O agente deve experimentar e descobrir de
forma gradual as consequências das suas
acções bem como os tipos de estado
existentes (Ex: Recém nascidos).
o A pesquisa é feita no mundo real em vez de
num modelo, pelo que pode representar um
risco significativo para um agente
ignorante.
o Problema - Colecção de informação
que o agente pode usar para decidir o
que fazer.
o Os elementos básicos de um
problema são os estados e as acções.
© Noel de Jesus Mendonça Lopes
© Noel de Jesus Mendonça Lopes
15
16
4
Problemas de estado único
Espaço dos estados
o Dado um estado inicial no qual o agente
sabe que se encontra.
o Dado um conjunto de acções disponíveis
para o agente.
o O estado inicial e o conjunto de acções
disponíveis definem o espaço dos estados
do problema : O conjunto de todos os
estados que se podem atingir a partir do
estado inicial e de uma qualquer sequência
de acções.
o Um caminho no espaço dos estados é
simplesmente uma sequência de acções
que vão de um estado para outro.
n Operador : Uma descrição de uma acção em
termos do estado que será alcançado quando a
acção em causa é levada a cabo num dado
estado.
n Função Sucessor S : Dado um estado x, S(x)
retorna o conjunto de estados que se podem
alcançar aplicando uma única acção no estado x.
© Noel de Jesus Mendonça Lopes
17
© Noel de Jesus Mendonça Lopes
Problemas de estado único
Problemas de estado único
o Dado um teste de objectivo que o agente
pode aplicar a uma descrição de um estado
para determinar se esse estado é um
estado que satisfaz objectivo.
o Dada uma função de custo do
caminho :
n Nalguns casos existe um conjunto explicito de
todos os estados que satisfazem o objectivo;
n Noutros, o objectivo é especificado através de
uma propriedade abstracta (Ex: Xadrez).
© Noel de Jesus Mendonça Lopes
19
18
n A soma dos custos das acções individuais
ao longo do caminho.
n Normalmente designa-se por g.
© Noel de Jesus Mendonça Lopes
20
5
Saída de um algoritmo de
pesquisa
Problema de estado único
Estado inicial
+
Conjunto de operadores
+
Teste de objectivo
+
Custo do caminho
© Noel de Jesus Mendonça Lopes
Solução
Caminho desde o estado inicial até um
estado que satisfaça o teste de objectivo.
21
© Noel de Jesus Mendonça Lopes
22
Problemas de estados múltiplos
Problemas de estados múltiplos
Conjunto de estados iniciais
+
Conjunto de operadores
+
Teste de objectivo
+
Custo do caminho
o Quando se aplica um operador a um conjunto de
estados obtemos a reunião de todos os estados que
se atingem aplicando o operador individualmente a
cada um dos estados.
o Um caminho liga vários conjuntos de estados.
o Uma solução é o caminho que leva a um conjunto
de estados, em que todos eles satisfazem o
objectivo.
o O espaço dos estados é substituído pelo espaço do
conjunto de estados.
© Noel de Jesus Mendonça Lopes
23
© Noel de Jesus Mendonça Lopes
24
6
Custo total
Eficácia da pesquisa
o Encontrou-se uma solução ?
o É uma boa solução (com um custo do
caminho baixo) ?
o Qual é o custo da pesquisa (tempo
e memória necessários para
encontrar a solução) ?
© Noel de Jesus Mendonça Lopes
Custo do caminho
+
Custo da pesquisa
25
© Noel de Jesus Mendonça Lopes
Custo da pesquisa
Abstracção
o Depende de o ambiente ser:
o Retirar tantos detalhes quanto
possível, garantindo no entanto que
cada uma das acções abstractas
podem ser levadas a cabo.
n Estático (0)
n Semi-dinâmico
n Dinâmico
26
n Descrição do estado
n Acções
n Efeitos das acções
© Noel de Jesus Mendonça Lopes
27
© Noel de Jesus Mendonça Lopes
28
7
Exemplos de problemas
Exemplos de problemas
o Puzzle com 8 peças
n Estado : A localização de cada uma das peças
(incluindo o branco).
n Operadores : Branco move-se para esquerda,
direita, cima ou baixo.
n Custo do caminho : Número de movimentos.
5
4
1
6
1
8
8
7
3
2
7
2
Problema
das
oito
rainhas
3
4
6
5
© Noel de Jesus Mendonça Lopes
29
30
Problema das oito rainhas Dimensão do espaço de procura
Problema das oito rainhas
o Teste de objectivo : 8 rainhas no
tabuleiro, não estar nenhuma a ser
atacada.
o Custo do caminho : zero.
o Estados : Qualquer combinação de 0
a 8 rainhas no tabuleiro.
o Operadores : Adicionar rainhas a
uma dada posição do tabuleiro.
© Noel de Jesus Mendonça Lopes
© Noel de Jesus Mendonça Lopes
31
o Estados : Arranjos de 8 rainhas, uma
em cada coluna.
o Operadores : Mover uma rainha
atacada, para outra posição do
tabuleiro, na mesma coluna.
648
2057
© Noel de Jesus Mendonça Lopes
32
8
Aspirador (Problema de estado
único)
o Teste de objectivo : Todas as salas
limpas.
o Custo do caminho : Cada acção
custa 1.
o Estados : Todos os estados da figura
seguinte.
o Operadores : Esquerda, direita,
aspirar.
© Noel de Jesus Mendonça Lopes
A
E
D
D
A
E
D
D
E
E
A
A
A
A
D
E
E
D
D
A
A
33
Aspirador (Problema de estados
múltiplos)
E
D
A, E
D
A
A
A
D
D
E
E
o Teste de objectivo : Todas as salas
limpas.
o Custo do caminho : Cada acção
custa 1.
o Conjunto de estados : Todos os
conjuntos da figura seguinte.
o Operadores : Esquerda, direita,
aspirar.
A
E
D
A
A
D
E
A, D
E
D
E
E
D
© Noel de Jesus Mendonça Lopes
D
E
E
A
A
D
E
A
D
A
E
35
9
Missionários e canibais
Outros problemas
o Pesquisa de rotas
n Redes de computadores
n Assistentes de viagem (computador
carro)
o Caixeiro viajante
o Navegação de robôs
o Determinar a melhor sequência de
montagem de um objecto.
© Noel de Jesus Mendonça Lopes
37
© Noel de Jesus Mendonça Lopes
Geração de sequências de
acções
Pesquisa da solução
o Ao aplicarmos os operadores ao
estado actual estamos a gerar um
novo conjunto de estados. Este
processo designa-se por expansão
do estado.
E
D
o Quando temos várias possibilidades
temos de escolher qual considerar
primeiro (determinado pela
estratégia da pesquisa).
o Escolher, testar, expandir.
38
E
A
© Noel de Jesus Mendonça Lopes
39
© Noel de Jesus Mendonça Lopes
40
10
Oradea
Árvore de pesquisa
Zerind
Arad
Estado inicial
Sibiu
Fagaras
Arad
Timisoara
Rimnicu Vilcea
Depois de expandir Arad
Lugoj
Arad
Mehadia
Pitesti
Bucharest
Dobreta
Criova
Zerind
Timisoara
Sibiu
© Noel de Jesus Mendonça Lopes
Árvore de pesquisa
Algoritmo Geral de Pesquisa
function PesquisaGeral(problema, estratégia) returns solução ou falha
Inicializar a árvore de pesquisa, utilizando o estado inicial do problema.
do
if não existem candidatos para expandir then return falha
Escolher um nó (folha) para expandir, de acordo com a estratégia
if nó contém um estado que satisfaz o objectivothen
return solução correspondente
end
Expandir o nó e adicionar os nós resultantes à arvore de pesquisa
loop
Depois de expandir Zerind
Arad
Zerind
Timisoara
Oradea
42
Sibiu
Arad
Nós de pesquisa
© Noel de Jesus Mendonça Lopes
43
© Noel de Jesus Mendonça Lopes
44
11
Estrutura dos nós
Fronteira
o O estado do espaço dos estados ao
qual o nó corresponde;
o Pai;
o Operador que foi aplicado para o
gerar;
o Profundidade;
o Custo do caminho g(n).
o O conjunto dos nós que ainda não foram
expandidos formam a fronteira.
o O objectivo da estratégia de pesquisa é
escolher um nó da fronteira.
o Se considerarmos os nós que fazem parte
da fronteira como estando numa lista, em
que os nós que aparecem primeiro são os
que o algoritmo de pesquisa escolhe
primeiro para expandir podemos rescrever
o algoritmo geral de pesquisa.
© Noel de Jesus Mendonça Lopes
45
© Noel de Jesus Mendonça Lopes
46
Avaliação das estratégias de
pesquisa
Algoritmo geral de pesquisa
o Completa
function PesquisaGeral(problema, FuncaoAdicaoFila)
returns solução ou falha
nos ← CriaFila(CriaNo(EstadoInicial(problema)))
do
if nos is empty then return falha
no ← RetiraPrimeiro(nos)
if ObjectivoSatisfeito(problema, Estado(no)) then return no
nos ← FuncaoAdicaoFila(nos, Expande(no, Operadores(problema)))
loop
o Garante que se houver uma solução ela é
encontrada ?
o Complexidade
n Tempo
o Quanto tempo é necessário para encontrar uma
solução ?
n Espaço
o Qual a memória necessária para efectuar a
pesquisa ?
o Solução óptima
o Quando existem várias soluções é encontrada a
solução de qualidade mais elevada ?
© Noel de Jesus Mendonça Lopes
47
© Noel de Jesus Mendonça Lopes
48
12
Algoritmos de pesquisa
Algoritmos de pesquisa cega
o Pesquisa uniforme (pesquisa cega)
o
o
o
o
o
o
n Não existe informação do nº de passos
ou do custo do caminho desde o estado
actual ao objectivo
o Pesquisa informada
n heurística
© Noel de Jesus Mendonça Lopes
49
Breadth-first search
© Noel de Jesus Mendonça Lopes
50
Breadth-first search
Function BreadthFirstSearch(problema)
returns solução ou falha
return PesquisaGeral(problema,
FuncaoAdicionaFimFila)
o Todos os nós com profundidade d são
expandidos antes dos nós com
profundidade d + 1.
o Se existir uma solução é garantido que o
algoritmo a encontra.
o A solução encontrada é sempre a solução
que tem o menor número de acções.
© Noel de Jesus Mendonça Lopes
Breadth-first search
Uniform cost search
Depth-first search
Depth-limited search
Iterative deepening search
Bidirectional search
51
© Noel de Jesus Mendonça Lopes
52
13
Breadth-first search
(Complexidade)
Breadth-first search
o Consideremos um espaço de estados
hipotético onde cada estado pode ser
expandido dando origem a b estados.
o Diz-se que o factor de ramificação
(branching factor) desses estados (e da
árvore) é b.
o Suponhamos que para atingirmos a solução
necessitamos de percorrer um caminho de
comprimento d (com d passos).
o Completo
o Óptimo se o custo do caminho for
uma função não decrescente da
profundidade do nó, isto é quando
todos os operadores têm o mesmo
custo.
o Complexidade (tempo e espaço)
n Problema
© Noel de Jesus Mendonça Lopes
53
Breadth-first search
(Complexidade)
54
Breadth-first search
(Complexidade)
o O número máximo de nós que temos
de percorrer antes de encontrar a
solução é :
Profundidade (d) Nós (b=10)
Tempo
Memória
0
1 1 milisegundo
100 Bytes
2
111 0,1 segundos
11 Kb
4
111111 11 segundos
1 Mb
6
10 6 18 minutos
111 Mb
8
10 8
31 horas
11 Gb
10
10 10
128 dias
1 Terabyte
12
10 12
35 anos
111 Terabytes
14
10 14
3500 anos
11111 Terabytes
1 + b + b2 + b3 + ... + bd
o Complexidade
O(bd )
© Noel de Jesus Mendonça Lopes
© Noel de Jesus Mendonça Lopes
55
© Noel de Jesus Mendonça Lopes
56
14
Uniform cost search
Uniform cost search
o Escolhe o nó com menor custo de
caminho para expandir.
o Idêntica à Breadth-first search nos
casos em que g(n) = Profundidade(n)
o Assume-se que :
I
1
I
∀n, g(sucessor(n)) ≥ g(n)
10
5 B
15
© Noel de Jesus Mendonça Lopes
0
A
C
5
57
Uniform cost search
F
5
© Noel de Jesus Mendonça Lopes
Uniform cost search
I
I
A
A
1
I
15
1
10
5 B
C
58
F
5
A
B
1
C
5
15
5
© Noel de Jesus Mendonça Lopes
I
5 B
15
59
10
C
F
5
A
B
F
5
C
5
15
11
© Noel de Jesus Mendonça Lopes
60
15
Uniform cost search
Depth-first search
o Algoritmo :
I
Function DepthFirstSearch(problema) returns solução ou falha
return PesquisaGeral(problema, FuncaoAdicionaInicioFila)
A
1
I
10
5 B
15
C
F
5
A
B
F
5
11
© Noel de Jesus Mendonça Lopes
F
10
C
15
61
o Necessita de pouca memória.
o Para um espaço com um factor de
ramificação de b e para uma profundidade
máxima de m o algoritmo necessita apenas
de bm nós.
o Complexidade : O(bm)
© Noel de Jesus Mendonça Lopes
62
Depth-first search
Depth-first search
o Para problemas que têm muitas soluções
este algoritmo pode encontrar uma solução
primeiro que o Breath-first search.
o Muitos problemas têm árvores de pesquisa
muito profundas ou mesmo infinitas, pelo
que este algoritmo pode não conseguir
recuperar de uma má escolha de um dos
ramos no inicio da árvore.
o Pode encontrar uma solução com um
custo de caminho muito maior que a
solução óptima.
o Não é óptimo nem completo.
o Fácil de implementar com uma função
recursiva.
© Noel de Jesus Mendonça Lopes
63
© Noel de Jesus Mendonça Lopes
64
16
Depth-limited search
Iterative deepening search
o Igual ao Depth-first search só que é
imposto um limite de profundidade.
o Não é óptimo
o Pode ou não ser completo, dependendo dos
limites impostos.
o Para um espaço com um factor de
ramificação de b e para um limite de
profundidade l o algoritmo necessita
apenas de bl nós.
o Complexidade : O(bl )
o Objectivo é determinar o diâmetro
do espaço de estados por tentativas.
o Combina os benefícios do Breadthfirst search com os do Depth-first
search.
o É óptimo e completo como o Breadthfirst search.
o Necessita de pouca memória como o
Depth-first search.
© Noel de Jesus Mendonça Lopes
65
© Noel de Jesus Mendonça Lopes
Iterative deepening search
Iterative deepening search
o Muitos estados são expandidos
múltiplas vezes. No entanto o tempo
adicional de pesquisa não é tão
significativo como pode parecer à
primeira vista.
o Tomemos como exemplo o caso do
depth-limited search em o que
número máximo de nós a percorrer é
de :
1 + b + b2 + ... + bd-2 + bd-1 + bd
o Para uma profundidade d = 5 e para um
factor de ramificação b = 10. O número
máximo de nós a percorrer é de :
© Noel de Jesus Mendonça Lopes
66
1 + 10 + 100 + 1000 +10000 + 100000 = 111111
o No iterative deepening search o número
máximo de nós a percorrer será de :
(d+1)1 + db + (d-1)b 2 + ... + 3b d-2 + 2b d-1 + 1b d
o Para o caso :
6 + 50 + 400 + 3000 + 20000 + 100000 = 123456
67
© Noel de Jesus Mendonça Lopes
68
17
Iterative deepening search
Bidirectional search
o Temos assim um aumento de cerca
de 11% que será ainda menor para
factores de ramificação maiores.
o Complexidade : O(2bd/2 ) = O(bd/2 )
Inicio
© Noel de Jesus Mendonça Lopes
69
Objectivo
© Noel de Jesus Mendonça Lopes
Bidirectional search
Bidirectional search
o O que significa procurar para trás?
o Procurar para trás significa gerar
sucessivamente predecessores a partir do
objectivo.
o Os predecessores de um nó n são todos os
nós que têm o nó n como sucessor.
o Quando todos os operadores são
reversíveis o conjunto dos predecessores e
sucessores é idêntico.
o Nalguns problemas calcular os
predecessores pode ser bastante difícil.
o E se existir não apenas um estado
correspondente ao objectivo, mas vários ?
o Se existir uma lista explicita destes
estados, podemos aplicar uma função
predecessora ao conjunto de estados, tal
como aplicamos os sucessores.
o Se dispusermos apenas uma descrição do
conjunto de estados correspondentes ao
objectivo (tal como no xadrez – cheque
mate) o problema torna-se mais
complicado.
© Noel de Jesus Mendonça Lopes
71
© Noel de Jesus Mendonça Lopes
70
72
18
Bidirectional search
Bidirectional search
o Deve existir uma forma eficiente de
verificar se cada um dos novos nós já
existe na árvore de pesquisa da outra
metade da pesquisa.
o Devemos decidir que tipo de algoritmo
vamos utilizar de cada lado da pesquisa.
o Complexidade : O(bd/2 ) assumindo que o
processo de teste de intercessão das duas
fronteiras pode ser levado a cabo num
tempo constante (isto é independente do
número de estados).
© Noel de Jesus Mendonça Lopes
73
74
Comparação das estratégias de
pesquisa
Bidirectional search
o Normalmente essa verificação é
possível através da utilização de uma
HASH table.
o Para determinar se as duas fronteiras
se têm nós em comum, é necessário
que os todos os nós de pelo menos
uma delas estejam em memória (tal
como no breath-first search).
o Complexidade do espaço : O(bd/2 )
© Noel de Jesus Mendonça Lopes
© Noel de Jesus Mendonça Lopes
75
Critério
Breadth
-First
UniformCost
Depthfirst
DepthLimited
Iterative
Deepening
Tempo
Espaço
Óptimo?
Completo?
bd
bd
Sim
Sim
bd
bd
Sim
Sim
bm
bm
Não
Não
bl
bl
Não
Sim, se l ≥ d
bd
bd
Sim
Sim
© Noel de Jesus Mendonça Lopes
Bidirectional
(quando
aplicável)
bd/2
bd/2
Sim
Sim
76
19
Evitar estados repetidos
Evitar estados repetidos
o Estados repetidos implicam perda de
tempo.
o Em muitos problemas é comum
aparecerem estados repetidos.
o O exemplo mais flagrante é quando
existem operações reversíveis.
o As árvores de pesquisa para estes
problemas são infinitas. No entanto se
retirarmos os estados repetidos podemos
reduzir o tamanho da árvore de pesquisa a
um tamanho finito.
o Mesmo quando a árvore de pesquisa
é finita, evitar os estados repetidos
pode levar a uma redução
exponencial do custo da pesquisa.
© Noel de Jesus Mendonça Lopes
77
© Noel de Jesus Mendonça Lopes
78
Formas de evitar estados
repetidos
Formas de evitar estados
repetidos
o Não retornar ao estado donde viemos. A
função de expansão deverá recusar-se a
gerar qualquer sucessor com o mesmo
estado que o estado correspondente ao nó
pai.
o Não criar caminhos com círculos. A função
de expansão deverá recusar-se a gerar
qualquer sucessor com o mesmo que
qualquer estado correspondente a um dos
nós antecessores.
o Não gerar qualquer estado que já tenha
sido gerado antes. Isto requer que todos os
estados estejam em memória.
© Noel de Jesus Mendonça Lopes
n Complexidade do espaço O(bd) ou O(s) em que
s é o número de estados do espaço dos estados.
n Normalmente é utilizada uma tabela HASH que
guarda os estados correspondentes a todos os
nós gerados. Desta forma verificar a existência
de espaços repetidos pode ser feito
eficientemente.
79
© Noel de Jesus Mendonça Lopes
80
20
Constraint satisfaction search
Constraint satisfaction search
o Um problema que para além dos requisitos
básicos em geral, satisfaz propriedades
estruturais adicionais designa-se por
constraint satisfaction problem (CSP).
o Num CSP os estados são definidos por um
conjunto de variáveis e o teste de
objectivo especifica um conjunto de
restrições a que esses valores devem
obedecer.
o O problema das 8 rainhas pode ser visto
como um CSP em que as variáveis são a
posição de cada uma das 8 rainhas; os
valores possíveis são os quadrados do
tabuleiro; e as restrições especificam que
não podem existir duas rainhas na mesma
linha, coluna ou diagonal. Uma solução
num CSP especifica os valores de todas as
variáveis, de tal modo que todas as
restrições são satisfeitas.
© Noel de Jesus Mendonça Lopes
81
© Noel de Jesus Mendonça Lopes
Constraint satisfaction search
Restrições
o Os CSP podem ser resolvidos por
algoritmos de pesquisa de propósito
geral, mas devido à sua estrutura
especial os algoritmos desenhados
para os CSP têm um desempenho
muito melhor.
o Unárias
82
n Referem-se ao valor de uma única
variável
o Binárias
n Relacionam pares de variáveis
o Ordem maior
n Envolvem três ou mais variáveis
© Noel de Jesus Mendonça Lopes
83
© Noel de Jesus Mendonça Lopes
84
21
Restrições
Variáveis e restrições
o Absolutas
o Cada variável Vi num CSP tem um
domínio Di, que é o conjunto de
valores que a variável pode tomar.
o O domínio pode ser discreto ou
continuo.
o Uma restrição unária especifica o
subconjunto de valores pertencentes
ao domínio Di que a uma dada
variável Vi pode ter.
n Quando violadas impedem a obtenção de
uma solução
o Preferência
n Indicam quais as soluções que são
preferíveis.
© Noel de Jesus Mendonça Lopes
85
© Noel de Jesus Mendonça Lopes
86
Aplicar um algoritmo de
pesquisa geral a um CSP
Aplicar um algoritmo de
pesquisa geral a um CSP
o Estado inicial – Um estado em que todas as
variáveis não têm nenhum valor.
o Operadores – Atribuem um valor a uma
variável a partir de um conjunto de valores
possíveis.
o Objectivo – Todas as variáveis têm valores
atribuídos que satisfazem todas as
restrições.
o A profundidade máxima da árvore de
pesquisa, bem como a profundidade onde se
encontram todas as soluções é n (número
de variáveis).
o Neste caso qual será o algoritmo adequado?
© Noel de Jesus Mendonça Lopes
87
© Noel de Jesus Mendonça Lopes
88
22
Backtracking search
Forward checking
o É despendido tempo quando pelo
menos uma das restrições já foi
violada.
o O que podemos fazer é inserir um
teste antes da geração de sucessores
que garanta que não são gerados
sucessores caso o estado actual viole
as restrições.
o Suponhamos que colocamos as primeiras 6
rainhas de tal forma que todas as colunas
da 8 linha estão a ser atacadas.
o O backtracking irá tentar todas as posições
para a 7ª rainha apesar de o problema já
não ser solúvel.
o O forward checking evita isto olhando para
a frente de forma a detectar se o problema
já é insolúvel.
© Noel de Jesus Mendonça Lopes
89
© Noel de Jesus Mendonça Lopes
Forward checking
Forward checking
o Cada vez que uma variável é instanciada,
são eliminados todos os valores dos
domínios que entrem em conflito com os
valores das variáveis instanciadas até à
data.
o Se algum dos domínios ficar com o
conjunto vazio de valores a pesquisa
retorna automaticamente.
o Na maioria dos casos é mais rápido que o
backtracking e é bastante fácil de
implementar.
© Noel de Jesus Mendonça Lopes
91
© Noel de Jesus Mendonça Lopes
90
92
23
Verificação da consistência dos
arcos
Verificação da consistência dos
arcos
o O forward checking é um caso especial da
verificação da consistência dos arcos.
o Um estado diz-se ter consistência de arco
quando todas as suas variáveis têm valores
do seu domínio que são consistentes com
todas as restrições que envolvem essa
variável.
o A consistência de arco pode ser obtida
apagando sucessivamente todos os valores
que são inconsistentes com uma dada
restrição.
© Noel de Jesus Mendonça Lopes
93
© Noel de Jesus Mendonça Lopes
94
Propagação de restrições
Consistência dos arcos
o À medida que se vão apagando
valores, outros valores podem tornarse inconsistentes porque dependiam
daqueles que foram apagados para
serem consistentes.
o Nalguns casos atingir a consistência
dos arcos é suficiente para resolver o
problema.
o A verificação da consistência dos
arcos é usada normalmente como um
passo de pré processamento, mas
pode também ser usada na pesquisa.
© Noel de Jesus Mendonça Lopes
95
© Noel de Jesus Mendonça Lopes
96
24