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