Folha 6
Colorir Mapas
Pretende-se colorir mapas de países, com um número mínimo de cores e
sem que cores iguais sejam utilizadas em países vizinhos.
São considerados países vizinhos os que tiverem, pelo menos, uma linha
de fronteira comum (caso dos países 1 e 2) ou até um ponto de
fronteira comum (caso dos países 2 e 3).
O mapa é modelado através de uma lista, tendo um elemento por cada
país do mapa.
O elemento correspondente a um país representa os países vizinhos
desse pais.
Por exemplo, o país 1, sendo o primeiro elemento da lista, tem como
vizinhos os países 2, 3 e 4.
(define mapal
'((2 3 4) ; pais 1
(1 3 4 5 7) ; pais 2
(1 6 7 2 4) ; pais 3
(l 7 6 2 3 5) ; pais 4
(7 2 4) ; pais 5
(3 4 7) ; pais 6
(2 3 4 5 6 8) ; pais 7
(7))) ; pais 8
A modelação das cores pode também ser feita através de uma lista
(define paleta-cores
'(C1 C2 C3 C4)) ; neste caso, utilizam-se 4 cores
A atribuição de cores aos vários paises é conseguida com uma chamada a
colorir-mapa, procedimento que espera dois argumentos, ou
seja, duas listas, uma que representa o mapa e outra o conjunto de
cores utilizadas para colorir o mapa.
Este procedimento devolve uma lista com a indicação das cores a
atribuir a cada país, a começar pelo pais 1.
=> (colorir-mapa mapal paleta-cores)
(c1 c2 c3 c4 c3 c2 c1 c2)
Uma tentativa de colorir o mapa com um conjunto de apenas três cores:
=> (colorir-mapa mapal '(cl c2 c3))
nao ha' solucao...
1. Fazer uma abordagem de-cima-para-baixo ao programa
colorir-mapa.
2. Escrever em Scheme o procedimento colorir-mapa,
com base nos resultados da abordagem anterior.
Sugestão de abordagem
A tarefa colorir-mapa pode desenvolver-se como se fosse a tarefa
procura-solucao que, para além de tomar um mapa com os países
para colorir e uma paleta de cores, tem ainda em consideração, como é
natural, uma solução de cores que vai criando. Uma solução começa
vazia e vai crescendo à medida que se encontra uma boa cor para cada
um dos países.
Sendo assim, podemos imaginar as seguintes tarefas de
procura-solucao:
-
Enquanto há países no mapa para colorir, toma a primeira cor da
paleta e verifica se é uma boa cor para o primeiro país do mapa.
Uma cor será boa para atribuir a um país se nenhum dos países
vizinhos, já com cor atribuída, a utiliza.
Sendo uma boa cor, constituirá mais uma cor da solução que se procura,
retira-se o país correspondente do mapa dos países a colorir, e
retoma-se novamente a tarefa procura-solucao com a paleta com
todas as cores.
Sendo uma má cor, também se retoma procura-solucao, mas sem
juntar nada à solução, sem retirar qualquer país do mapa, e reduzindo
a paleta retirando-lhe a cor referida.
-
E se se atingir o fim da paleta, sem encontrar uma boa cor?
Ou, de facto, não há solução possível, ou alguma das escolhas não foi
bem feita.
Assim, recua-se para a solução anterior e, a partir da cor na
altura escolhida, procura-se uma nova cor e o processo prossegue.
É claro que se tiver de recuar tanto que a solução fica vazia, então é
porque não há mesmo solução possível.
-
A tarefa procura-solucao termina com solução, quando não
houver mais países no mapa para colorir.
Da descrição anterior ainda se identificam algumas sub-tarefas:
-
Recuar na solução, uma tarefa que implica abandonar a última cor
escolhida, retomando procura-solucao com a solução e com o
mapa na situação anterior e com a paleta a partir da cor a rejeitar.
Aqui identificam-se outras sub-tarefas, mapa-anterior,
solucao-anterior e as-outras-cores a partir da cor
rejeitada.
-
Determinar se uma cor é boa para um país, uma tarefa que implica
verificar se nenhum dos países vizinhos já com cor atribuída, tem a
cor em análise.