Mission Rios E Canibais

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º