Utilização de CSP para montagem e
resolução de problemas que
envolvem coloração de mapas
Tema 4
André Martini Diniz
Danilo Elias da Silva
Agenda
• Introdução
• Problema
• Implementação
– Montagem mapa
– Algoritmos
• Testes
• Resultados
Introdução
• Coloração de mapas
[2]
Introdução
• Problema CSP
– Variáveis
• Domínio
– Restrições
• Algoritmos
Introdução
• Modelagem
Variáveis (cores):
• Portugal
• Spain
• France
• Italy
• Switzerland
• Luxembourg
• ...
[2]
Restrições:
• Portugal != Spain
• Spain != France
• France != Italy
Agenda
• Introdução
• Problema
• Implementação
– Montagem mapa
– Algoritmos
• Testes
• Resultados
Problema
• Exercício 5.7
• Para coloração de mapas:
– Montar o mapa (algoritmo fornecido)
– Montar tabela (nPontos máximo)
Agenda
• Introdução
• Problema
• Implementação
– Montagem mapa
– Algoritmos
• Testes
• Resultados
Montagem mapa
• Algoritmo
(1) Gerar n pontos aleatórios no quadrado unitário;
enquanto(sem conexões possíveis)
{
(2) x = ponto aleatório;
(3) y = ponto mais próximo e conectável a x;
se (x não conectado a y E conexão não cruza com outras
conexões)
(4) conecta x a y;
senão
invalida conexão x a y;
}
Montagem mapa
• Algoritmo (1)
y
1
0
1
x
Montagem mapa
• Algoritmo (1)
y
1
0
1
x
Montagem mapa
• Algoritmo (2)
y
X
1
0
1
x
Montagem mapa
• Algoritmo (3)
y
X
1
0
Y
1
x
Montagem mapa
• Algoritmo (4)
y
2 segmentos não se
cruzam:
1
• Primitivas Geométricas[3]
• Produto vetorial
0
1
x
Montagem mapa
• No final
y
1
0
1
x
Montagem mapa
• Descoberta das variáveis
Montagem mapa
• Variáveis
– Varrer conexões entre pontos
– Achar padrão P1 -> P2 -> P3
– Se achar:
• Achou nova variável (triângulo)
P2
P1
P3
Montagem mapa
• Restrições
– Entre triângulos
• Uma aresta (2 pontos)
P1
A
B
• A != B
P2
Agenda
• Introdução
• Problema
• Implementação
– Montagem mapa
– Algoritmos
• Testes
• Resultados
Algoritmos
• Backtracking Search
– Utiliza busca em profundidade com retrocesso
– Algoritmo recursivo
B
C
A
D
Cores:
Vermelha
Verde
Azul
Algoritmos
• Backtracking Search
A=V
A=V
B=V
A=V
B=V
C=V
Erro!
A=V
B=V
C=V
A=V
B=V
C=V
D=V
Algoritmos
• Backtracking Search
função RECURSIVE-BACKTRACKING (atribuições, problema-CSP)
retorna a solução, ou uma falha
{
se (as atribuições estão completas) então retorna as atribuições
variável = Seleciona uma variável sem valor
das variáveis do problema-CSP
para cada valor presente no domínio de valores do problema-CSP faça:
{
se o valor é consistente para atribuir à variável
segundo as restrições do problema-CSP
{
adiciona {variável = valor} à atribuições
resultado = RECURSIVE-BACKTRACKING (atribuições, problema-CSP)
se resultado != falha então retorna resultado
remove {variável = valor} de atribuições
}
}
retorna falha
}
Algoritmos
• Backtracking Search com MRV (Minimum
Remainig Values)
– Utiliza heurística MRV para “ordenar” a seleção de
variáveis
– Variáveis com menor número de valores legais
possíveis são selecionadas primeiro
B
C
A
D
Cores:
Vermelha
Verde
Azul
Algoritmos
• Backtracking Search com MRV
A= V
A=V
C=V
Erro!
A=V
C=V
A=V
C=V
B=V
A=V
C=V
B=V
D=V
Algoritmos
• Forward Checking
– Utiliza as restrições entre as variáveis para
antecipar falhas
– A cada atribuição de valor a uma variável, elimina
esse valor das possibilidades das variáveis
“vizinhas”
– Se um domínio de possibilidades fica vazio
retrocede imediatamente
Algoritmos
• Forward Checking
B
C
A
D
Cores:
Vermelha
Verde
Azul
(1)A = V; B = {V, V, A}, C = {V, A}, D = {V, V, A}
(2)B = V; C = {V, A}, D = {V, V, A}
(3)C = V; D = {V, A}
(4)D = V
Algoritmos
• Forward Checking com MRV
– Combina a heurística MRV com o forward
checking
– Seleciona primeiramente a variável com menos
valores legais, tornando o foward checking mais
“inteligente”
Algoritmos
• Min-Conflicts
– Utiliza princípios de busca local
– Gera uma solução aleatória e tenta melhorá-la
– Para cada iteração muda os valores das variáveis
buscando minimizar os conflitos
– Pode ficar “preso” em um mínimo local
Algoritmos
• Min-Conflicts
função Min-Conflicts (num-iterações, problema-CSP)
retorna a solução, ou uma falha
{
solução-atual = uma atribuição completa e aleatória do problema-CSP
para um número de iterações < num-iterações faça:
{
se (solução-atual é uma solução completa)
retorna solução-atual
calcula conflitos de todos os estados vizinhos;
aplica mudança com menor número mínimo de conflitos;
}
retorna falha
}
Agenda
• Introdução
• Problema
• Implementação
– Montagem mapa
– Algoritmos
• Testes
• Resultados
Testes
• N máximo
Repetido n
vezes
Testes
• Desempenho
– Número iterações (mudanças de estado)
– Número de pontos:
• 10
• 20
• 50
– Cores
• 3 (Vermelho, Verde, Azul)
• 4 (Vermelho, Verde, Azul, Amarelo)
Agenda
• Introdução
• Problema
• Implementação
– Montagem mapa
– Algoritmos
• Testes
• Resultados
Resultados
NPontos
(seed)
NCores
BT
BT
+
MRV
FC
FC
+
MRV
MC
10
(0)
3
24
24
13
13
4
10
(0)
4
24
24
13
13
2
20
(3)
3
48
47
29
29
9
20
(0)
4
2182
65
40
33
8
50
(92)
3
3912
158
80
90
!!
50
(0)
4
168
161
89
89
!!
Bibliografia
1. S. Russel e P. Norvig. Artificial Intelligence: A
Modern Approach. Prentice Hall, Upper
Saddle River, USA. 2nd. Edition, (2003).
2. http://www.ctl.ua.edu/math103/mapcolor/
mapcolor.htm. Map Coloring Work.
3. C. Esperança e P. R. Cavalcante :
orion.lcg.ufrj.br/gc/download/Primitivas%20
Geometricas.ppt. Geometria Computacional
Primitivas Geométricas (2002)