Missionários e Canibais

Prévia do material em texto

Clique para editar o estilo do título mestre
Clique para editar o estilo do subtítulo mestre
*
*
*
Missionários e Canibais
Estratégias de Busca
Bruno Kinder Almentero
Yura Carvalho Ferreira
*
*
*
Descrição do Problema
O problema é bastante popular na literatura pois foi assunto do primeiro artigo a tratar de formulação de problemas de busca de forma analítica. 
Pode ser formulado de várias maneiras
*
*
*
Descrição do Problema
 Três missionários e três canibais estão às margens de um rio. Na mesma margem existe um bote com capacidade para no máximo duas pessoas.
 O problema é o de encontrar uma forma de levar as 6 pessoas para a outra margem do rio, sem nunca deixar numa margem um número maior de canibais do que de missionários. 
*
*
*
Busca em Largura 
Expande primeiro todos os nós de um nível antes de avançar para o próximo
É ótima e completa 
Armazena todos os nós
*
*
*
Busca em Profundidade
Expande primeiro todos os nós de um caminho
Não é ótimo nem completo
Armazena somente os nós do caminho
*
*
*
Busca Limitada em Profundidade
BP com um limite máximo de profundidade
É completo se a profundidade máxima for maior ou igual ao nível da solução.
Não é ótimo
Armazena somente os nós do caminho.
*
*
*
Busca em Profundidade Iterativa
Combinação de BP com Busca Limitada em Profundidade
É completa e ótima.
Armazena somente os nós do caminho
*
*
*
Busca A*
Utilizada o custo real mais uma função heurística
É completa e ótima 
Armazena todos os nós
*
*
*
Modelagem
Um estado tem a seguinte forma: (m, c, b), onde m é o número de missionários na margem de origem, c é o número de canibais na mesma margem e se b = 1 indica que o barco está na margem de origem, se b = 0 indica que o barco está na margem oposta.
Um nó possui um estado, um nível, uma heurística e um ponteiro para o seu pai. 
*
*
*
Modelagem
Os operadores do problema são:
mover 1 missionário
mover 1 canibal 
mover 2 missionários
mover 2 canibais
mover 1 missionário e 1 canibal
Dessa maneira o nosso estado inicial será (3, 3, 1) e aplicando-se os operadores e descartando os estados inválidos ( nº canibais > nº missionários em uma mesma margem) devemos chegar a solução (0, 0, 0).
*
*
*
Implementação
Neste problema especificamente, estados repetidos são gerados freqüentemente e para evitar que a busca em Profundidade entre em “loop”, não visitamos estados repetidos. 
A busca Limitada em Profundidade e a busca em Profundidade Iterativa são análogas à busca em Profundidade. A única diferença é que não precisamos testar os estados repetidos já que impomos um limite máximo de profundidade. 
 
*
*
*
Implementação
Todos as buscas são implementadas em uma mesma função (função busca) e a busca Iterativa nada mais é que um loop que chama a busca em Profundidade para cada limite até que a solução seja encontrada.
*
*
*
Heurística A*
 Número de missionários na margem destino é uma boa heurística?
 A heurística escolhida foi o número de Missionários na margem de origem. Por que?
A heurística é admissível? Pode decrescer?
*
*
*
Heurística A*
Margem RIO Margem
Origem Destino 
(2 , 3 , 1) (1, 0 , 0)
(1, 1, 0) (2, 2, 1)
*
*
*
Resultados
Máquina: AMD –750 Mhz, 640MB RAM e Sistema Operacional Windows XP 
*
*
*
Resultados
Para finalizar salientamos que estes dados gerados como resultado foram muito importantes para avaliarmos a corretude do algoritmo. 
Isso foi conseguido pois examinando os dados e verificando informações incoerentes, permitiu uma gradativa correção do algoritmo até se encontrar a solução certa e livre de erros 
*
*
*
Conclusões
Todos os algoritmos acham a solução, a única exceção é a busca em profundidade limitada que só encontra a solução se a profundidade máxima for maior que o nível da solução mais rasa.
Basicamente a diferença entre os algoritmos implementados é a ordenação da lista que armazena os nós que deverão ser expandidos.