Utilização de CSP para montagem e resolução de problemas que envolvem

coloração de mapas

Tema 4André Martini DinizDanilo 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• ...

Restrições:

• Portugal != Spain• Spain != France• France != Italy

[2]

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ãoinvalida conexão x a y;

}

Montagem mapa• Algoritmo (1)

y

x

1

10

Montagem mapa• Algoritmo (1)

y

x

1

10

Montagem mapa• Algoritmo (2)

y

x

1

10

X

Montagem mapa• Algoritmo (3)

y

x

1

10

X

Y

Montagem mapa• Algoritmo (4)

y

x

1

10

2 segmentos não se cruzam:

• Primitivas Geométricas[3]• Produto vetorial

Montagem mapa• No final

y

x

1

10

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)

P1

P2

P3

Montagem mapa• Restrições– Entre triângulos• Uma aresta (2 pontos)

• A != B

P1

P2

A

B

Agenda

• Introdução• Problema• Implementação– Montagem mapa– Algoritmos

• Testes• Resultados

Algoritmos

• Backtracking Search– Utiliza busca em profundidade com retrocesso– Algoritmo recursivo

A

B

C

D

Cores:VermelhaVerdeAzul

Algoritmos

• Backtracking Search

A = V

A = VB = V

A = VB = VC = VErro!

A = VB = VC = V

A = VB = VC = VD = V

Algoritmos

• Backtracking Searchfunçã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çõesvariável = Seleciona uma variável sem valor

das variáveis do problema-CSPpara 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 resultadoremove {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

A

B

C

D

Cores:VermelhaVerdeAzul

Algoritmos

• Backtracking Search com MRV

A= V

A = VC = VErro!

A = VC = V

A = VC = VB = V

A = VC = VB = VD = 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

(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

A

B

C

D

Cores:VermelhaVerdeAzul

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-Conflictsfunçã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-CSPpara 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 nvezes

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+

MRVFC

FC+

MRVMC

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%20Geometricas.ppt. Geometria Computacional Primitivas Geométricas (2002)