Exemplo_Missionarios-canibais

Prévia do material em texto

Inteligência Artificial 
João Luís Tavares da Silva 
Exemplo de representação do 
Problema “Canibais e 
Missionários” 
Problemas 
• Três canibais e três missionários estão viajando juntos e 
chegam à margem de um rio. Eles desejam atravessar para a 
outra margem para, desta forma, continuar a viagem. O único 
meio de transporte disponível é um barco que comporta no 
máximo duas pessoas. Há uma outra dificuldade: em nenhum 
momento o número de canibais pode ser superior ao número 
de missionários pois desta forma os missionários estariam em 
grande perigo de vida. Como administrar a travessia? 
Espaço de Estados 
• Podemos representar os estados por um par ordenado (c,m) 
•  c = representa o número de canibais (0 ≤ c ≥ 3) 
• m = representa o número de missionários (0 ≤ m ≥ 3) 
• Teremos 16 (24) estados possíveis já que existem duas 
variáveis (c,m) com 4 valores possíveis para cada uma (0 à 3) 
•  Estes estados vão de (0,0) à (3,3) 
Espaço de Estados 
• Também podemos representar a margem onde (c,m) se 
encontram através do complemento dos pares ordenados: 
•  (0,0) na margem esquerda e, portanto (3,3) na margem direita 
•  (0,1) na margem esquerda e, portanto (3,2) na margem direita 
•  E assim, sucesivamente… 
Estados Viáveis 
• Com esta representação (c,m), não é difícil testar os estados 
não viáveis, ou seja, os que restringem que o número de 
canibais exceda o número de missionários. 
• Os pares ordenados que representam os estados não viáveis: 
•  {(2,1);(3,1);(3,2) - (1,2);(0,2);(0,1)} 
Condições de Travessia 
• Se o barco comporta no máximo 2 pessoas, há 5 possíveis 
situações em cada travessia: 
•  Levar 1 canibal → (1,0) 
•  Levar 2 canibais; → (2,0) 
•  Levar 1 missionário; → (0,1) 
•  Levar 2 missionários; → (0,2) 
•  Levar 1 canibal e 1 missionário. → (1,1) 
Usando	a	forma	(cm),	onde	“c”	é	o	número	de		
Canibais	e	“m”,	o	número	de	missionários,	que		
serão	atravessados,	temos	as	seguintes	ações:	
Pré-condições 
• Em cada uma destas ações, testar se existem indivíduos 
suficientes para transportar 
•  (1,0) → C ≥ 1 
•  (2,0) → C ≥ 2 
•  (0,1) → M ≥ 1 
•  (0,2) → M ≥ 2 
•  (1,1) → C ≥ 1 e M ≥ 1 
Pré-condições 
• Em cada uma destas ações, testar para garantir que tem mais 
Missionários do que Canibais: 
•  (1,0) → (3-M)-(3-C) ≥ 1 
•  (2,0) → (3-M)-(3-C) ≥ 2 
•  (0,1) → (3-C)-(3-M) ≥ 1 
•  (0,2) → (3-C)-(3-M) ≥ 2 
•  (1,1) → (3-C) ≤ (3-M) 
Efeitos das Ações 
• Em cada uma destas ações, é preciso calcular o efeito (pós-
condições) que cada uma tem nos estados objetivos: 
• Considerando que x é a margem de origem e y a de destino: 
•  (1,0) → Cy = (3 - Cx) + 1 e My = (3 - Mx) 
•  (2,0) → Cy = (3 - Cx) + 2 e My = (3 - Mx) 
•  (0,1) → My = (3 - Mx) + 1 e Cy = (3 - Cx) 
•  (0,2) → My = (3 - Mx) + 2 e Cy = (3 - Cx) 
•  (1,1) → Cy = (3 - Cx) + 1 e My = (3 - Mx) + 1 
Espaço de Estados 
• O Grafo a seguir exemplifica como seria o espaço de espaços total, 
caso o teste de restrição fosse apenas nos estados de origem do 
movimento, por exemplo: 
•  Os círculos em azul representam a margem esquerda; 
•  Os círculos em vermelho representam a margem direita; 
•  Os círculos hachurados em laranja representam estados não viáveis; 
•  Considerando o estado inicial (3,3) na margem esquerda e a ação (0,1), 
mover um missionário da esquerda para a direita, o teste de restrição seria: 
•  (3-M)-(3-C) ≥ 1 
•  (3-3)-(3-3) ≥ 1 
•  0 ≥ 1, ou seja, o movimento é não viável 
pois deixa 3 canibais com 1 Missionário 
na margem de origem 
3,3 
0,1 
0,1 
Espaço de Estados Parcial 
• Vamos considerar 3M e 3C na margem esquerda (≥ 1): 
• Como definimos x e y no início do Exemplo, podemos definir: 
•  Estado inicial = (3,3) na margem esquerda ou x=(3,3) 
•  Estado Final = (3,3) na margem direita ou y=(3,3) 
3 ,3 
Espaço de Estados Parcial 
• Cada uma das 5 ações gera uma aresta para um novo estado: 
• Os estados origem são as quantidades resultantes de C e M na 
margem oposta (vermelho) 
3,3 
1,0 
1 ,0 2 ,0 0 ,1 0 ,2 1 ,1 
2,0 0,1 0,2 1,1 
3C	e	3M	na	margem	Esq	
1C	e	0M	na	margem	Dir	
Mover	1C	da	Esq	para	a	Dir	
Estados	não	viáveis,	pois	deixam	
C	>	M	na	origem	
• Ações que retornam para o estado original estão com as setas 
em azul: 
• O próximo slide exibe o grafo total. 
Espaço de Estados Parcial 
3,3 
1,0 
1 ,0 2 ,0 0 ,1 0 ,2 1 ,1 
2,0 0,1 0,2 1,1 
1,0 
2,0 
1,1 
Esta	aresta	representa	o	retorno	
De	1C	e	1M	para	a	margem	origem	
Espaço de Estados Total 
3,3 
1,0 
1,0 2,0 0,1 0,2 1,1 
2,0 0,1 0,2 1,1 
1,0 
10 
1,0 
2,3 3,2 
1,0 
2,0 
1,1 
1,0 
3,0 1,2 2,1 
2,0 
0,1 
0,2 1,1 
2,0 
1,3 
1,0 
1,1 
2,2 0,2 
1,0 
0,2 
1,1 
2,1 3,1 1,2 2,2 
2,0 0,1 1,0 
3,1 2,1 
1,1 0,1 2,0 
0,2 
2,1 3,1 1,2 1,3 
2,0 0,1 1,0 
1,1 
1,0 
2,1 3,0 
0,2 
0,1 
2,3 
2,0 
1,0 
1,0 
1,2 
 
2,1 
 
1,1 2,0 
1,1 0,1 
0,2 
2,0 
3,3 
2,0 1,1