UNIVERSIDADE REGIONAL DE BLUMENAU
CENTRO DE CIÊNCIAS EXATAS E NATURAIS
CURSO DE CIÊNCIAS DA COMPUTAÇÃO – BACHARELADO
IMPLEMENTAÇÃO DE UM ALGORITMO HEURÍSTICO
PARA PROBLEMAS DE RESTRIÇÕES
ALEXSANDRO SANTOS PIRES
BLUMENAU
2006
2006/2-01
ALEXSANDRO SANTOS PIRES
IMPLEMENTAÇÃO DE UM ALGORITMO HEURÍSTICO
PARA PROBLEMAS DE RESTRIÇÕES
Trabalho de Conclusão de Curso submetido à
Universidade Regional de Blumenau para a
obtenção dos créditos na disciplina Trabalho
de Conclusão de Curso II do curso de Ciências
da Computação — Bacharelado.
Prof. Jomi Fred Hübner, Doutor - Orientador
BLUMENAU
2006
2006/2-01
IMPLEMENTAÇÃO DE UM ALGORITMO HEURÍSTICO
PARA PROBLEMAS DE RESTRIÇÕES
Por
ALEXSANDRO SANTOS PIRES
Trabalho aprovado para obtenção dos créditos
na disciplina de Trabalho de Conclusão de
Curso II, pela banca examinadora formada
por:
Presidente:
______________________________________________________
Prof. Jomi Fred Hübner, Doutor – Orientador, FURB
Membro:
______________________________________________________
Prof. Paulo César Rodacki Gomes, Doutor – FURB
Membro:
______________________________________________________
Prof. Mauro Marcelo Mattos, Doutor – FURB
Blumenau, 15 de dezembro de 2006.
Dedico este trabalho a todos os familiares e
amigos, especialmente aqueles que me
ajudaram diretamente na realização deste, a
comunidade científica de computação e
inteligência artificial e ao meu orientador.
AGRADECIMENTOS
À Deus, pela oportunidade de fazer este trabalho.
À minha família, que mais do que nunca, esteve tão presente.
À minha namorada Iloara Cláudia Gutz por ser compreensiva com minha dedicação
intensa a este trabalho e por estar sempre me motivando para a conclusão do mesmo.
Aos meus amigos, pelos empurrões e cobranças.
Ao meu orientador, Jomi Fred Hübner, por ter acreditado na conclusão deste trabalho,
e me ajudado nas horas mais difíceis.
Ao bolsista de iniciação científica em inteligência artificial, Karlyson Schubert Vargas,
por ter ajudado na compreensão de itens relacionados ao dynDCSP e CCB.
A sr. Áureo Alves, representante da Clicheria Blumenau, por me dar a oportunidade de
me dedicar integralmente a realização deste trabalho por um mês.
Ao Russell e Norvig, por criarem uma obra didática magnífica sobre inteligência
artificial.
A melhor forma de prever o futuro é inventá-lo.
Alan Kay.
RESUMO
Este trabalho apresenta a implementação do algoritmo de busca-com-retrocesso para resolver
problemas de satisfação de restrições (PSR) ou em inglês, Constraint Satisfaction Problem
(CSP). Também há a integração com um projeto que permite a descrição CSPs através de uma
linguagem de alto nível, para que os mesmos sejam consistidos, modelados e resolvidos pelo
algoritmo implementado. O algoritmo conta com heurísticas de variável mais restritiva,
variável mais restringida e conflitos mínimos na obtenção da solução dos problemas. A
especificação foi feita utilizando o Enterprise Architect (EA) com a Unifield Modeling
Language (UML) e a implementação na linguagem Java com a Integrated Development
Environment (IDE) Eclipse.
Palavras-chave: Busca-com-retrocesso. Problema de satisfação de restrições. PSR. Conflitos
mínimos.
ABSTRACT
This work presents the implementation of the search algorithm with backtracking to solve
constraint satisfaction problem (CSP). Also it has the interation with a project that allows the
description of CSPs in a high level language so that the same either consisted, shaped and
solved for implemented algorithm. The algorithm has heuristics: more restrictive variable,
more retricted variable and minimun conflicts in the attainment of the solution of the problem.
The specification was made using the Enterprise Architect with the Unifield Modeling
Language (UML) and the implementation in the Java language with the Integrated
Development Environment (IDE) Eclipse.
Key-words: Backtracking. Constraint satisfaction problem. CSP. Minimun conflicts.
LISTA DE ILUSTRAÇÕES
Figura 1 – Mapa da Austrália ................................................................................................... 16
Quadro 1 – Definição do problema de coloração de mapas modelado em CSP ...................... 16
Figura 2 – Uma solução possível para o problema das n-rainhas com n=8 ............................. 17
Figura 3 – Parte de uma árvore de busca gerada pelo algoritmo busca-com-retrocesso.......... 18
Quadro 2 – Algoritmo de busca-com-retrocesso...................................................................... 18
Quadro 3 – Algoritmo de busca local com a heurística de conflitos mínimos......................... 20
Figura 4 – Parte 1 do exemplo de busca local com conflitos mínimos .................................... 21
Figura 5 – Parte 2 do exemplo de busca local com conflitos mínimos .................................... 21
Figura 6 – Parte 3 do exemplo de busca local com conflitos mínimos .................................... 22
Quadro 4 – Especificação do CSP para o problema da Figura 1.............................................. 23
Quadro 5 – Especificação da linguagem para construção de CSP/COP do CCB .................... 23
Quadro 6 – Especificação de domínio...................................................................................... 23
Quadro 7 – Exemplo de especificação do domínio .................................................................. 23
Quadro 8 – Especificação de variáveis..................................................................................... 23
Quadro 9 – Exemplo de especificação das variáveis................................................................ 24
Quadro 10 – Exemplo de especificação das restrições............................................................. 24
Figura 7 – Tela do editor do CCB ............................................................................................ 25
Figura 8 – Visão geral do CCB ................................................................................................ 25
Quadro 11 – Exemplo da especificação de um CSP com a biblioteca do dynDCSP ............... 26
Quadro 12 – Problema das n-rainhas especificado com a biblioteca do dynDCSP ................. 27
Figura 9 – Pacotes do dynDCSP............................................................................................... 28
Figura 10 – Classes do pacote CSP do dynDCSP .................................................................... 28
Figura 11 – Diagrama de casos de uso ..................................................................................... 31
Figura 12 – Diagrama de atividades ......................................................................................... 32
Figura 13 – Diagrama de classes .............................................................................................. 33
Quadro 13 – Método pesquisaComRetrocesso da classe resolveCSP ..................... 36
Quadro 14 – Método retrocessoRecursivo da classe resolveCSP.......................... 37
Quadro 15 – Método ehCompleta da classe resolveCSP ............................................... 38
Quadro 16 – Método getVarSemValor da classe resolveCSP...................................... 38
Quadro 17 – Saída do console da resolução de um CSP.......................................................... 39
Quadro 18 – Método getVariavelMaisRestritiva da classe resolveCSP ........... 39
Quadro 19 – Método ordenarVariavelMaisRestritiva da classe resolveCSP.. 40
Quadro 20 – Método ordenarVariavelMaisRestringida da classe resolveCSP41
Quadro 21 – Método getVariavelMaisRestringida da classe resolveCSP ......... 42
Quadro 22 – Método iniciaConflitosMinimos da classe ConflitosMinimos .... 42
Quadro 23 – Método getValorConflitosMinimos da classe ConflitosMinimos43
Quadro 24 – Método getNumeroConflitos da classe ConflitosMinimos.............. 43
Quadro 25 – Método getVariaveisConflitantes da classe ConflitosMinimos44
Quadro 26 – Método getViolacoes da classe ConflitosMinimos ............................ 44
Quadro 27 – Método atribuicaoAleatoria da classe ConflitosMinimos ........... 45
Quadro 28 – Método selecionaVarAleatoria da classe ConflitosMinimos....... 45
Quadro 29 – Método getDominio da classe ConflitosMinimos ................................. 45
Quadro 30 – Inserção de um comboBox na classe BuilderGUI ........................................ 46
Quadro 31 – Inserção do método pesquisaComRetrocesso na classe BuilderGUI.. 46
Quadro 32 – Arquivo de lote executa.bat......................................................................... 46
Quadro 33 – Classe GeraInterfaceCCB ........................................................................... 47
Figura 14 – Interface do CCB................................................................................................... 47
Figura 15 – Tela abrir arquivo.................................................................................................. 48
Figura 16 – Tela do CBB com um CSP especificado .............................................................. 48
Figura 17 – Seleção do método de resolução ........................................................................... 49
Figura 18 – Tela do CBB com um CSP especificado e resolvido com heurística ................... 50
Figura 19 – VC das execuções: problema da Figura 1 ............................................................. 51
Figura 20 – Tempo médio das execuções: problema da Figura 1 ............................................ 52
Figura 21 – Problema de coloração de mapas com domínios diferentes. ................................ 52
Quadro 34 – Código fonte do problema de coloração de mapas com domínios diferentes ..... 53
Figura 22 – VC das execuções: coloração de mapas com domínios diferentes. ...................... 53
Figura 23 – Tempo médio das execuções: coloração de mapas com domínios diferentes ...... 54
Figura 24 – VC nas execuções: n-rainhas com n=4 ................................................................. 54
Figura 25 – Tempo médio das execuções: n-rainhas com n=4 ................................................ 55
LISTA DE SIGLAS
PSR – Problema de Satisfação de Restrição
VAR – Variável
AO – Austrália Ocidental
TN – Território Norte
Q – Queensland
AM – Austrália Meridional
NGS – Nova Gales do Sul
V – Victoria
T – Tazmânia
SUMÁRIO
1 INTRODUÇÃO.................................................................................................................. 12
1.1 OBJETIVOS DO TRABALHO ........................................................................................ 13
1.2 ESTRUTURA DO TRABALHO ...................................................................................... 14
2 FUNDAMENTAÇÃO TEÓRICA .................................................................................... 15
2.1 CONSTRAINT SATISFACTION PROBLEM..................................................................... 15
2.2 BUSCA-COM-RETROCESSO ........................................................................................ 17
2.3 HEURÍSTICAS ................................................................................................................. 19
2.4 CSP && COP BUILDER .................................................................................................. 22
2.5 DYNDCSP ......................................................................................................................... 25
2.6 TRABALHOS CORRELATOS........................................................................................ 29
3 DESENVOLVIMENTO DO TRABALHO ..................................................................... 30
3.1 REQUISITOS PRINCIPAIS DO PROBLEMA A SER TRABALHADO....................... 30
3.2 ESPECIFICAÇÃO ............................................................................................................ 30
3.2.1 Diagrama de casos de uso ............................................................................................... 30
3.2.2 Diagrama de atividades ................................................................................................... 31
3.2.3 Diagrama de classes ........................................................................................................ 32
3.3 IMPLEMENTAÇÃO ........................................................................................................ 34
3.3.1 Técnicas e ferramentas utilizadas.................................................................................... 35
3.3.1.1 Implementação do algoritmo busca-com-retrocesso .................................................... 35
3.3.1.2 Implementação da heurística variável mais restritiva................................................... 39
3.3.1.3 Implementação da heurística variável mais restringida................................................ 41
3.3.1.4 Implementação da heurística de conflitos mínimos em busca local............................. 42
3.3.1.5 Integração com o CCB.................................................................................................. 45
3.3.2 Operacionalidade da implementação .............................................................................. 46
3.4 RESULTADOS E DISCUSSÃO ...................................................................................... 50
4 CONCLUSÕES.................................................................................................................. 56
4.1 EXTENSÕES .................................................................................................................... 57
REFERÊNCIAS BIBLIOGRÁFICAS ................................................................................. 58
12
1 INTRODUÇÃO
Assim como a informática de maneira geral desperta interesse em quem a descobre,
muitos estudantes de ciência da computação entusiasmam-se com a disciplina de Inteligência
Artificial. Neste contexto, há um tópico interessante chamado problema de satisfação de
restrições (PSR) ou, em inglês, Constraint Satisfaction Problem (CSP).
O CSP pode ser definido por um conjunto de variáveis e por um conjunto de restrições,
onde cada variável tem um domínio não-vazio de valores possíveis, conforme Russell e
Norvig (2004, p. 135). Cada restrição envolve algum subconjunto das variáveis e especifica
combinações de valores contidos no seu domínio e que são permitidos para esse subconjunto.
Um estado do problema é definido por uma atribuição de valores a alguma ou todas as
variáveis, sendo que uma atribuição que não viola nenhuma restrição é uma atribuição válida.
Uma solução para o CSP é uma atribuição para todas as variáveis que satisfaz todas as
restrições.
O problema de coloração de mapas é um exemplo clássico de um problema que pode
ser traduzido para os moldes do CSP, onde se deseja colorir, com um número definido de
cores, um mapa no qual há uma área definida e finita de regiões, sendo que as vizinhas não
podem ter a mesma cor. Isso se torna algo complexo de ser resolvido por um ser humano
quando há muitas regiões, um alto grau de vizinhança e poucas cores.
Para a utilização prática das técnicas de CSP, é necessário utilizar algum sistema de
buscas que verifique todas as variáveis envolvidas. Dentre eles, pode-se citar o de busca-comretrocesso, que é um algoritmo de busca recursiva e em profundidade que gera nodos em
níveis de uma árvore, tentando buscar uma solução para o CSP. Caso não ache a solução no
nível atual da árvore, ele retorna um nível e continua a busca, sucessivamente. Há também
algoritmos de busca local que criam um estado inicial para a atribuição com valores aleatórios
atribuídos as variáveis, verificando se já se encontrou a solução, senão altera uma variável
com um outro valor de cada vez.
Para minimizar os custos de busca, há a necessidade de aplicar heurísticas1 de busca e
de uso geral, como exemplo, a de conflitos mínimos. Ela dá preferência para o valor que
resulta no número de conflitos com outras variáveis já atribuídas. Assim como a heurística de
conflitos mínimos, há outras heurísticas existentes como a de variável mais restritiva e
1
Para Rich e Knight (1993, p. 49), a palavra heurística vem do grego heuriskein, que significa “descobrir”.
13
variável mais restringida.
Para a especificação de CSPs, é utilizado um projeto que permite especificar CSPs
através de objetos em Java e em uma linguagem própria de alto nível, que é interpretada
através de um parser e gera uma instância de objetos em Java que representam o CSP
informado. Este projeto, denominado dynDCSP, é descrito em Santos (2005) e foi
desenvolvido em Java pelo Grupo de Inteligência Artificial (GIA) da Universidade Regional
de Blumenau (FURB). Neste projeto, está incluso a ferramenta CSP && COP Builder (CCB)
que interpreta uma especificação de CSP, mas não possui nenhum algoritmo para a resolução
de CSPs. Para resolver este problema, implementou-se o algoritmo busca-com-retrocesso,
utilizou-se a representação de CSP disponibilizado pelo dynDCSP e integrou-o ao CCB.
Atualmente, há uma integração entre um algoritmo de resolução de CSPs e o CCB,
presente no projeto dynDCSP, também desenvolvido pelo GIA da FURB. Porém, o algoritmo
implementado foi concebido para resolver os CSPs de forma distribuída, ou seja, em diversos
computadores. Neste trabalho, o algoritmo busca-com-retrocesso é implementado de forma
centralizada2 uma vez que já há um algoritmo de resolução distribuída no projeto dynDCSP.
A implementação também utiliza heurísticas na busca pela solução do CSP informado.
1.1 OBJETIVOS DO TRABALHO
O objetivo deste trabalho é implementar o algoritmo de busca-com-retroceso para
solucionar CSPs, disponibilizando heurísticas para a obtenção da solução, e integrando-o com
a ferramenta CCB, sendo capaz de informar um CSP por meio de uma linguagem para o
retorno de uma solução obtida através da busca efetuada pelo algoritmo. O trabalho a ser
implementado também deve poder ser utilizado como uma ferramenta didática, com
documentação da programação a ser feita e também podendo ser equiparada com os
algoritmos que a literatura propõe.
2
Centralizada pelo fato de toda a execução e processamento ser realizado localmente em um só computador.
14
1.2 ESTRUTURA DO TRABALHO
O conteúdo deste trabalho está dividido em três capítulos. O capítulo 2 apresenta a
fundamentação teórica contendo um estudo detalhado sobre constraint satisfaction problem
(seção 2.1), sobre o algoritmo de busca-com-retrocesso (seção 2.2), sobre heurísticas (seção
2.3), sobre o CSP && COP Builder (seção 2.4), sobre o dynDCSP (seção 2.5) e os trabalhos
correlatos (seção 2.6).
O capítulo 3 abrange o desenvolvimento do trabalho, contendo os requisitos principais
do problema a ser trabalhado (seção 3.1), especificação do sistema (seção 3.2), e a
implementação (3.3) é subdividido em técnicas e ferramentas utilizadas (seção 3.3.1) e
operacionalidade da implementação, que apresenta o funcionamento do sistema com estudo
de caso. É apresentado também os resultados e discussão (seção 3.4) do trabalho.
As conclusões do trabalho são evidenciadas no capítulo 4 que tem uma subseção que
demonstra as extensões (seção 4.1) possíveis para este trabalho.
15
2 FUNDAMENTAÇÃO TEÓRICA
A fundamentação teórica contém 5 seções que servirão de base para o entendimento
deste trabalho. A seção 2.1 trata dos aspectos, conceitos fundamentais e exemplos de CSP, a
seção 2.2 demonstra o algoritmo busca-com-retrocesso, a seção 2.3 apresenta a descrição das
heurísticas, a seção 2.4 demonstra a ferramenta CSP && COP Builder que é utilizado em
conjunto com a implementação do algoritmo de resolução de CSPs, a seção 2.5 mostra o
projeto dynDCSP, que oferece a representação de CSPs através de objetos em Java. Por fim, a
seção 2.6 explana sobre os trabalhos correlatos.
2.1 CONSTRAINT SATISFACTION PROBLEM
Para a modelagem de um problema CSP são necessários alguns conceitos básicos que
garantirão uma abordagem adequada para o problema. Formalmente, de acordo com Russell e
Norvig (2004, p. 135), pode-se definir um CSP como sendo um conjunto de variáveis, V1, V2,
...,Vn, e um conjunto de restrições, R1, R2, ..., Rm. Cada variável Vi tem um domínio Di, sendo
que o mesmo não pode ser vazio, e cada restrição Rj envolve um subconjunto de variáveis Vi
que especificam combinações para um valor aceitável para esse subconjunto. Um estado do
problema é tido como uma atribuição de valores a uma ou todas as variáveis ({Xi = vi, Xj = vj,
...}) e será uma solução para o CSP somente se um conjunto de atribuições for consistente
com todas as restrições.
Um exemplo prático de problema de satisfação de restrições é o de coloração de
mapas, como mencionado anteriormente. Na Figura 1 (a) é demonstrado o mapa dos
principais estados e territórios da Austrália e ao lado, na Figura 1 (b), um grafo, representando
como o problema pode ser estruturado, com os nós representando os estados e as arestas a
relação direta de vizinhança.
16
Fonte: Russell e Norvig (2004, p. 135).
Figura 1 – Mapa da Austrália
Modelando o problema como um CSP, as variáveis são os estados do mapa, as
restrições do problema são a não repetição da cor de um estado em outro estado vizinho e o
domínio de cada variável, as cores que podem colorir cada estado. A definição e uma solução
possível para este problema é apresentada no Quadro 1.
Variáveis = { AO, TN, Q, NGS, V, AM, T }
Restrições = { (AO ≠ TN),
(AO ≠ AM),
(TN ≠ AO),
(TN ≠ AM),
(TN ≠ Q)
...,
(NGS ≠ V) }
Domínio para as variáveis = { vermelho, verde, azul }
Solução possível = { (AO = vermelho),
(TN = verde),
(Q = vermelho),
(NGS = verde),
(V = vermelho),
(AM = azul),
(T = vermelho) }
Quadro 1 – Definição do problema de coloração de mapas modelado em CSP
Nas literaturas que contemplam CSP, geralmente é encontrado o problema das nrainhas. De acordo com Russell e Norvig (204, p. 67), é um problema interessante para testes
de algoritmos de busca e consiste em posicionar um número informado de rainhas em um
tabuleiro de xadrez de forma que não haja possibilidade de ataque entre nenhuma delas.
Também se considera a regra do xadrez em que a rainha se movimenta quantos passos sejam
necessários sendo que sua movimentação é feita na horizontal, vertical ou na diagonal.
Na especificação do problema das n-rainhas, geralmente é definido que o número de
rainhas seja igual ao número de linhas e colunas do tabuleiro, portanto, para o problema
17
proposto cada rainha é disposta em uma linha do tabuleiro e a numeração associada é
provinda do seu domínio e é relacionada com a coluna em que ela está, por exemplo, “R1 =
2” significa que a rainha número um está posicionada na coluna 2 da sua linha número um.
Na Figura 2, é ilustrado uma solução possível para o problema das n-rainhas, com n =
8 num tabuleiro de xadrez de tamanho 8x8. Nota-se que nenhuma delas está em posição de
ataque, ou seja, na mesma linha, coluna ou diagonal.
Fonte: Tsang (1993, p. 2).
Figura 2 – Uma solução possível para o problema das n-rainhas com n=8
2.2 BUSCA-COM-RETROCESSO
De acordo com Russell e Norvig (2004, p. 138), busca-com-retrocesso é um tipo de
busca recursiva e em profundidade que atribui valores a um nodo da árvore de busca, se
aprofundando pela esquerda, e toda vez que encontra uma inconsistência na atribuição de
algum valor, decorrente das restrições, retorna (efetua um retrocesso) e tenta pelo ramo mais
próximo à direita, e mesmo se não houver mais, retorna um nível da árvore e continua a busca
até o encontro da solução. Conforme Tsang (1993, p. 37), o algoritmo fará um retrocesso para
18
à última decisão quando o mesmo não conseguir continuar.
A Figura 3 traz o exemplo de parte da árvore de busca gerada pelo algoritmo buscacom-retrocesso aplicado ao exemplo de coloração de mapas, demonstrado na Figura 1. Ele
inicia gerando um valor para cada nodo do nível atual e se aprofunda pelo nodo da esquerda,
gerando novos sucessores e assim por diante. Caso um sucessor não satisfaça as condições das
restrições, ele retorna e gera o próximo sucessor da direita, caso contrário, ele retorna mais
um nível e faz as mesmas verificações sucessivamente.
Fonte: Campos (2003).
Figura 3 – Parte de uma árvore de busca gerada pelo algoritmo busca-com-retrocesso
No Quadro 2, é apresentado o algoritmo de busca-com-retrocesso proposto por Russell
e Norvig (2004).
função PESQUISA-COM-RETROCESSO(psr) retorna uma solução ou falha
retornar RETROCESSO-RECURSIVO({}, psr)
função RETROCESSO-RECURSIVO(atribuição, psr) retorna uma solução ou falha
se atribuição é completa então retornar atribuição
var <- SELECIONAR-VARIAVEL-NÃO-ATRIBUÍDA(VARIÁVEIS[psr],atribuição,psr)
para cada valor em VALORES-DE-ORDEM-NO-DOMÍNIO(var, atribuição, psr) faça
se valor é consistente com atribuição de acordo com RESTRIÇõES[psr] então
adicionar {var = valor} a atribuição
resultado <- RETROCESSO-RECURSIVO(atribuição,psr)
se resultado ≠ falha então retornar resultado
remover {var = valor} de atribuição
retornar falha
Fonte: Russell e Norvig (2004, p. 139).
Quadro 2 – Algoritmo de busca-com-retrocesso
19
A expressão busca-com-retrocesso é utilizada para indicar uma busca em
profundidade que escolhe valores para uma variável de cada vez e que efetua
o retrocesso quando uma variável não tem valores válidos restantes a serem
atribuídos. [...] Além disso, ele estende a atribuição corrente para gerar um
sucessor, em vez de copiá-lo. (RUSSELL; NORVIG, 2004, p. 138).
O algoritmo consiste basicamente em criar uma árvore com os nodos contendo as
atribuições dos valores do domínio às variáveis feitas até o momento e se for consistente, ele
continua a buscar por novas atribuições para chegar a uma atribuição completa, ou seja, uma
solução, senão, ele apaga esse nodo e retorna tentando novamente com um valor diferente, e
assim sucessivamente. Caso não consiga mais retornar e não tenha mais variáveis nem valores
do domínio para serem atribuídos, o algoritmo retorna como falha, o que denomina a não
existência de uma solução para o CSP informado.
2.3 HEURÍSTICAS
Heurísticas aplicadas em algoritmos de busca procuram basicamente reduzir o número
de passos até que se chegue à solução, pois para muitos problemas, de acordo com Russell e
Norvig (2004, p. 109-110), o que importa é a configuração final do problema, e não a ordem
em que ele foi resolvido. Ainda, segundo Rich e Knight (1993, p. 76), heurísticas são também
estratégias de busca que podem ser escritas independentemente de qualquer tarefa ou domínio
de problema em particular.
Nos algoritmos de resolução de CSP cabe a agregação da heurística de conflitos
mínimos. De acordo com Filho et al. (1998), ela seleciona o valor que resulta no número
mínimo de conflitos com outras variáveis, portanto, quando for atribuir esse valor, sabe-se
que este será mais aceito para ser atribuído a outras variáveis. Assim como esta, e ainda de
acordo com Filho et al. (1998), outras heurísticas também podem ser aplicadas ao algoritmo
de resolução de CSP como a de variável mais restritiva, que prefere a variável envolvida no
maior número de restrições e variável mais restringida, onde é preferida a variável com menos
valores em seu domínio.
Conforme Russell e Norvig (2004, p. 140), a heurística de variável mais restritiva
consiste em selecionar a variável envolvida no maior número de restrições. Para isso, deve-se
inicialmente obter a lista de variáveis do CSP e verificar uma a uma e utilizar por primeiro a
que tem a maior a quantidade de restrições em que ela é afetada, obtendo assim, logicamente,
20
uma maior possibilidade de atribuições futuras, diminuindo o número de conflitos posteriores.
Para a variável mais restringida, que é a heurística da variável que pode assumir o menor
número de valores, também se deve obter a lista de variáveis do CSP e verificar uma a uma a
quantidade de valores do domínio que ela pode assumir usando por primeiro, a variável que
tiver a menor quantidade, o que logicamente deixará as atribuições posteriores com uma
maior liberdade de atribuições com relação à quantidade de valores do domínio.
Segundo Russell e Norvig (2004, p.146), conflitos mínimos é uma heurística que
prefere pelo valor do domínio da variável que tenha o menor número de conflitos com outras
variáveis. Ela pode ser aplicada em um algoritmo de busca local. Ainda segundo Russell e
Norvig (2004, p. 146), algoritmos de busca local utilizam uma formulação de estados
completos, ou seja, o estado inicial atribui um valor a cada variável e a função sucessor altera
um valor de uma variável de cada vez.
Por exemplo, no problema das 8 rainhas, o estado inicial poderia ser uma
configuração aleatória de 8 rainhas em 8 colunas, e a função sucessor
escolheria uma rainha e consideraria a possibilidade de movê-la para outro
lugar em sua coluna. [...] Na escolha de um novo valor para uma variável, a
heurística mais obvia é selecionar o valor que resulta no número mínimo de
conflitos com outras variáveis – a heurística de conflitos mínimos.
(RUSSELL; NORVIG, 2004, p. 146).
No Quadro 3 é demonstrado o algoritmo de busca local com a heurística de conflitos
mínimos proposto por Russell e Norvig (2004).
função CONFLITOS-MÍNIMOS(psr, max_etapas) retorna uma solução ou falha
entradas: psr, um problema de satisfação de restrições
max_etapas, o número de etapas permitidas antes de desistir
corrente <- uma atribuição inicial completa para psr
para i=1 até max_etapas faça
se corrente é uma solução para psr então retornar corrente
var<- uma variável em conflito escolhida ao acaso a partir de VARIÁVEIS[psr]
valor<- um valor v para var que minimiza CONFLITOS(var,v,corrente,psr)
definir var = valor em corrente
retornar falha
Fonte: Russell e Norvig (2004, p. 146).
Quadro 3 – Algoritmo de busca local com a heurística de conflitos mínimos
Como exemplo, pode-se citar o problema das 8-rainhas. O algoritmo de busca local
iniciou com uma configuração aleatória das rainhas no tabuleiro conforme a Figura 4.
Verificou-se as rainhas que estavam em conflito, as rainhas 4 e a 8, selecionando uma
aleatoriamente – neste passo a 8. Logo após conta-se os conflitos gerados para cada posição
em que pode ser movida e é escolhido aleatoriamente entre os dois conflitos mínimos gerados.
Por fim deste passo, é movido a rainha para esta nova posição.
21
Fonte: adaptado de Russell e Norvig (2004, p. 147).
Figura 4 – Parte 1 do exemplo de busca local com conflitos mínimos
Com a nova configuração do tabuleiro, é verificado a consistência e detectado que
ainda há inconsistência com as restrições, sendo elas com as rainhas 6 e 8, conforme a Figura
5. É escolhida aleatoriamente – neste passo a 6. Conta-se os conflitos gerados para cada
posição em que pode ser movida e é escolhido o menor valor de conflito mínimo, neste caso o
valor que gerou 0 conflitos, ou seja, a posição na coluna A. É movido a rainha para esta nova
posição.
Fonte: adaptado de Russell e Norvig (2004, p. 147).
Figura 5 – Parte 2 do exemplo de busca local com conflitos mínimos
22
É novamente verificado a consistência e confirmado uma atribuição completa,
conforme a Figura 6. Obteve-se a solução com apenas 2 passos realizados pela busca local
com a heurística de conflitos mínimos.
Fonte: adaptado de Russell e Norvig (2004, p. 147).
Figura 6 – Parte 3 do exemplo de busca local com conflitos mínimos
2.4 CSP && COP BUILDER
O CCB foi desenvolvido para ser usado em conjunto com o dynDCSP, que também foi
implementado pelo GIA, e possui algoritmos de resolução de CSPs de forma distribuída, em
inglês, Distributed Constraint Satisfaction Problem (DCSP) e ainda uma biblioteca capaz de
representar CSPs através de classes em Java. Para que um DCSP seja resolvido na plataforma
dynDCSP, deve-se informar um código fonte que descreve o CSP/ Constraint Optimization
Problem (COP), para que o parser do CCB gere como saída instâncias de objetos que
representam o CSP/COP e disponibilize-as novamente para a plataforma do dynDCSP para
que o mesmo a resolva em um dos seus algoritmos distribuídos.
Com o CSP && COP Builder é possível especificar um CSP/COP a partir de uma
linguagem de alto nível, não sendo necessário manipular códigos fontes de especificação CSP
para a montagem dos domínios, variáveis e restrições.
No Quadro 4, é demonstrado como pode ficar o exemplo da Figura 1, definido na
23
linguagem de alto nível utilizada pelo parser da ferramenta CCB.
Csp
Id: coloração de mapas;
Version: 1.0;
Description: exemplo de definição CSP na linguagem do CCB;
Domains
// as cores como domínio. 1 = vermelho, 2 = verde e 3 = azul
cores : {1,2,3}
Variables
// Os estados como variáveis
ao, tn, q, ngs, v, am, t: cores;
Constraints
//as restrições de vizinhança, note que “t” não tem vizinhança alguma, logo
// não terá restrições.
ao != tn;
ao != am;
tn != am;
tn != q;
am != q;
am != ngs;
am != v;
q != ngs;
ngs != v;
Quadro 4 – Especificação do CSP para o problema da Figura 1
Para a representação de um CSP/COP, a linguagem definida para o CCB segue
basicamente a sintaxe demonstrada no Quadro 5.
Csp | Cop
Id: string; // identificador do problema
Version: float; // versão do problema
Description: string; // descrição do problema
Domains
// definição dos domínios
Variables
// definições das variáveis do problema
Constraints
// restrições do problema (identificador opcional)
Quadro 5 – Especificação da linguagem para construção de CSP/COP do CCB
Em Domains, deve-se definir os domínios como no Quadro 6.
dominio_id : {elemento_dominio_1, elemento_dominio_2, ..., elemento_dominio_n};
Quadro 6 – Especificação de domínio
Os elementos do domínio devem ser declarados como numerais inteiros, conforme
demonstrado no Quadro 7.
// A representação: cores = {verde, vermelho, amarelo} deverá ser especificada da
// seguinte forma:
cores : {1, 2, 3};
Quadro 7 – Exemplo de especificação do domínio
Já as variáveis são declaradas conforme descrito no Quadro 8.
variavel_id : dominio_id;
Quadro 8 – Especificação de variáveis
Após o identificador de cada variável, deve-se colocar o domínio pertencente a ela.
Pode-se ainda identificar várias variáveis pertencentes a um só domínio, separando as com
24
vírgula na identificação das mesmas. No Quadro 9, tem-se um exemplo das definições das
variáveis.
// Uma variável com o domínio “cores”
x1 : cores;
// Quatro variáveis com o domínio “cores”
x1, x2, x3, x4 : cores;
Quadro 9 – Exemplo de especificação das variáveis
Por fim, as restrições são especificadas por expressões numéricas e lógicas. Sua
sintaxe é similar a do Java e tem uma série de funções embutidas como exibida no Quadro 10.
// Operadores/expressões lógicas e relacionais
&& (e)
-- (ou)
‘ (ou exclusivo)
!= (diferente)
== (igualdade)
allDifferent ([lista de variáveis, separadas por vírgula]) (todas diferentes)
// Operadores numéricos
+ (adição)
- (subtração)
* (multiplicação)
/ (divisão)
Sin(valor) (seno(em graus))
Cos(valor) (cosseno(em graus))
// Exemplo de Expressões:
x1 != x2; (x1 deve ser diferente de x2)
allDiff([x1, x2, x3, x4]); (x1, x2, x3 e x4 devem ser diferentes uma das outras)
(x1 + 1) == x4 (a expressão: variável x1 mais 1, deve ser igual a variável x4)
Quadro 10 – Exemplo de especificação das restrições
A interface do CCB é demonstrada na Figura 7. O código fonte contendo a
especificação do CSP na linguagem de alto nível do CCB deve ser digitada ou aberta em um
arquivo no CCB para que o mesmo possa interpretá-la, gerando uma instância do CSP/COP
para que seja usado no framework dynDCSP ou em outra aplicação, no caso, este trabalho,
como na Figura 8.
25
Fonte: Santos (2006, p. 2).
Figura 7 – Tela do editor do CCB
Fonte: Santos (2006, p.1).
Figura 8 – Visão geral do CCB
2.5 DYNDCSP
O dynDCSP tem uma biblioteca em Java chamada CSP que provê a representação de
CSPs a partir de classes, onde podem ser gerados objetos de atribuição, variáveis, restrições,
domínios, o próprio objeto CSP entre outros. No Quadro 11, tem-se um exemplo da
26
representação de um problema CSP em código Java com a biblioteca CSP do dynDCSP.
package helloCSP;
import
import
import
import
import
import
import
csp.CSP;
csp.Constraint;
csp.Value;
csp.Variable;
csp.domains.IntegerDomain;
csp.exp.VariableExpression;
csp.exp.logic.DifferentExpression;
/**
* The Makoto's x1/x2/x3 example
*
* @author jomi
*/
public class HelloCSP extends CSP {
/** Creates a new instance of HelloCSP */
public HelloCSP() {
super("HelloCSP");
// domains
IntegerDomain e1 = new IntegerDomain("oneVl");
e1.addValue(new Value(new Integer(2)));
IntegerDomain e2 = new IntegerDomain("twoVl");
e2.addValue(new Value(new Integer(1)));
e2.addValue(new Value(new Integer(2)));
// variables
Variable x1 = new Variable("x1");
x1.setDomain(e2);
addVariable(x1);
Variable x2 = new Variable("x2");
x2.setDomain(e1);
addVariable(x2);
Variable x3 = new Variable("x3");
x3.setDomain(e2);
addVariable(x3);
// constraints
Constraint c1 = new Constraint();
c1.setExpression(new DifferentExpression(new VariableExpression(x1), new
VariableExpression(x3)));
addConstraint(c1);
Constraint c2 = new Constraint(newDifferentExpression(
newVariableExpression(x2), new VariableExpression(x3)));
addConstraint(c2);
}
}
Fonte: Santos (2006).
Quadro 11 – Exemplo da especificação de um CSP com a biblioteca do dynDCSP
De posse dessa biblioteca, é possível definir CSPs a partir de um código em Java. A
classe
Domain
possui métodos onde é possível criar diversos domínios, cada um deles
rotulados por uma string, para que sejam atribuídos a variáveis. É possível adicionar valores
ou mesmo intervalos na classe Domain. No Quadro 11, tem-se o domínio oneV1 com o valor 2,
objeto da classe Value. As variáveis são da classe Variable que também são rotuladas por uma
27
string
e é possível através do método
setDomain,
As restrições são representadas pela classe
indicar a qual domínio a variável pertence.
Constraint
que pelo método
setExpression
é
possível definir as restrições das variáveis, como a de diferença, com a classe
DifferentExpression.
Quanto ao problema das n-rainhas, no qual sua instanciação deve ser feita informando
o número de rainhas ao construtor da classe como parâmetro. O código fica conforme o
Quadro 12.
//Suprimido imports, saídas de console e alguns comentários para uma melhor
visualização do código em todos os quadros seguintes
public class NQueensCSP extends CSP {
public NQueensCSP(int n) {
super("NQueensCSP");
// creating domains, they are equal for all n-queens
Domain queensDomain = new IntegerDomain("queensDomain", 1, n);
// creating PriorityVariable's to represent the queens
for (int i = 0; i < n; i++) {
Variable av = new Variable("q" + (i + 1));
av.setDomain(queensDomain);
addVariable(av);
}
// creating the constrains for all queens
ArrayList varExpressions = new ArrayList();
Iterator itv = getVariables().iterator();
while (itv.hasNext()){
varExpressions.add(
new VariableExpression( (Variable)itv.next() ));
}
addConstraint( new Constraint(new AllDifferentExpression(varExpressions)));
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
Variable xi = (Variable) getVariable("q" + (i + 1));
Variable xj = (Variable) getVariable("q" + (j + 1));
VariableExpression varXi = new VariableExpression(xi);
VariableExpression varXj = new VariableExpression(xj);
AbsExpression ae =
new AbsExpression(new SubtractionExpression(varXi,varXj));
ConstantExpression ce =
new ConstantExpression(new Value( new Integer(Math.abs(i - j))));
DifferentExpression de = new DifferentExpression(ce, ae);
addConstraint(new Constraint(de));
}
}
}
}
Fonte: Santos (2006).
Quadro 12 – Problema das n-rainhas especificado com a biblioteca do dynDCSP
O framework dynDCSP possui dois pacotes, um capaz de representar um CSP e o
outro permite a resolução de DCSPs conforme diagrama de pacotes apresentado na Figura 9.
28
Fonte: Santos (2005, p. 38).
Figura 9 – Pacotes do dynDCSP
Na figura 10, tem-se a visão geral do pacote CSP que contém as classes
Domain, Variable, Value, CSP, Expression
Assignment,
e Constraint para a definição de um CSP.
Fonte: Santos (2005, p. 39).
Figura 10 – Classes do pacote CSP do dynDCSP
29
2.6 TRABALHOS CORRELATOS
O Gnu Prolog é um compilador da linguagem Prolog e também um solucionador de
problemas moldados em CSP. Segundo Dias (2003), ele possui diversas funcionalidades
aplicadas à resolução e definição de CSPs, tais como: variáveis de domínio finito totalmente
integradas com as variáveis e inteiros do Prolog; não é necessário descrever explicitamente o
domínio; restrições podem ser declaradas como termos de primitivas simples e definições de
restrições predefinidas. O Gnu Prolog foi desenvolvido com a linguagem C e utiliza a técnica
de propagação para resolver os CSPs, em particular, a arc-consistency (AC), demonstrada em
Hentenryck (1989 apud DIAS, 2003).
Outro trabalho correlato é o descrito em Tralamazza (2004), que apresenta a
implementação um algoritmo para problema de satisfação de restrição distribuída utilizando
orientação a objetos, a linguagem Java e o algoritmo Asynchronous Weak Commitment
(AWC) como relatado por Yokoo (2001 apud TRALAMAZZA, 2004). Além da
implementação do algoritmo, Tralamazza (2004), aplicou duas heurísticas, conflitos mínimos
e a de valor menos utilizado, que dá a preferência de atribuição para o valor menos utilizado
nas restrições, conforme descrito em Filho et al. (1998).
Um trabalho correlato mais recente (SANTOS, 2005) descreve a implementação de um
algoritmo para a solução de Distributed Constraint Optimization Problem (DCOP),
denominado Asynchronous Distributed Optimization (Adopt), executando-o em um ambiente
distribuído. Foi implementado em Java e um dos objetivos desse trabalho foi especificar uma
modelagem molecular como sendo um CSP/DCSP, visto que há semelhança estrutural entre
uma molécula e um grafo, como descrito em Santos (2005). Utilizou-se da plataforma
dynDCSP no seu trabalho, porém efetuou modificações para que o mesmo pudesse solucionar
COPs, refatorando e incluindo algumas classes.
30
3 DESENVOLVIMENTO DO TRABALHO
As seções subseqüentes apresentam a implementação, especificação e integração do
algoritmo busca-com-retrocesso com heurísticas utilizando recursos do dynDCSP e integrado
com o CCB.
3.1 REQUISITOS PRINCIPAIS DO PROBLEMA A SER TRABALHADO
Os principais requisitos deste trabalho são:
a) implementação do algoritmo busca-com-retrocesso;
b) validação dos resultados obtidos com o algoritmo;
c) implementação das heurísticas:
-
variável mais restritiva;
-
variável mais restringida;
-
conflitos mínimos.
d) validação dos resultados obtidos com o algoritmo e as heurísticas;
e) integrar o algoritmo com o CCB.
3.2 ESPECIFICAÇÃO
Na especificação do trabalho, foi utilizado a ferramenta Enterprise Architect (EA) com
Unified Modeling Language (UML) e em conjunto com o paradigma de orientação a objetos.
Os diagramas são apresentados em seções: diagrama de casos de uso (seção 3.2.1), diagrama
de atividades (seção 3.2.2) e diagrama de classes (seção 3.2.3).
3.2.1
Diagrama de casos de uso
Na Figura 11, é demonstrado o diagrama de casos de uso. O ator usuário do sistema
31
informa o CSP, seleciona a heurística desejada e por fim pode pedir pra resolver o CSP.
Figura 11 – Diagrama de casos de uso
3.2.2
Diagrama de atividades
O diagrama da Figura 12 mostra o diagrama de atividades do algoritmo de busca-comretrocesso da seguinte forma:
a) início do algoritmo;
b) é informado um CSP para o algoritmo;
c) é guardado o tempo inicial e inicializado com o valor zero o número de
verificações de consistência;
d) inicia-se o retrocesso recursivo;
e) se encontrou a solução, calcula o tempo total, exibe tempo total e número de
verificações de consistência, retorna a atribuição completa;
f) senão, calcula o tempo total, exibe tempo total e número de verificações de
consistência e retorna nulo;
g) final do algoritmo.
32
Figura 12 – Diagrama de atividades
3.2.3
Diagrama de classes
O diagrama de classes demonstrado na Figura 13 contém quatro classes:
Conflitos Mínimos, CSP
e
Assignment.
As classes
CSP
e
Assignment
ResolveCSP,
são provenientes da
biblioteca do dynDCSP já foram especificadas em Santos (2005) e são demonstradas no
diagrama apenas para se verificar a ordem de dependência entre essas classes, por isso não
serão detalhadas.
A classe
possui seis atributos:
ResolveCSP
verificações de consistência;
sendo
0
chaveHeuristica,
para não utilizar heurística,
restringida e
3
processamento
1
listVarMaisRestritiva
heurísticas
um
variável mais restritiva e
que
ArrayList
inteiro que conta o número de
inteiro que seleciona qual heurística utilizar
para variável mais restritiva,
para conflitos mínimos,
das
vc,
descHeuristica, long
deve
ser
2
para variável mais
que armazena o tempo de
descontado
do
tempo
total,
que deve armazenar a lista ordenada da heurística
listVarMaisRestringida
ordenada da heurística variável mais restringida.
um
ArrayList
que deve armazenar a lista
33
Figura 13 – Diagrama de classes
Os métodos da classe ResolveCSP são:
a)
pesquisaComRetrocesso
que deve ser enviado como parâmetro o CSP e um inteiro
que seleciona a heurística a ser usada, e por fim retorna um
atribuição completa ou
null.
Assignment,
uma
É por este método que se inicia a busca por uma
solução do CSP;
b)
retrocessoRecursivo
é o método que tornará possível a recursividade do
algoritmo. Deve ser enviado como parâmetro a atribuição e o CSP e retorna um
boolean
c)
para permitir o retrocesso no caso da atribuição não ser consistente;
ehCompleta
verifica se a atribuição está completa, ou seja, se todas as variáveis do
CSP tem um valor válido atribuído. Deve ser enviado como parâmetro o CSP e a
atribuição e retorna um boolean;
d)
getVarSemValor
é um método que retorna a primeira variável não atribuída da lista
de variáveis do CSP. Deve ser enviado como parâmetro a atribuição, o CSP e caso
não haja variáveis que ainda não foram atribuídas, retorna null;
e)
tempoDeExecucao
simplesmente calcula e exibe o tempo de execução em segundos
dado como parâmetros um tempo inicial e um tempo final em nanosegundos.
f)
ordenarVariavelMaisRestritiva
com
a
heurística
de
listVarMaisRestritiva
g)
getVarMaisRestritiva
classe
é o método que ordena as variáveis de acordo
variável
mais
restritiva
no
atributo
de
classe
e deve-se enviar como parâmetro o CSP;
retorna uma variável da seqüência obtida pelo atributo de
listVarMaisRestritiva
e que ainda não foi atribuído, por isso, deve-se
34
enviar a atribuição como parâmetro;
h)
ordenarVariavelMaisRestringida
é o método que ordena as variáveis de acordo
com a heurística de variável mais restringida no atributo de classe
listVarMaisRestringida
i)
getVarMaisRestringida
classe
e deve-se enviar como parâmetro o CSP;
retorna uma variável da seqüência obtida pelo atributo de
listVarMaisRestringida
e que ainda não foi atribuído, por isso, deve-se
enviar a atribuição como parâmetro.
A classe
contém o algoritmo de busca local com a heurística de
ConflitosMinimos
conflitos mínimos. Segue os métodos da classe ConflitosMinimos.
a)
iniciaConflitosMinimos
é o método que retorna uma atribuição completa ou
null
quando enviado como parâmetros o CSP e um inteiro que denomina a quantidade
de etapas na busca efetuada pela heurística;
b)
getValorConflitosMinimos
é o método que se deve enviar uma variável, o CSP e a
atribuição retornando um Value contendo o valor de conflitos mínimos;
c)
getNumeroConflitos
retorna um inteiro contendo o número de conflitos que
variável e o valor enviados como parâmetro causam. Também deve ser enviado
como parâmetros a atribuição e o CSP;
d)
getVariaveisConflitantes
retorna uma lista com as variáveis conflitantes contidas
na atribuição, que deve ser enviado como parâmetro juntamente com o CSP;
e)
getViolacoes
é o método que retorna um int que denomina o número de violações
que a variável e valor enviados como parâmetro criam com relação às restrições;
f)
atribuicaoAleatoria
retorna uma atribuição com valores aleatórios atribuídos a
variáveis. Um detalhe fundamental é que a atribuição aleatória não é
necessariamente uma atribuição completa, cabe ao algoritmo de busca local efetuar
essa verificação. Deve ser enviado como parâmetro o CSP;
g)
selecionaVarAleatoria
é o método que retorna uma variável de forma aleatória,
dado uma lista de variáveis como parâmetro;
h)
getDominio
retorna um ArrayList com o domínio enviado como parâmetro.
3.3 IMPLEMENTAÇÃO
A seção implementação está dividida em 2 seções. A primeira (seção 3.3.1), denota as
35
técnicas e ferramentas utilizadas ao longo da implementação deste trabalho enquanto a
segunda (seção 3.3.1), demonstra a operacionalidade da implementação.
3.3.1
Técnicas e ferramentas utilizadas
A implementação deste trabalho foi realizada com as técnicas de orientação a objetos
que proporciona a linguagem de programação Java versão 5.0 e o ambiente de programação
Eclipse versão 3.1.
Juntamente com o Java e o Eclipse, utilizou-se também o framework dynDCSP que
disponibilizou toda uma solução para definição de CSPs por intermédio de classes em Java e
do CCB, parte integrante do dynDCSP, que possibilita a definição de um CSPs em uma
linguagem de alto nível para que o mesmo faça a interpretação e gere os objetos provindos
das classes que o dynDCSP disponibiliza.
É importante citar que mesmo o trabalho utilizando o Java, a literatura expõe
algoritmos de forma estruturada. Portanto, mesmo este trabalho contendo classes, métodos e
relações conforme o paradigma de orientação a objetos recomenda, a programação dos
métodos em si, foi feita de forma estruturada, o que facilita a didática, tendo a mesma
seqüência e programação que é demonstrada nos algoritmos recomendados por Russel e
Norvig(2004).
3.3.1.1 Implementação do algoritmo busca-com-retrocesso
A primeira parte da implementação deste trabalho foi programar o algoritmo de
resolução de CSPs busca-com-retrocesso. Durante a etapa de desenvolvimento, o mesmo
sofreu diversas melhorias com relação ao código em Java, até obter-se um algoritmo com
código simples e objetivo. O algoritmo de busca-com-retrocesso ficou implementado de
acordo com o Quadro 13, o Quadro 14, o Quadro 15 e com o Quadro 16.
No Quadro 13 é apresentado parte do código da classe
pesquisaComRetrocesso.
Pode-se verificar que o método
resolveCSP
com o método
pesquisaComRetrocesso
inicia o
algoritmo para a busca da solução do CSP. Ao chamar este método, devem ser enviados como
parâmetros o objeto csp e um inteiro que fará o papel de um seletor para a heurística desejada.
Observa-se que logo de início, é guardado o tempo inicial e também seleciona a heurística que
36
foi acionada com o parâmetro
usarHeuristica
vazia, é efetuado um condicional
if
e que logo após criar o objeto de atribuição
chamando o método recursivo
retrocessoRecursivo,
enviando como parâmetros a atribuição e o CSP, para que seja criado a árvore de busca, e
quando finalizar, ele deverá retornar
true
ou
false,
sinalizando se foi encontrada ou não a
solução, para aí sim calcular o tempo de execução, número de verificações de consistência e
retornar para o método ou a atribuição completa ou nulo.
public Assignment pesquisaComRetrocesso(CSP csp,int usarHeuristica){
//Seta qual heurística será usada
chaveHeuristica = usarHeuristica;
//Determina heurística
switch(chaveHeuristica){
case 1:
//Ordena lista de variavel mais restritiva
ordenarVariavelMaisRestritiva(csp);
break;
case 2:
//Ordena lista de variavel mais restringida
ordenarVariavelMaisRestringida(csp);
break;
case 3:
//Pega tempo inicial da heuristica
tInicial = System.nanoTime();
//Tenta resolver pelos conflitos mínimos
Assignment confMinAtrib =
new ConflitosMinimos().iniciaConflitosMinimos(csp,50,this);
//se achou resposta
if(confMinAtrib != null){
//calcula e exibe o tempo de execução
tempoExecucao(tInicial,System.nanoTime(),descHeuristica);
//retorna a atribuição completa
return confMinAtrib;
};
}
//Pega tempo inicial
long tInicial = System.nanoTime();
//Cria o objeto de atribuiçao vazia
Assignment atribuicao = new Assignment();
//Inicia retrocesso recursivo RETROCESSO-RECURSIVO( {}, psr )
if (retrocessoRecursivo(atribuicao,csp)) {
//calcula e exibe o tempo de execução
tempoExecucao(tInicial,System.nanoTime(),descHeuristica);
//retorna a atribuição completa
return atribuicao;
} else {
//calcula e exibe o tempo de execução
tempoExecucao(tInicial,System.nanoTime(),descHeuristica);
//retorna nulo, ou seja, não há solução para o CSP
return null;
}
}
Quadro 13 – Método pesquisaComRetrocesso da classe resolveCSP
No quadro 14, é demonstrado o método
classe resolveCSP.
retrocessoRecursivo
também incluso na
37
private boolean retrocessoRecursivo(Assignment atrib, CSP csp) {
//Se atribuição está completa
if( ehCompleta(atrib, csp) ){
//Então retorna a Atribuição completa
return true;
}
//var <- SELECIONAR VARIAVEL NAO ATRIBUIDA
Variable var = null;
switch(chaveHeuristica){
case 0:
var = getVarSemValor(atrib, csp);
break;
case 1:
var = Heuristicas.getVarMaisRestritiva(atrib);
break;
case 2:
var = Heuristicas.getVarMaisRestringida(atrib);
break;
}
//Para cada valor do Domínio faça
Iterator i = var.getDomain().iterator();
while(i.hasNext()){
Value v = (Value)i.next();
//adiciona valor e variável na Atribuição
atrib.putVariableValue(var, v);
//Incrementa verificações de consistência
vc++;
//Se valor é consistente na atribuição
if (csp.isConsistent(atrib)){
//resultado <- RETROCESSO RECURSIVO(atribuicao,csp)
if (retrocessoRecursivo(atrib,csp)) {
//retorna resultado
return true;
}
}
//Remove variável e valor da Atribuição
atrib.removeVariable(var);
}
//retorna resultado falso
return false;
}
Quadro 14 – Método retrocessoRecursivo da classe resolveCSP
No início do método
método
ehCompleta
retrocessoRecursivo
é efetuado um condicional
if
com o
enviando a atribuição e o CSP como parâmetros que verifica se a
atribuição é completa, retornando
true.
Caso a atribuição não esteja completa, é selecionada
uma variável que ainda não foi atribuída, utilizando heurística, ou não, dependendo da entrada
inicial do algoritmo com a chave
chaveHeuristica.
Se não foi utilizado heurística na seleção
da variável, é apenas retornada uma da lista de variáveis do objeto
getVarSemValor,
csp
com o método
enviando como parâmetros a atribuição para descobrir quais variáveis já
foram atribuídas e o objeto csp para obter a lista de variáveis.
Após, para cada valor do domínio da variável selecionada, é adicionado a variável e o
valor na atribuição e verificado se a consistência com as restrições é mantida com o método
isConsistent,
condicional
encontrado na classe
if,
e retornado
true
CSP
da biblioteca dynDCSP. Sendo sim, é feito mais um
é feita a recursividade chamando o próprio método
38
retrocessoRecursivo.
Caso contrário, a atribuição inconsistente é removida e é continuado o
laço iterativo de cada valor do domínio da variável.
Quando a árvore montada tiver uma atribuição completa, os métodos subseqüentes
chamados recursivamente, retornaram true sucessivamente até o algoritmo chegar no método
pesquisaComRetrocesso,
que é o primeiro nível da busca, para retornar a atribuição, o mesmo
pode-se dizer quando não se consegue achar a consistência com as atribuições, retornando
false,
e por fim o método pesquisaComRetrocesso retornando null.
A seguir, o Quadro 15 exibe o método
ehCompleta
que verifica se a atribuição é
completa.
public boolean ehCompleta(Assignment atrib, CSP csp){
int atribSize = atrib.size();
int varsSize = csp.getVariables().size();
return atribSize == varsSize;
}
Quadro 15 – Método ehCompleta da classe resolveCSP
O método ehCompleta avalia o tamanho das listas de atribuição e das variáveis do CSP,
se os tamanhos forem iguais, retorna true, senão false. Esse método se tornou simples pois a
atribuição sempre será consistente antes da sua chamada, bastando apenas verificar se o
tamanho da lista atribuição corresponde com o tamanho da lista de variáveis do CSP.
O método getVarSemValor é um método que meramente retorna a primeira variável não
atribuída da lista de variáveis. As variáveis do CSP são percorridas e é efetuado o condicional
if
para verificar se a variável atual da lista ainda não foi atribuída, caso verdadeiro, retorna-se
a variável, caso contrário, continua-se percorrendo até achar a variável que ainda não foi
atribuída. Ocorrendo o término da lista, ou seja, não havendo nenhuma variável sem valor, é
retornado null. No Quadro 16 e demonstrado o método getVarSemValor.
private Variable getVarSemValor(Assignment atrib, CSP csp){
ArrayList variaveis = new ArrayList();
variaveis = (ArrayList)csp.getVariables();
for(int i=0; i < variaveis.size(); i++){
Variable var = (Variable)variaveis.get(i);
if(!atrib.contains(var)){
return var;
}
}
return null;
}
Quadro 16 – Método getVarSemValor da classe resolveCSP
Com o algoritmo busca-com-retrocesso implementado, a validação do mesmo foi
efetuada com o problema de coloração de mapas, e com sucesso, obteve-se como solução a
saída do console conforme o Quadro 17.
39
Algoritmo Iniciado...
*** Atribuicao Completa! ***
Verificações de Consistência = 21
Tempo de execução= 0.007523861 segundos.
{v=azul, tn=verde, t=azul, q=azul, ngs=verde, ao=azul, am=vermelho}
Quadro 17 – Saída do console da resolução de um CSP
Como se pode observar no Quadro 17, o algoritmo busca-com-retrocesso executou
quatorze verificações de consistência (VC), ou seja, chamou o método
isConsistent
do CSP
quatorze vezes. O tempo de execução do algoritmo foi de 0,007523861 segundos e obteve
como resposta para o problema, a atribuição {v=verde, tn=azul, t=vermelho, q=verde,
ngs=azul, ao=verde, am=vermelho}, uma solução consistente para o problema.
3.3.1.2 Implementação da heurística variável mais restritiva
Ao invés do algoritmo busca-com-retrocesso chamar o método
chamado o método
getVariavelMaisRestritiva
getVarSemValor,
é
quando a heurística é ativada. A
implementação é apresentada no Quadro 18.
//Retorna a primeira variavel mais restrita não atribuída
private Variable getVariavelMaisRestritiva(Assignment atrib){
//Para todas as variáveis da lista de mais restritas
for(int i=0;i < listVarMaisRestritiva.size();i++){
//se a variável mais restritiva atual não foi atribuída
if(!atrib.contains((Variable)listVarMaisRestritiva.get(i))){
//então retorna a variável mais restritiva atual
return (Variable)listVarMaisRestritiva.get(i);
}
}
//Retorna null caso não haja mais variáveis mais restritivas não atribuídas
return null;
}
Quadro 18 – Método getVariavelMaisRestritiva da classe resolveCSP
Para obter a variável mais restrita não atribuída, deve ocorrer antes o método
ordenarVariávelMaisrestritiva,
que pega a lista de todas as variáveis do CSP e as ordena em
ordem crescente de acordo com o maior número de restrições. Implementou-se a heurística de
variável mais restritiva, conforme o Quadro 19 onde contém o seu algoritmo nas linhas de
comentário, que são antecedidas por //.
40
//***HEURÍSTICA*** = VARIÁVEL MAIS RESTRITIVA (VAR COM O MAIOR NRO DE RESTRIÇÕES)
private void ordenarVariavelMaisRestritiva(CSP csp){
//Inicializa o maior número de restrições
int maiorNumRestricoes = 0;
//Map para guardar a variável e o número de restrições
Map<Variable,Integer> mapVariavelRestricoes = new HashMap<Variable,Integer>();
//Enquanto há restrições
Collection r = csp.getConstraints();
Iterator it = r.iterator();
while(it.hasNext()){
//Pega próxima restrição
Constraint cons = (Constraint) it.next();
//Pega a expressão da restrição
Expression exp = cons.getExpression();
//Pega as envolvidas na expressão da restrição
ArrayList variaveisDaExpressao = (ArrayList)exp.getVariables();
//Para cada variável da expressão
for(int i=0;i<variaveisDaExpressao.size();i++){
//Pega a variavel atual
Variable variavelAtual = (Variable)variaveisDaExpressao.get(i);
//se variável já está no map
if(mapVariavelRestricoes.containsKey(variavelAtual)){
//pega o qde atual de restrições
int qdeAtual = mapVariavelRestricoes.get(variavelAtual);
//remove do map
mapVariavelRestricoes.remove(variaveisDaExpressao.get(i));
//insere no map com a qde incrementada com 1
mapVariavelRestricoes.put(variavelAtual,qdeAtual+1);
//Se a qdeAtual+1 for o maior número de restrições
if((qdeAtual+1 > maiorNumRestricoes)){
//o maior número de restrições é o atual
maiorNumRestricoes= qdeAtual+1;
}
}else{
//senão adiciona a variável com 1 restrição
mapVariavelRestricoes.put(variavelAtual,1);
//Se a qdeAtual(1) for o maior número de restrições
if((1 > maiorNumRestricoes)){
//o maior número de restrições é o atual
maiorNumRestricoes= 1;
}
}
}
}
//ORDENAÇÃO
for (int x=maiorNumRestricoes;x >= 0;x--){
for(int i=0;i < csp.getVariables().size();i++){
Variable var= (Variable)csp.getVariables().get(i);
//Se lista acabou, sobrou as vars sem restrição, entao adicionar todas
if(x==0){
if(!listVarMaisRestritiva.contains(var)){
listVarMaisRestritiva.add(var);
}
}else{
if(mapVariavelRestricoes.containsKey(var))
if((int)mapVariavelRestricoes.get(var) == x)
listVarMaisRestritiva.add(var);
}
}
}
}
Quadro 19 – Método ordenarVariavelMaisRestritiva da classe resolveCSP
41
3.3.1.3 Implementação da heurística variável mais restringida
Observa-se no Quadro 20 a implementação da heurística de variável mais restringida,
contendo em suas linhas de comentário, o algoritmo da mesma.
//***HEURÍSTICA***= VARIÁVEL MAIS RESTRINGIDA (VAR MENOR NRO DE VALORES DO DOMÍNIO)
private void ordenarVariavelMaisRestringida(CSP csp){
//Lista de seleção das variáveis
Map<Variable,Integer> mapVariavelQtde = new HashMap<Variable,Integer>();
//Menor quantidade de valores do domínio
int menorQtde = Integer.MAX_VALUE;
//Maior quantidade de valores do domínio
int maiorQtde = 0;
//Pega a lista de variaveis do CSP
ArrayList variaveis = (ArrayList)csp.getVariables();
//Para cada variável do CSP
for(int i=0;i<variaveis.size();i++){
//Inicia quantidade atual com 0
int qtdeAtual=0;
//Pega a variavel atual
Variable variavelAtual = (Variable)variaveis.get(i);
//Para cada valor do dominio da variável
Iterator it = variavelAtual.getDomain().iterator();
while(it.hasNext()){
it.next();
//incrementa quantidade de valores do domínio
qtdeAtual++;
}
//Se menor quantidade, guarda
if(qtdeAtual<menorQtde )
menorQtde= qtdeAtual;
//Se maior quantidade, guarda
if(qtdeAtual>maiorQtde)
maiorQtde= qtdeAtual;
//adiciona variavel e quantidade na lista
mapVariavelQtde.put(variavelAtual,qtdeAtual);
}
//ORDENAÇÃO
for (int x=menorQtde;x <= maiorQtde;x++){
for(int i=0;i < csp.getVariables().size();i++){
//Se lista acabou, sobrou as vars sem restrição, entao adicionar todas
if(x==0){
if(!listVarMaisRestringida.contains(csp.getVariables().get(i))){
listVarMaisRestringida.add((Variable)csp.getVariables().get(i));
}
}else{
if((int)mapVariavelQtde.get(csp.getVariables().get(i)) == x)
listVarMaisRestringida.add((Variable)csp.getVariables().get(i));
}
}
}
}
Quadro 20 – Método ordenarVariavelMaisRestringida da classe resolveCSP
Assim como na heurística de variável mais restritiva é chamado um método para
retornar a primeira variável mais restritiva não atribuída, a heurística de variável mais
restringida funciona da mesma forma, só que ordenando a lista de variáveis do CSP de forma
decrescente pela quantidade de valores do seu domínio. Pode-se observar o método
getVariavelMaisRestringida
no Quadro 21.
42
//Retorna a primeira variavel mais restringida não atribuída
private Variable getVariavelMaisRestringida(Assignment atrib){
//Para todas as variáveis da lista de mais restringidas
for(int i=0;i < listVarMaisRestringida.size();i++){
//se a variável mais restringida atual não foi atribuída
if(!atrib.contains((Variable)listVarMaisRestringida.get(i))){
//então retorna a variável mais restringida atual
return (Variable)listVarMaisRestringida.get(i);
}
}
//Retorna null caso não haja mais variáveis mais restringidas não atribuídas
return null;
}
Quadro 21 – Método getVariavelMaisRestringida da classe resolveCSP
3.3.1.4 Implementação da heurística de conflitos mínimos em busca local
A busca local com a heurística de conflitos mínimos é um algoritmo independente de
pré-processamento que se inicia antes do algoritmo de busca-com-retrocesso e caso ele
encontre a solução, é terminado o algoritmo ou caso contrário, é iniciado a busca-comretrocesso.
Para
iniciar
iniciaConflitosMinimos
esta
da Classe
busca
heurística,
ConflitosMinimos.
é
necessário
chamar
o
método
No Quadro 22 é possível visualizar o
algoritmo implementado da heurística de conflitos mínimos.
//Inicia Heurística de Conflitos Mínimos
public Assignment conflitosMinimos(CSP csp,int maximoEtapas){
//Inicia a atribuição com uma estado aleatório de valores
Assignment corrente = atribuicaoAleatoria(csp);
//Para cada passo de etapas
for(int i=1;i <= maximoEtapas;i++){
//Se o CSP é consistente e a atribuição é completa
if((csp.isConsistent(corrente))&&(ehCompleta(corrente,csp)))
//retorna a corrente(atribuição)
return corrente;
//Senão, seleciona uma variável aleatória da lista de conflitantes
Variable varConflitante =
selecionaVarAleatoria(getVariaveisConflitantes(csp,corrente));
//Seleciona o valor de conflitos mínimos pra variável conflitante escolhida
Value valorConflitoMinimo =
getValorConflitosMinimos(varConflitante,csp,corrente);
//remove a variavel e valor antigos da atribuição
corrente.removeVariable(varConflitante);
//Insere variavel e novo valor a atribuição
corrente.putVariableValue(varConflitante,valorConflitoMinimo);
}
//Se acabou tentativas, retorna null
return null;
}
Quadro 22 – Método iniciaConflitosMinimos da classe ConflitosMinimos
O método
getValorConflitosMinimos
retorna o valor que gera o número mínimo de
conflitos para uma variável enviada como parâmetro. Este método é apresentado no Quadro
23.
43
private Value getValorConflitosMinimos(Variable var,CSP csp, Assignment atrib){
//Map para os valores e conflitos
Map<Value,Integer> selectCM = new HashMap<Value,Integer>();
//Conflitos mínimos recebe o maior inteiro possível
int conflitosMinimos = Integer.MAX_VALUE;
Iterator i = var.getDomain().iterator();
//Enquanto tem valores do domínio da variável
while(i.hasNext()){
Value valor = (Value)i.next();
//Pega a quantidade de conflitos atuais
int conflitosAtual= getNumeroConflitos(var,valor,atrib,csp);
//Insere valor e conflitos atuais
selectCM.put(valor,conflitosAtual);
//Se conflito atual for menor que conflitos mínimos
if(conflitosAtual < conflitosMinimos){
//Conflitos mínimos é o atual
conflitosMinimos= conflitosAtual;
}
}
//Escolher o valor de conflito mínimo aleatório
List vars = new ArrayList();
i = var.getDomain().iterator();
while(i.hasNext()){
Value valor = (Value)i.next();
if(selectCM.get(valor) == conflitosMinimos)
vars.add(valor);
}
Collections.shuffle(vars);
//Retorna o primeiro da lista aleatória
return (Value)vars.get(0);
}
Quadro 23 – Método getValorConflitosMinimos da classe ConflitosMinimos
O método getNumeroConflitos retorna a quantidade de conflitos que uma variável gera
ao ser atribuída com o valor enviado como parâmetro. Sua implementação é apresentada no
Quadro 24.
private int getNumeroConflitos(Variable variavelConflitante, Value valor,
Assignment atrib,CSP csp) {
//Pega uma cópia da atribuicao
Assignment copiaAtrib = (Assignment)atrib.clone();
//remove a variavel conflitante da cópia
copiaAtrib.removeVariable(variavelConflitante);
//atribui novo valor na cópia
copiaAtrib.putVariableValue(variavelConflitante, valor);
//pega as variáveis conflitantes
//List varsConflitantes = getVariaveisConflitantes(csp,copiaAtrib);
//retorna o nro de conflitos(nro de vars conflitantes)
int nroConflitos = getViolacoes(csp, copiaAtrib,variavelConflitante);
return nroConflitos;
}
Quadro 24 – Método getNumeroConflitos da classe ConflitosMinimos
O método
getVariaveisConflitantes
retorna uma lista com as variáveis que estão em
conflito na atribuição. Este método é apresentado no Quadro 25.
44
private List getVariaveisConflitantes(CSP csp,Assignment atrib) {
List variaveisConflitantes = new ArrayList();
List variaveis = csp.getVariables();
//Para cada variável do CSP
for(int i=0;i<variaveis.size();i++){
//pega a variavel atual
Variable variavelAtual = (Variable)variaveis.get(i);
//Se não é satisfeito com o valor
if (getViolacoes(csp,atrib,variavelAtual) != 0)
//Variável é conflitante!
variaveisConflitantes.add(variavelAtual);
}
return variaveisConflitantes;
}
Quadro 25 – Método getVariaveisConflitantes da classe ConflitosMinimos
Para obter o número de violações de uma variável é utilizado o método
getViolacoes.
Este mesmo método é utilizado para saber se uma atribuição é consistente, retornando 0 para a
possibilidade. Este método é apresentado no Quadro 26.
private int getViolacoes(CSP csp, Assignment atrib, Variable var) {
//Numero de violações
int violacoes = 0;
Collection r = csp.getConstraints();
Iterator it = r.iterator();
//Enquanto tiver restrições
while(it.hasNext()){
//Próxima restrição
Constraint cons = (Constraint) it.next();
//Pega a expressão
Expression exp = cons.getExpression();
//Pega as variaveis da expressão
ArrayList variaveis = (ArrayList)exp.getVariables();
//Se variavel foi atribuída
if (variaveis.contains(var)) {
try {
//Se tem violação
if (!cons.eval(atrib))
//Incrementa violações
violacoes++;
} catch (VariableNotFoundException e) {
e.printStackTrace();
}
}
}
//retorna as violações
return violacoes;
}
Quadro 26 – Método getViolacoes da classe ConflitosMinimos
O método
atribuicaoAleatoria
gera uma atribuição aleatória para o CSP informado,
podendo a mesma ser consistente ou não. Este método é apresentado no Quadro 27.
45
private Assignment atribuicaoAleatoria(CSP csp){
Assignment atribuicao = new Assignment();
//Para cada variavel do CSP
for(int i=0; i< csp.getVariables().size(); i++){
//Pega a variavel
Variable variavel = (Variable)csp.getVariables().get(i);
//Pega um valor aleatório
Domain dominio = variavel.getDomain();
//System.out.println(dom);
List listDominio = getDominio(dominio);
Collections.shuffle(listDominio);
Value v = (Value)listDominio.get(0);
//Atribui Valor a Variável
atribuicao.putVariableValue(variavel,v);
}
//Retorna Atribuição
return atribuicao;
}
Quadro 27 – Método atribuicaoAleatoria da classe ConflitosMinimos
Para obter uma variável aleatória a partir de uma lista de variáveis, usa-se o método
selecionaVarAleatoria.
Esse método é mostrado no Quadro 28.
private Variable selecionaVarAleatoria(List vars){
Random randomGenerator;
randomGenerator = new Random();
int index = randomGenerator.nextInt(vars.size());
return (Variable)vars.get(index);
}
Quadro 28 – Método selecionaVarAleatoria da classe ConflitosMinimos
O método
getDominio
retorna um
ArrayList
de um domínio enviado como parâmetro.
No Quadro 29 pode-se visualizar este método.
private ArrayList getDominio(Domain d){
ArrayList dominio = new ArrayList();
Iterator i = d.iterator();
while(i.hasNext()){
Value v = (Value)i.next();
dominio.add(v);
}
return dominio;
}
Quadro 29 – Método getDominio da classe ConflitosMinimos
3.3.1.5 Integração com o CCB
Para a integração deste trabalho com o CCB, não bastou só a adaptação deste para que
o mesmo funcione com o CCB. Foi necessário importar os pacotes e classes que
implementam o CCB e editá-las a fim de remover as referências com o framework DynDCSP
pois o mesmo funcionava somente a partir da execução deste framework.
Os pacotes importados foram os de interface, de análise semântica e de análise
sintática. No pacote
ui,
que contém a interface do CCB foi modificado a classe
BuilderGUI
46
para que se pudesse selecionar através de um
comboBox
a heurística desejada conforme o
Quadro 30.
box = new Choice();
box.addItem("Only Backtracking");
box.addItem("Backtracking with V+Rtt");
box.addItem("Backtracking with V+Rtg");
box.addItem("Backtracking with MinC");
toolBar.add(box);
Quadro 30 – Inserção de um comboBox na classe BuilderGUI
Ao invés do botão
buildProblemFile
da classe
Build
gerar os objetos da classe CSP com o método
BuilderGUI,
este mesmo botão foi modificado para
Solve
e além
de gerar os objetos do CSP, enviá-los para o algoritmo busca-com-retrocesso resolver e
retornar a atribuição, exibindo o sucesso ou não da resposta para o problema encontrado. A
modificação é demonstrada no Quadro 31.
private void buildProblemFile(){
if ( saveFile() ){
errorMessages.setText("--- COMPILING ----\n\r");
getBuilder().buildProblem(file);
Iterator i = getBuilder().getBuiltProblems().values().iterator();
while(i.hasNext()){
resolveCSP.BuiltProblem ccb = (resolveCSP.BuiltProblem)i.next();
Assignment result = new ResolveCSP().pesquisaComRetrocesso(
ccb.getProblem(),box.getSelectedIndex());
errorMessages.setText("--- RESULT ---- \n\r"+result.toString());
}
}
}
Quadro 31 – Inserção do método pesquisaComRetrocesso na classe BuilderGUI
3.3.2
Operacionalidade da implementação
Para a operacionalidade da implementação, deve-se ter a pasta com todo o projeto
ResolveCSP,
abri-la e executar o arquivo de lote
executa.bat
ou executar a linha de comando
conforme o Quadro 32, que é o mesmo conteúdo do arquivo de lote.
java -classpath bin;lib/dcsp.jar resolveCSP.GeraInterfaceCCB
Quadro 32 – Arquivo de lote executa.bat
É possível também executá-lo através da IDE Eclipse, abrindo o projeto ResolveCSP, e
executar como um aplicativo Java a classe geraInterfaceCCB demonstrada no Quadro 33. Esta
classe contém o método
CSP.
main
que executa e exibe a interface do CCB para a resolução de um
47
package resolveCSP;
import ui.BuilderGUI;
public class GeraInterfaceCCB {
public static void main(String[] args) {
new BuilderGUI().show();
}
}
Quadro 33 – Classe GeraInterfaceCCB
Para executar o CCB é necessário importar a classe
interface do CCB e criar um método
BuilderGUI
main.
para poder executar o método
ui.BuilderGUI,
que contém a
Após é preciso criar um objeto da classe
show.
Logo após executar o programa pela forma
escolhida, é exibido a tela conforme a Figura 14.
Figura 14 – Interface do CCB
Após o início de interface, é possível especificar um CSP no primeiro campo de texto
disponível observando de cima para baixo, ou mesmo abrir um arquivo de texto contendo o
CSP previamente salvo pelo CCB.
Para verificar a operacionalidade do trabalho, especificou-se um CSP do problema de
coloração com o mapa de Santa Catarina. Considerou-se as como regiões do problema, as
cidades do estado e o domínio contendo 6 cores. A especificação na linguagem de alto nível
do CCB teve quase 1922 linhas.
Para abrir o arquivo de texto que deverá conter a especificação de um CSP, deve-se
clicar no menu File e depois em Open ou pressionar CTRL
+ O
ou ainda clicar no botão abrir na
48
barra de ferramentas do programa. Logo após, aparecerá uma tela similar ao da Figura 15.
Figura 15 – Tela abrir arquivo
Localiza-se e seleciona-se o arquivo desejado e clica-se em
open
similar a da Figura 16.
Figura 16 – Tela do CBB com um CSP especificado
e será exibido a tela
49
Com o CSP definido na tela, deve-se escolher o método de resolução do CSP, assim
como na Figura 17.
Figura 17 – Seleção do método de resolução
Se é preferido só a busca-com-retrocesso, seleciona-se a primeira opção,
Backtracking.
Only
Se é desejado a busca-com-retrocesso com a heurística de variável mais
restritiva, seleciona-se a segunda opção
Backtracking with V+Rtt.
Caso seja preferido a
busca-com-retrocesso com a heurística de variável mais restringida, seleciona-se a opção
Backtracking
with
V+Rtg.
Ou ainda, se é preferido a heurística de conflitos mínimos,
seleciona-se a quarta e última opção Backtracking
with MinC.
Neste último caso, o algoritmo
de busca local com a heurística de conflitos mínimos será iniciado e caso não encontre a
solução em um número de 50 etapas, é iniciado o algoritmo de busca-com-retrocesso.
Depois de selecionada a opção de busca com a heurística, é possível clicar em
Solve
para iniciar o algoritmo de busca com a opção de heurística desejada, assim como na Figura
18.
50
Figura 18 – Tela do CBB com um CSP especificado e resolvido com heurística
3.4 RESULTADOS E DISCUSSÃO
Os resultados que serão mostrados, foram obtidos a partir de um notebook com
processador AMD Athlon 64bits 3200+ com 512Mb de memória RAM (Random Access
Memory) e sistema operacional Microsoft Windows XP Professional. É importante salientar
que todo o processamento e tempo gasto pelas heurísticas está sendo ignorado, já que a
gerência do tempo gasto com elas, é obtido implementando métodos de gerência como o de
consistência de arcos, existentes em Russell e Norvig (2004). Com relação ao algoritmo e
heurística de conflitos mínimos optou-se por 50 como limite de passos máximos que este
algoritmo pode efetuar, pois, conforme Russell e Norvig (2004, p.147), a heurística de
conflitos mínimos por busca local resolve até mesmo o problema de um milhão de rainhas em
uma média de 50 etapas. Nesta busca heurística, é considerado todo o tempo de busca, para
demonstrar como o tempo de processamento da heurística influencia no tempo decorrido do
início até a solução do problema.
51
Para realizar uma análise dos trabalhos correlatos em relação a este trabalho, optou-se
por somente incluir o Gnu Prolog. Isso deve-se ao mesmo ser o único trabalho correlato que
utiliza um algoritmo de busca centralizada. Somente será apresentado o mesmo quando
houverem comparações com relação ao tempo de execução, devido ao mesmo não exibir o
número de verificações de consistência que efetua.
Ao executar o algoritmo aplicado ao problema de coloração de mapas da Figura 1 por
10 vezes seguidas e calculando a média das execuções, observa-se na Figura 19 que houve um
ganho nítido comparado ao algoritmo de busca-com-retrocesso com o mesmo algoritmo
aplicado a heurística de variável mais restritiva e o de conflitos mínimos. Na busca pelo
solução do CSP, o algoritmo de busca-com-retrocesso teve que gerar 21 nodos no seu grafo,
ou seja, teve de verificar a consistência da atribuição 21 vezes, enquanto o mesmo algoritmo
aplicado a heurística de variável mais restritiva, gerou 15 nodos. A heurística de conflitos
mínimos diminuiu ainda mais o número de verificações de consistência para somente 8. Notase que foi obtido um ganho expressivo apesar de ser um problema relativamente simples para
o algoritmo. Não foi testado esse problema com a heurística de variável mais restringida
devido ao fato do problema não possuir domínios diferentes para cada variável, tornando
assim desnecessário a sua aplicação.
Verificações de Consistência (VC)
25
21
20
15
15
10
8
5
0
Busca-com-retrocesso
Busca-com-retrocesso com
variável mais restritiva
Conflitos Mínimos
Figura 19 – VC das execuções: problema da Figura 1
Calculando a média dos tempos de execução em milisegundos, obteve-se o gráfico da
Figura 20. O Gnu Prolog teve um tempo 9 vezes melhor que o menor tempo obtido por este
trabalho. Isso se deve ao fato do mesmo utilizar mais heurísticas e métodos de verificação
prévia como a de consistência de arcos. Nota-se que o algoritmo busca-com-retrocesso obteve
52
ganho quando aplicado a heurística de variável mais restritiva. A heurística de conflitos
mínimos gastou mais de 5 vezes o tempo que o algoritmo de busca-com-retrocesso, porém
obteve a solução com menos VC, conforme a Figura 16.
40,0
34,8
Tempo em milisegundos
35,0
30,0
25,0
20,0
15,0
7,4
10,0
5,0
5,5
0,6
0,0
Gnu Prolog
Busca-comretrocesso
Busca-comretrocesso com
Variável mais
restritiva
Conflitos Mínimos
Figura 20 – Tempo médio das execuções: problema da Figura 1
Para obter soluções com menor número de VC com a heurística de variável mais
restringida, especificou-se um CSP de coloração de mapas com domínios diferentes aplicados
às variáveis do CSP.
As restrições deste problema podem ser observadas no grafo conforme a Figura 21.
Figura 21 – Problema de coloração de mapas com domínios diferentes.
A especificação deste CSP no CCB ficou conforme o Quadro 34.
53
Csp
Id: Coloracao mapas com dominios diferentes;
Version: 1.0;
Description: Coloracao de mapas. Autor Alexsandro S Pires;
Domains
cores1 : {1};
cores2 : {1,2};
cores3 : {1,2,3};
Variables
A, B, C : cores3;
D, E, F : cores2;
G, H : cores1;
Constraints
A != B;
A != C;
A != E;
A != G;
A != H;
B != E;
B != F;
C != E;
C != F;
D != F;
E != F;
F != G;
Quadro 34 – Código fonte do problema de coloração de mapas com domínios diferentes
Ao executar este CSP por 10 vezes seguidas, e obtendo-se a média das verificações de
consistência, obteve-se o resultado conforme a Figura 22. O resultado obtido com este
problema foi ainda maior aplicado as heurísticas. Houve um ganho de no mínimo 20% se
comparado as execuções heurísticas do que só o algoritmo de busca-com-retrocesso. É
importante citar que a heurística de conflitos mínimos não encontrou a solução em 2
execuções das 10 feitas, devido a isto, sua média das verificações de consistência ficou um
pouco menor que a de variável mais restringida.
Verificações de Consistência (VC)
80
73
70
60
50
40
29
30
20
14
12,4
Busca-comretrocesso com
variável mais
restringida
Conflitos Mínimos
10
0
Busca-comretrocesso
Busca-comretrocesso com
variável mais restritiva
Figura 22 – VC das execuções: coloração de mapas com domínios diferentes.
54
No Figura 23, é evidenciado novamente o ganho de tempo obtido pelas heurísticas que
o Gnu Prolog implementa, sendo neste caso 4 vezes mais rápido que o melhor tempo deste
trabalho. Também se observa a eficiência da heurística de variável mais restringida diminuir o
tempo de 23,5 milisegundos para apenas 6,3 milisegundos, um ganho de mais de 300%.
Comparando a Figura 22 com a Figura 23 e observando os resultados dos conflitos mínimos,
verifica-se novamente a elevação do tempo enquanto se considera o tempo gasto pela
heurística, já que as VC foram praticamente iguais se comparado com a heurística de variável
mais restringida.
60
Tempo em milisegundos
49,7
50
40
30
23,5
17,1
20
6,3
10
1,5
0
Gnu Prolog
Busca-comretrocesso
Busca-comretrocesso com
variável mais
restritiva
Busca-comConflitos Mínimos
retrocesso com
variável mais
restringida
Figura 23 – Tempo médio das execuções: coloração de mapas com domínios diferentes
No problema das n-rainhas com n=4, fez-se também uma série de 10 execuções para
cada algoritmo e heurística, obtendo o gráfico da Figura 24.
Verificações de Consistência (VC)
70
60
58
58
58
50
40
30
16,8
20
10
0
Busca-comretrocesso
Busca-comretrocesso com
variável mais restritiva
Busca-comretrocesso com
variável mais
restringida
Figura 24 – VC nas execuções: n-rainhas com n=4
Conflitos Mínimos
55
Nota-se que somente houve ganho com a heurística de conflitos mínimos, isso se deve
ao fato do problema das n-rainhas ter domínios iguais onde todas as variáveis possuem o
mesmo número de valores do domínio, o que anula a heurística de variável mais restringida e
também possui restrições entre todas as variáveis de forma idêntica, sendo as variáveis
diferentes de todas as outras, anulando a heurística de variável mais restritiva. Com a busca
local e a heurística de conflitos mínimos obteve-se ganho médio superior a 300% se
comparado com o gasto na busca pelas outras heurísticas.
Nas comparações de tempo com este problema, exibido na Figura 25, este trabalho
obteve um ganho em relação ao Gnu Prolog, evidenciados na heurística de variável mais
restringida. Isso se deve ao problema aplicado ser mais complexo e as heurísticas do Gnu
Prolog estarem gastando mais tempo. Com relação o tempo do algoritmo busca-comretrocesso, o mesmo com a variável mais restritiva e o Gnu Prolog praticamente obteve-se o
mesmo tempo. Evidencia-se novamente um maior tempo gasto pelo algoritmo de busca local
com a heurística de conflitos mínimos.
Tempo em milisegundos
60,0
52,6
50,0
40,0
30,0
20,0
18,7
17,5
19,0
10,6
10,0
0,0
Gnu Prolog
Busca-comretrocesso
Busca-comBusca-comConflitos Mínimos
retrocesso com retrocesso com
variável mais
variável mais
restritiva
restringida
Figura 25 – Tempo médio das execuções: n-rainhas com n=4
56
4 CONCLUSÕES
A implementação do algoritmo busca-com-retrocesso se mostrou eficaz na resolução
de CSPs com todos os problemas testados. Demonstrou soluções concisas com as restrições e
domínios informados. Quando se aliou o algoritmo busca-com-retrocesso com as heurísticas,
pode-se verificar o poder de minimizar o custo da busca com rotinas de escolha que se
baseiam no domínio e nas restrições. É evidente o ganho do algoritmo com as heurísticas
presentes neste trabalho. Elas se mostraram eficientes, reduzindo o custo na busca pela
solução do CSP, o que satisfaz as expectativas que a literatura aponta para sua utilização.
Diante desses resultados, tem-se a conclusão de que o trabalho atendeu a todos os objetivos
previamente formulados.
A ferramenta utilizada para a implementação, a IDE Eclipse, se mostrou adequada a
esta implementação. Ela forneceu todo o material necessário a uma implementação bem
sucedida como a possibilidade de depurar o programa, a possibilidade de explorar as classes
por pacotes, e o auto-complemento de código. A especificação deste trabalho, desenvolvida
com o EA, se mostrou adequada a UML. Os pacotes de especificação de CSP que o dynDCSP
disponibiliza, funcionou de maneira adequada em todas as situações testadas, tendo uma
documentação que facilitou o entendimento e utilização das classes e métodos que o mesmo
disponibiliza. O CCB também funcionou da maneira esperada em todas as situações, tendo
uma interface simples de operar, porém só era muito atrelado ao dynDCSP, tendo que
executar o dynDCSP para usar o CCB.
Como vantagens, pode-se citar a implementação do algoritmo em Java, o que torna a
aplicação portável a diversas plataformas de sistema operacionais, além de ser integrada com
o editor do CCB, deixando assim um trabalho completo com editor, compilador e algoritmo
de resolução heurístico, podendo a mesma ser uma ferramenta didática onde o professor pode
ensinar seus alunos sobre CSP, os alunos especificarem os CSPs neste trabalho para verem os
resultados da busca e também demonstrar como o CSP é resolvido por um algoritmo de busca
heurístico. Cientificamente, pode-se demonstrar como as heurísticas se mostram eficientes
quando se deseja reduzir o espaço de busca e também como um algoritmo de busca local
heurístico pode resolver problemas complexos em poucas etapas de busca a solução. Também
é didático pela forma com que foi programada, ou seja, idêntica a literatura, o que facilita o
entendimento e compreensão.
Como limitações mais importantes, podem-se citar o uso de heurísticas combinadas, ou
57
seja, combinar a heurística de variável mais restritiva com a heurística de conflitos mínimos, o
tempo de processamento das heurísticas combinada com a do algoritmo serem maiores do que
só o algoritmo e as heurísticas não terem visão em mais de um nível da árvore de resolução,
onde poderia ser detectado problemas futuros e não criar ramificações por aquele valor do
domínio que sempre dará a impossibilidade do CSP ser consistente.
4.1 EXTENSÕES
Como extensão mais importante de trabalhos futuros, pode-se citar a implementação
de mais heurísticas como a de consistência de arcos, uma depuração detalhada dos algoritmos
e a implementação de um algoritmo de ordenação nas heurísticas, para obter um tempo
melhor na resolução do CSP quando aplicado as heurísticas. Pois como Russell e Norvig
(2004, p. 140) salientam, se levar em conta o tempo gasto com o algoritmo mais o tempo e o
custo extra para calcular as heurísticas, o tempo total poderá ser maior que simplesmente o
algoritmo busca-com-retrocesso, e que este custo pode ser gerenciado com os métodos de
verificação prévia das variáveis, com a consistência de arcos e propagação de restrições.
58
REFERÊNCIAS BIBLIOGRÁFICAS
CAMPOS, P. G. Resolução de problemas por meio de resolução de restrições. Recife,
[2003]. Disponível em: <http://www.cin.ufpe.br/~in1006/2003/CSP.ppt>. Acesso em: 20 set.
2006.
DIAS, D. The Gnu Prolog web site. France, 2003. Disponível em: <http://gnuprolog.inria.fr/>. Acesso em: 8 abr. 2006.
CARVALHO FILHO, E. C. B. et al. Constraint satisfaction problems. Recife, [1998?].
Disponível em: <http://www.cin.ufpe.br/~compint/aulas-IAS/csp.ppt>. Acesso em: 10 abr.
2006.
RICH, E.; KNIGHT, K. Inteligência artificial. Tradução Maria Cláudia Santos Ribeiro
Ratto. São Paulo: Makron, 1993.
RUSSELL, S. J.; NORVIG, P. Inteligência artificial. Tradução PubliCare Consultoria. Rio
de Janeiro: Elsevier, 2004.
SANTOS, F. Implementação distribuída do algoritmo Adopt. 2005. 115 f. Trabalho de
Conclusão de Curso (Bacharelado em Ciências da Computação) – Centro de Ciências Exatas
e Naturais, Universidade Regional de Blumenau, Blumenau.
_______. ccb_short_guide.pdf. Blumenau, 2006. 1 arquivo (98 Kbytes). Adobe Acrobat
Reader 7. Disponível em:
<http://www.inf.furb.br/gia/dynDCSP/doc/ccb/ccb_short_guide.pdf>. Acesso em: 9 abr.
2006.
TRALAMAZZA, D. M. Desenvolvimento de um algoritmo para problema de satisfação
de restrição distribuída. 2004. 37 f. Trabalho de Conclusão de Curso (Bacharelado em
Ciências da Computação) – Centro de Ciências Exatas e Naturais, Universidade Regional de
Blumenau, Blumenau.
TSANG, E. Foundations of constraint satisfaction. London: Academic Press, 1993.