TRABALHO DE RECUPERAÇÃO

TRABALHO DE RECUPERAÇÃO

O clássico problema Missionários e Canibais que pode ser assim definido:

Na margem esquerda de um rio 3 missionários e 3 canibais desejam atravessar o rio usando um bote já ancorado nesta margem. Entretanto as seguintes restrições devem ser obedecidas:

• o bote pode carregar no máximo 2 pessoas;

• tanto os missionários como os canibais podem conduzir o bote;

• nunca pode existir mais canibais do que missionários em qualquer das 2 margens do rio, caso contrário os missionários serão imediatamente devorados pelos canibais.

O problema consiste em efetuar a passagem das 6 pessoas da margem esquerda para a margem direita do rio sem que nenhum missionário seja devorado.

a) Mostre que são necessárias no mínimo 11 viagens para resolver esse problema e que existem 4 soluções com esse no de viagens. Mostre quais são essas 4 soluções.

b) Resolva manualmente esse problema usando o algoritmo A* (mostre graficamente as expansões realizadas).

Dicas:

a) Codifique cada movimento como a operação MOVE(x,y,z), onde:

x = número de Missionários sendo transportados,

y = número de Canibais sendo transportados,

z = E ou D (E = destino margem esquerda do rio, D = destino margem direita do rio).

b) Codifique o estado usando ME(me,ce,be), onde:

me = no de Missionários na margem esquerda,

ce = no de Canibais na margem esquerda,

be = 1 ou 0, indicando se o bote está ou não na margem esquerda.

Portanto:

Codificação do Estado Inicial: ME(3,3,1),

Codificação do Estado Final desejado: ME(0,0,0).

Exemplo: aplicando a operação MOVE(0,2,D) no Estado Inicial, obtemos o estado ME(3,1,0).

c) Use como heurística de busca no diagrama de estados (critério quantitativo para seleção do próximo estado a ser expandido) uma estimativa da quantidade de trabalho que deve ainda ser realizado para o estado analisado (p. ex., use o no de pessoas na margem esquerda como indicativo do no de viagens que precisam ser realizadas).

d) Teste as suas soluções usando a web page:

http://www.learn4good.com/games/puzzle/boat.htm