Hill-Climbing Problema das 8-rainhas
Autoras: Katti Faceli e Myrian Renata Barros Araujo
Descrição do proplema:
O objetivo do problema é colocar 8 rainhas em um tabuleiro de
forma que nenhuma rainha ataque outra. (Uma rainha ataca outra se esta
estiver na diagonal e/ou horizontal e/ou vertical). Este tipo de problema,
pertence a classe dos casos em que dado um estado inicial a solução
consiste em encontrar uma melhor configuração final, mesmo
que esta não seja a mais satisfatória. Exemplificando, dado
um estado inicial. As Figuras 1 e 2 mostram uma possível configuração
inicial e final do tabuleiro.
Uma solução satisfatória poderia ser:
Descrição da resolução:
Foram desenvolvidas duas versões para o problema, as quais diferem
basicamente pela forma de movimentação das peças no
tabuleiro:
-
Versão 1: movimenta uma rainha qualquer da sua posição
original para uma nova posição cuja coluna não contenha
outra rainha;
-
Vantagens:
-
é mais genérico pois permite que seja dada qualquer configuração
inicial das rainhas no tabuleiro;
-
encontra alguma solução para qualquer estado inicial;
-
Desvantagens:
-
maior custo computacional pois é mais complexo;
-
a execução é um mais lenta que a outra versão;
-
implementação mais complexa que a outra versão;
-
gera mais estados na fase de expansão de um nó, consumindo
grande quantidade de memória (pilha);
-
Versão 2: movimenta uma rainha para uma outra posição
na mesma coluna
-
Vantagens:
-
menor custo computacional pois é mais restrito;
-
a execução é mais rápida;
-
implementação mais simples;
-
gera menos estados na fase de expansão de um nó, consumindo
menos quantidade de memória (pilha) do que a versão anterior;
-
Desvantagens:
-
exige que a configuração inicial seja específica (deve
ser colocada uma rainha em cada coluna);
-
não encontra resposta satisfatória para casos que a configuração
inicial não é a esperada.
Formalização do problema usando o Formalismo Espaço
de Estados
Para a resolução do problema foram criados duas versões,
estas se diferenciam por alguns aspectos:
-
As configurações inicias (ou os estados iniciais) e
-
a forma de movimentação das rainhas no tabuleiro.
Considerações iniciais
-
Estado
-
Representação - lista de pares ordenados que representam
as posições de cada rainha no tabuleiro;
-
Versão 1: arranjo de 8 rainhas no tabuleiro de modo aleatório.
Por exemplo: [(L1,C1),(L2,C2),(L3,C3),(L4,C4),(L5,C5),(L6,C6),(L7,C7),(L8,C8)];
-
Versão 2: arranjo de 8 rainhas no tabuleiro, uma em cada coluna.
Por exemplo: [(L1,1),(L2,2),(L3,3),(L4,4),(L5,5),(L6,6),(L7,7),(L8,8)];
-
Estado inicial
-
Múltiplos estados: qualquer estado permitido, em cada versão;
-
Estado final
-
Múltiplos estados: qualquer estado permitido que possui a característica
de não haver ataque entre as rainhas;
operador
-
O operador mover / 3 retorna a heurística referente ao novo estado;
-
Versão 1: mover(Estado0, Estado1, Heurística);
% Dado um estado Est0, retorna em Est1 um estado correspondente a movimentação
de uma rainha
% a partir do estado Est0
mover(Est0, Est1, H) :-
permitido(R),
not(elem(R, Est0)),
troca(R1, R, Est0, Est1),
coluna_diferente(R, Est1),
heuristica_2(Est1, H).
% Permite a troca de posicao de dois elementos em uma lista
troca(R1, R2, [R1| Resto], [R2| Resto]).
troca(R1, R2, [R3| Resto1], [R3| Resto2]) :-
troca(R1, R2, Resto1, Resto2).
% Determina a area permitida para a movimentacao das pecas (tamanho
do tabuleiro)
permitido((L, C)) :-
entre(L, 1, 8),
entre(C, 1, 8).
% Determina se uma rainha esta em uma coluna diferente de todas as demais
coluna_diferente((L, C), []).
coluna_diferente((L, C), [(L, C)|Outras]):-
!,
coluna_diferente((L, C),
Outras).
coluna_diferente((L, C),
[(L1, C1)|Outras]):-
C \= C1,
coluna_diferente((L, C),
Outras).
% Predicado que verifica se um valor esta entre dois outros, permitindo
instanciar
% este valor caso ele nao esteja instanciado
entre(_, Min, Max) :-
Min > Max,
!,
fail.
entre(X, X, _).
entre(X, Min, Max) :-
ProxMin is Min + 1,
entre(X, ProxMin, Max).
% Verifica se exite um elemento em uma lista
elem(X, [X| _]).
elem(X, [_| Xs]) :-
elem(X, Xs).
-
Versão 2: mover(Estado1, Estado2, Heurística);
-
% Permite a troca de posicao de dois elementos em uma lista
troca(R1, R2, [R1| Resto], [R2| Resto]).
troca(R1, R2, [R3| Resto1], [R3| Resto2]) :-
troca(R1, R2, Resto1,
Resto2).
% Dado um estado Est0, retorna em Est1 um estado correspondente
a movimentação de uma rainha
% a partir do estado Est0
mover(Est0, Est1, H) :-
entre(NovaLinha, 1, 8),
troca((L, C), (NovaLinha, C), Est0, Est1),
L \= NovaLinha,
heuristica_1(Est1, H).
% Predicado que verifica se um valor esta entre dois outros, permitindo
instanciar
% este valor caso ele nao esteja instanciado
entre(_, Min, Max) :-
Min > Max,
!,
fail.
entre(X, X, _).
entre(X, Min, Max) :-
ProxMin is Min + 1,
entre(X, ProxMin, Max).
-
Custo do caminho
-
Zero, uma vez que o tipo de solução é o estado meta.
Algoritmo de busca: Hill-Climbing
O algoritmo Hill-Climbing é classificado como Algoritmo de Melhorias
Iterativas, e é utilizado para a resolução de problemas,
cuja descrição do estado contém toda a informação
necessária para a solução, ou seja, o caminho até
a solução é irrelevante. É interessante notar
também que este algoritmo mantém somente um estado (o mais
promissor) na memória.
Devido as características acima a solução encontrada
nem sempre é a solução ótima, uma vez que o
algoritmo pode encontrar um máximo (ou mínimo) local, encerrando
a busca.
O código a seguir exibe a implementação do algoritmo
Hill-Climbing utilizado.
-
% Implementa busca informada - Algoritmo Hill Climbing
hill(I, F):-
heuristica_1(I, H1),
findall((H, Est), (mover(I, Est, H), H <
H1), Lista_Est),
minimo_lista1(Lista_Est, (H2, ProxEst)),
H1 > H2,
!,
hill(ProxEst, F).
hill(I, I).
% Retorna o estado que tem a menor heuristica
minimo_lista1([L|Lc], Min):-
min_l1(Lc, L, Min).
% Complemento do predicado minimo_lista1
min_l1([], Min, Min).
min_l1([L|Lc], MinAtual, Min):-
maior1(L, MinAtual),
!,
min_l1(Lc, MinAtual, Min).
min_l1([L|Lc], MinAtual, Min):-
min_l1(Lc, L, Min).
% Verifica qual heuristica eh maior
maior1((H, _), (H1, _)):-
H > H1.
Para este problema, em particular, foram utilizadas duas heurísticas:
heuristica_1(Estado, Heuristica): a partir de um estado, esta heurística
irá fornecer o número de rainhas que atacam uma (ou mais)
rainha(s). Por exemplo: no estado representado na figura1 a heurística
é 8, pois todas as rainhas atacam.
% Heuristica_1: retorna o numero de rainhas que atacam
heuristica_1(Est, H):-
quantasAtacam(Est, Est, 0, H).
% Conta o numero de rainhas que atacam alguma outra rainha
quantasAtacam([], _, N, N).
quantasAtacam([R|Outras], Est, Ac, N):-
ataca(R, Est, D),
Ac1 is Ac + D,
quantasAtacam(Outras, Est, Ac1, N).
% Determina se uma rainha ataca (1) ou nao (0)
ataca(R, Est, 0):-
nao_ataca(R, Est),
!.
ataca(_, _, 1).
% Verifica se uma rainha nao ataca todas as outras do tabuleiro
nao_ataca(_,[]).
nao_ataca(R, [R|Outras]):-
!,
nao_ataca(R, Outras).
nao_ataca((L,C),[(L1,C1)|Outras]):-
L \= L1,
C \= C1,
T is C1-C,
T2 is L1-L,
T \= T2,
T3 is L-L1,
T \= T3,
nao_ataca((L,C),Outras).
heuristica_2(Estado, Heuristica): a partir de um estado, esta heurística
irá fornecer o número total de ataques entre as rainhas.
Por exemplo: no estado representado na figura1 a heurística é
22 ataques, no total, entre as rainhas.
% Heuristica_2: retorna o total de ataques entre todas as rainhas
heuristica_2(Est, H):-
contaAtaques(Est, Est, 0, H).
% Conta o total de ataques entre todas as rainhas
contaAtaques([], _, N, N).
contaAtaques([R|Outras], Est, Ac, N):-
conta(R, Est, 0, D),
!,
Ac1 is Ac + D,
contaAtaques(Outras, Est, Ac1, N).
conta(_, [], N, N).
conta(R, [R1|Outras], Ac, N):-
((R \= R1, ataca1(R, R1), Ac1 is Ac + 1); Ac1
is Ac),
!,
conta(R, Outras, Ac1, N).
ataca1((L,C),(L1,C1)):-
L = L1.
ataca1((L,C),(L1,C1)):-
C = C1.
ataca1((L,C),(L1,C1)):-
T is C1-C,
((T2 is L1-L, T = T2);
(T3 is L-L1, T = T3)).
Heurística 1 X Heurística 2
A heurística 1 efetua uma contagem do número de rainhas
que atacam alguma outra rainha. Isto é feito da seguinte maneira:
para cada rainha R de um dado estado é feita uma busca neste estado
até que seja encontrada uma outra rainha que seja atacada pela rainha
R. Se nesta busca foi encontrada uma rainha atacada incrementa-se o número
de rainhas que atacam (rainha R ataca alguma outra rainha).
A heurístcia 2 efetua uma contagem do número total de
ataques entre todas as rainhas. Isto é feito da seguinte maneira:
para cada rainha R de um dado estado é feita uma contagem do número
de outras rainhas que ela ataca. Este número é então
somado ao total de ataques.
A vantagem da heurística 1 em relação a heurística
2 é que ela é mais rápida, não precisa percorrer
todo o estado. Além disso a heurística 1 gera menos estados
na expansão do nó do que a heurística 2.
Com relação a obtenção de soluções,
a heurística 2 fornece soluções mais próximas
da ótima para um maior número de configurações
iniciais do que a heurística 1.
Análise das propriedades do algoritmo em face do problema
particular e das heurísticas
Dependendo do estado inicial e da heurística empregada o algoritmo
pode encontrar uma solução ótima (8 rainhas no tabuleiro
sem ataque entre elas), uma solução intermediária
(8 rainhas com algumas sem ataque) ou encontrar uma solução
ruim (8 rainhas atacando).
O problema do Hill-Climbing é justamente este, pode ser que ele
não encontre a solução que se espera.
Uma vantagem do algoritmo é que este não consome muita
memória pois não armazena todos os nós expandidos,
apenas o nó que melhora o estado atual (o nó que possue melhor
heurística do que a do estado atual).
Uma característica desta implementação é
que é feita uma otimização em que os estados promissores
que não apresentam uma heurisita que melhore a atual não
chegam a entrar na lista de possiveis nós para expansão.
Isto representa uma economia de memória.
Execução - Casos de teste
Execução:
As várias versões foram compiladas e executadas no modo
DOS, devido as restrições de memória e tempo impostas
pelo interpretador Prolog. De posse do arquivo executável basta
digitar na linha de comando o nome do arquivo para executá-lo.
O programa principal foi estruturado da seguinte forma: em primeiro
lugar faz alguns testes pré-definidos e em seguida permite que o
usuário entre com alguns casos de teste. Para encerrar o programa
basta entrar com "stop".
Casos de teste:
Foram feitas execuções dos mesmos casos de teste para
cada versão e cada heurística.
Versão 1 - Heurística 1
rainhasv1h1
[(1 , 1),(4 , 2),(3 , 3),(1 , 4),(7 , 5),(3 , 6),(7 , 7),(5
, 8)] -> [(1 , 1), (6 , 2),(8 , 3),(3 , 4),(7 , 5),(4 , 6),(2 , 7),(5 ,
8)]
[(1 , 1),(2 , 2),(3 , 3),(4 , 4),(5 , 5),(6 , 6),(7 , 7),(8
, 8)] -> [(1 , 1), (2 , 2),(3 , 3),(4 , 4),(5 , 5),(6 , 6),(7 , 7),(8 ,
8)]
[(1 , 1),(1 , 2),(1 , 3),(1 , 4),(1 , 5),(1 , 6),(1 , 7),(1
, 8)] -> [(1 , 1), (6 , 2),(1 , 3),(1 , 4),(7 , 5),(5 , 6),(8 , 7),(2 ,
8)]
[(1 , 1),(2 , 1),(3 , 1),(4 , 1),(5 , 1),(6 , 1),(7 , 1),(8
, 1)] -> [(1 , 5), (2 , 1),(3 , 6),(4 , 4),(5 , 7),(6 , 1),(7 , 8),(8 ,
2)]
[(1 , 1),(2 , 2),(3 , 3),(4 , 4),(5 , 5),(6 , 6),(2 , 7),(1
, 8)] -> [(6 , 1), (2 , 2),(3 , 3),(7 , 4),(5 , 5),(4 , 6),(8 , 7),(1 ,
8)]
[(5 , 1),(4 , 2),(3 , 3),(2 , 4),(6 , 4),(5 , 5),(4 , 6),(7
, 3)] -> [(5 , 1), (7 , 2),(2 , 3),(3 , 5),(6 , 4),(1 , 6),(4 , 8),(8 ,
7)]
[(2 , 2),(3 , 3),(7 , 2),(6 , 3),(3 , 6),(2 , 7),(6 , 6),(7
, 7)] -> [(3 , 2), (1 , 3),(7 , 1),(8 , 5),(5 , 6),(2 , 7),(6 , 4),(4 ,
8)]
[(1 , 1),(6 , 2),(8 , 3),(3 , 4),(7 , 5),(4 , 6),(2 , 7),(5
, 8)] -> [(1 , 1), (6 , 2),(8 , 3),(3 , 4),(7 , 5),(4 , 6),(2 , 7),(5 ,
8)]
Estado Inicial: [(2,2), (3,3), (7,2), (6,3), (3,6), (2,7),
(6,6), (7,7)].
Estado Final: [(3 , 2),(1 , 3),(7 , 1),(8 , 5),(5 , 6),(2
, 7),(6 , 4),(4 , 8)]
Estado Inicial: stop.
Versão 1 - Heurística 2
rainhasv1h2
[(1 , 1),(4 , 2),(3 , 3),(1 , 4),(7 , 5),(3 , 6),(7 , 7),(5 , 8)] ->
[(1 , 1), (4 , 2),(6 , 3),(3 , 4),(7 , 5),(2 , 6),(8 , 7),(5 , 8)]
[(1 , 1),(2 , 2),(3 , 3),(4 , 4),(5 , 5),(6 , 6),(7 , 7),(8 , 8)] ->
[(6 , 1), (3 , 2),(6 , 3),(4 , 4),(1 , 5),(8 , 6),(5 , 7),(7 , 8)]
[(1 , 1),(1 , 2),(1 , 3),(1 , 4),(1 , 5),(1 , 6),(1 , 7),(1 , 8)] ->
[(8 , 1), (6 , 2),(3 , 3),(1 , 4),(7 , 5),(5 , 6),(8 , 7),(2 , 8)]
[(1 , 1),(2 , 1),(3 , 1),(4 , 1),(5 , 1),(6 , 1),(7 , 1),(8 , 1)] ->
[(1 , 5), (2 , 1),(3 , 6),(4 , 4),(5 , 7),(6 , 1),(7 , 8),(8 , 2)]
[(1 , 1),(2 , 2),(3 , 3),(4 , 4),(5 , 5),(6 , 6),(2 , 7),(1 , 8)] ->
[(6 , 1), (3 , 2),(1 , 3),(7 , 4),(5 , 5),(8 , 6),(2 , 7),(4 , 8)]
[(5 , 1),(4 , 2),(3 , 3),(2 , 4),(6 , 4),(5 , 5),(4 , 6),(7 , 3)] ->
[(5 , 1), (7 , 2),(2 , 3),(4 , 8),(6 , 4),(3 , 5),(1 , 6),(8 , 7)]
[(2 , 2),(3 , 3),(7 , 2),(6 , 3),(3 , 6),(2 , 7),(6 , 6),(7 , 7)] ->
[(5 , 1), (4 , 3),(8 , 2),(3 , 5),(1 , 4),(2 , 7),(6 , 6),(7 , 8)]
[(1 , 1),(6 , 2),(8 , 3),(3 , 4),(7 , 5),(4 , 6),(2 , 7),(5 , 8)] ->
[(1 , 1), (6 , 2),(8 , 3),(3 , 4),(7 , 5),(4 , 6),(2 , 7),(5 , 8)]
Estado Inicial: [(2,2), (3,3), (7,2), (6,3), (3,6), (2,7), (6,6), (7,7)].
Estado Final: [(5 , 1),(4 , 3),(8 , 2),(3 , 5),(1 , 4),(2 , 7),(6 ,
6),(7 , 8)]
Estado Inicial: stop.
Versão 2 - Heurística 1
rainhasv2h1
[(1 , 1),(4 , 2),(3 , 3),(1 , 4),(7 , 5),(3 , 6),(7 , 7),(5 , 8)] ->
[(1 , 1), (6 , 2),(8 , 3),(3 , 4),(7 , 5),(4 , 6),(2 , 7),(5 , 8)]
[(1 , 1),(2 , 2),(3 , 3),(4 , 4),(5 , 5),(6 , 6),(7 , 7),(8 , 8)] ->
[(1 , 1), (2 , 2),(3 , 3),(4 , 4),(5 , 5),(6 , 6),(7 , 7),(8 , 8)]
[(1 , 1),(1 , 2),(1 , 3),(1 , 4),(1 , 5),(1 , 6),(1 , 7),(1 , 8)] ->
[(1 , 1), (6 , 2),(1 , 3),(1 , 4),(7 , 5),(5 , 6),(8 , 7),(2 , 8)]
[(1 , 1),(2 , 1),(3 , 1),(4 , 1),(5 , 1),(6 , 1),(7 , 1),(8 , 1)] ->
[(1 , 1), (2 , 1),(3 , 1),(4 , 1),(5 , 1),(6 , 1),(7 , 1),(8 , 1)]
[(1 , 1),(2 , 2),(3 , 3),(4 , 4),(5 , 5),(6 , 6),(2 , 7),(1 , 8)] ->
[(6 , 1), (2 , 2),(3 , 3),(7 , 4),(5 , 5),(4 , 6),(8 , 7),(1 , 8)]
[(5 , 1),(4 , 2),(3 , 3),(2 , 4),(6 , 4),(5 , 5),(4 , 6),(7 , 3)] ->
[(5 , 1), (4 , 2),(3 , 3),(2 , 4),(6 , 4),(8 , 5),(1 , 6),(7 , 3)]
[(2 , 2),(3 , 3),(7 , 2),(6 , 3),(3 , 6),(2 , 7),(6 , 6),(7 , 7)] ->
[(2 , 2), (3 , 3),(7 , 2),(6 , 3),(3 , 6),(2 , 7),(6 , 6),(7 , 7)]
[(1 , 1),(6 , 2),(8 , 3),(3 , 4),(7 , 5),(4 , 6),(2 , 7),(5 , 8)] ->
[(1 , 1), (6 , 2),(8 , 3),(3 , 4),(7 , 5),(4 , 6),(2 , 7),(5 , 8)]
Estado Inicial: [(2,2), (3,3), (7,2), (6,3), (3,6), (2,7), (6,6), (7,7)].
Estado Final: [(2 , 2),(3 , 3),(7 , 2),(6 , 3),(3 , 6),(2 , 7),(6 ,
6),(7 , 7)]
Estado Inicial: stop.
Versão 2 - Heurística 2
rainhasv2h2
[(1 , 1),(4 , 2),(3 , 3),(1 , 4),(7 , 5),(3 , 6),(7 , 7),(5 , 8)] ->
[(1 , 1), (4 , 2),(6 , 3),(3 , 4),(7 , 5),(2 , 6),(8 , 7),(5 , 8)]
[(1 , 1),(2 , 2),(3 , 3),(4 , 4),(5 , 5),(6 , 6),(7 , 7),(8 , 8)] ->
[(6 , 1), (3 , 2),(6 , 3),(4 , 4),(1 , 5),(8 , 6),(5 , 7),(7 , 8)]
[(1 , 1),(1 , 2),(1 , 3),(1 , 4),(1 , 5),(1 , 6),(1 , 7),(1 , 8)] ->
[(8 , 1), (6 , 2),(3 , 3),(1 , 4),(7 , 5),(5 , 6),(8 , 7),(2 , 8)]
[(1 , 1),(2 , 1),(3 , 1),(4 , 1),(5 , 1),(6 , 1),(7 , 1),(8 , 1)] ->
[(8 , 1), (8 , 1),(8 , 1),(8 , 1),(8 , 1),(8 , 1),(8 , 1),(8 , 1)]
[(1 , 1),(2 , 2),(3 , 3),(4 , 4),(5 , 5),(6 , 6),(2 , 7),(1 , 8)] ->
[(6 , 1), (3 , 2),(1 , 3),(7 , 4),(5 , 5),(8 , 6),(2 , 7),(4 , 8)]
[(5 , 1),(4 , 2),(3 , 3),(2 , 4),(6 , 4),(5 , 5),(4 , 6),(7 , 3)] ->
[(5 , 1), (3 , 2),(8 , 3),(6 , 4),(6 , 4),(4 , 5),(2 , 6),(8 , 3)]
[(2 , 2),(3 , 3),(7 , 2),(6 , 3),(3 , 6),(2 , 7),(6 , 6),(7 , 7)] ->
[(7 , 2), (3 , 3),(7 , 2),(3 , 3),(5 , 6),(8 , 7),(5 , 6),(8 , 7)]
[(1 , 1),(6 , 2),(8 , 3),(3 , 4),(7 , 5),(4 , 6),(2 , 7),(5 , 8)] ->
[(1 , 1), (6 , 2),(8 , 3),(3 , 4),(7 , 5),(4 , 6),(2 , 7),(5 , 8)]
Estado Inicial: [(2,2), (3,3), (7,2), (6,3), (3,6), (2,7), (6,6), (7,7)].
Estado Final: [(7 , 2),(3 , 3),(7 , 2),(3 , 3),(5 , 6),(8 , 7),(5 ,
6),(8 , 7)]
Estado Inicial: stop.
Versão 1 : Heurística1
e Heurística2 (roda
em Amzi 4.1)
Versão 2 : Heurística1
e
Heurística2 (roda
em Amzi 4.1)
Última Atualização [99/Apr/28 06:43]
por Katti Faceli e Myrian
Renata Barros Araujo