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º