Redux da coloração de mapas

Esta seção reconsidera o problema de coloração do mapa da Seção 2.1. Desta vez, devemos representar as regiões adjacentes usando uma lista de regiões vizinhas, e não necessariamente armazenar o mapa explicitamente usando os dados do programa. Por exemplo, o mapa na Seção 2.1 poderia ser representado com a seguinte representação de lista de adjacência

[[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[3,4],[4,5]]

A intenção é criar um programa para colorir o mapa que possa ser usado da seguinte forma:

 
?- color([[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[3,4],[4,5]], 
                  [red,green,blue,yellow],Coloring). 
Coloring = [[5,red],[4,green],[3,red],[1,blue],[2,yellow]] ; ...   /* 48 solutions */

Observe que aqui, por exemplo, 1 e 3 são adjacentes porque [1,3] pertence à lista, mas 3 é adjacente a 1 pelo mesmo motivo. Podemos calcular a relação de adjacência geralmente usando a seguinte definição.

 
adjacent(X,Y,Map) :-  member([X,Y],Map) ; member([Y,X],Map).

Observe a disjunção, ';', na cláusula. 'X' e 'Y' representam nomes de regiões e 'Map' é uma lista de adjacências. O predicado 'member' foi definido na última seção 2.7.

Observe ainda que uma lista de adjacências pode ser usada para definir o mapa, desde que cada região seja adjacente a pelo menos uma outra região (não regiões desconectadas). Portanto, pode-se calcular uma lista de nomes de regiões, dada a lista de adjacências. Aqui está uma definição do Prolog para isso.

find_regions([],R,R). 
find_regions([[X,Y]|S], R,A) :- 
     (member(X,R) ->  
        (member(Y,R) -> find_regions(S,R,A) ; find_regions(S,[Y|R],A)) ; 
           (member(Y,R) -> find_regions(S,[X|R],A) ; find_regions(S,[X,Y|R],A) ) ).

Esta é a forma de implicação do Prolog mais complicada até agora. Passe algum tempo entendendo o que ele diz antes de prosseguir. Por exemplo,

 
?- find_regions([[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[3,4],[4,5]],[],R). 
R = [5,4,3,1,2]

Preste atenção especial ao uso do parâmetro de acumulação (o segundo parâmetro).

Agora, dada a lista de adjacências e uma lista de cores, deve-se ser capaz de calcular as cores adequadas -- ou seja, as cores em que as regiões adjacentes têm cores diferentes. Em outras palavras, afirmado de cima para baixo, a intenção é colorir o mapa calculando primeiro as regiões da lista de adjacências, depois colorir o mapa e depois verificar se a coloração não está em conflito. Retratado com uma árvore, temos

Fig. 2.9

A árvore mostra a decomposição lógica de cima para baixo pretendida para o design do programa. Posteriormente, com os valores preenchidos para as variáveis, ela poderia se tornar uma árvore de cláusulas justificando alguma consequência particular do programa.

 
color(Map,Colors,Coloring) :-
        find_regions(Map,[],Regions), 
        color_all(Regions,Colors,Coloring), 
        \+ conflict(Map,Coloring). 
 
color_all([R|Rs],Colors,[[R,C]|A]) :- 
        member(C,Colors), 
        color_all(Rs,Colors,A). 
color_all([],_,[]). 
 
 
conflict(Map,Coloring) :- 
        member([R1,C],Coloring), 
        member([R2,C],Coloring), 
        adjacent(R1,R2,Map).

É muito importante perceber onde o programa em execução faz as escolhas de coloração. Basicamente, isso acontece na primeira cláusula de definição de 'color_all', e as escolhas são determinadas por 'member'. Ao retroceder(backtracking) em 'member', escolhe-se outra cor.

Exercício 2.9 O programa é um tanto ineficiente porque espera até depois de ter colorido um mapa completamente antes de determinar se há um conflito na coloração. Modifique o programa para que suas cores e verificações contra conflito simultaneamente (antes de continuar a colorir mais regiões). Teste o programa modificado e o original em um mapa dos Estados Unidos.

Veja Também

• Código do Prolog para esta seção.
• 2.1 Coloração de mapas
• 2.7 Listas em Prolog
• 2.10 I/O Simples em Prolog
• Prolog Tutorial Sumário