Problema dos canibais e missionários

O problema dos canibais e missionários e o intimamente relacionado problema dos maridos ciumentos, são clássicos quebra-cabeças de travessia de rio. O problema dos canibais e missionários é um bem conhecido problema brinquedo em inteligência artificial, onde ele foi usado por Saul Amarel como um exemplo de representação de problemas.

O Problema

Configuração inicial do problema dos canibais e missionários

No problema dos canibais e missionários, três missionários e três canibais devem atravessar um rio com um barco que pode transportar no máximo duas pessoas, sob a restrição de que, para ambas as margens, se há missionários presentes naquela margem, eles não podem ser ultrapassados pelo número de canibais na mesma margem (se fossem, os canibais comeriam os missionários.) O barco não pode atravessar o rio por si só, sem pessoas a bordo.

No problema dos maridos ciumentos, os missionários e os canibais se tornam três casais, com a restrição de que nenhuma mulher pode estar na presença de outro homem a não ser que seu marido também esteja presente. Sob esta restrição, não pode haver homens e mulheres presentes em uma margem com o número de mulheres superando o dos homens, pois se houvesse, haveria uma mulher sem a presença de seu marido. Portanto, ao se mudar mulheres por canibais e homens por missionários, qualquer solução para o problema dos maridos ciumentos também será uma solução para o problema dos missionários e canibais.

Solução

A primeira solução conhecida para o problema dos maridos ciumentos, utilizando-se 11 viagens de um só sentido, é a seguinte. Os casais são representados como $\alpha$ (marido) e a (mulher), $\beta$ e b, e $\gamma$ e c.

Viagem nº	Margem de saída	Viagem	Margem de chegada
(início)	$\alpha$a $\beta$b $\gamma$c
1	$\beta$b $\gamma$c	$\alpha$a →
2	$\beta$b $\gamma$c	←$\alpha$	a
3	$\alpha$ $\beta$ $\gamma$	bc →	a
4	$\alpha$ $\beta$ $\gamma$	← a	b c
5	$\alpha$a	$\beta$$\gamma$ →	b c
6	$\alpha$a	← $\beta$b	$\gamma$c
7	a b	$\alpha$$\beta$ →	$\gamma$c
8	a b	← c	$\alpha$ $\beta$ $\gamma$
9	b	a c →	$\alpha$ $\beta$ $\gamma$
10	b	← $\beta$	$\alpha$a $\gamma$c
11		$\beta$b →	$\alpha$a $\gamma$c
(fim)			$\alpha$a $\beta$b $\gamma$c

Esta é a mais curta solução para o problema, mas não é a única solução mais curta.^, p. 291.

Se, no entanto, apenas um homem pode sair do barco de cada vez e os maridos devem estar na margem para contar como o par de sua esposa ao invés de apenas estar no barco na margem: mover de 5-6 é impossível, pois assim que o $\gamma$ deixar b na margem não será com o seu marido, apesar dele estar ainda no barco.

Como mencionado anteriormente, esta solução para o problema de maridos ciumentos vai se tornar uma solução para o problema dos missionários e canibais após a substituição dos homens por missionários e as mulheres por canibais. Neste caso, pode-se negligenciar as identidades individuais dos missionários e canibais. A solução dada é apenas mais curta ainda, e é uma das quatro soluções mais curtas.

Se uma mulher dentro do na margem (mas não sobre a margem) conta como sendo ela mesma (ou seja, não na presença de todos os homens sobre a margem), então este quebra-cabeças pode ser resolvido em 9 viagens de um só sentido:

Viagem nº	Margem de saída	Viagem	Margem de chegada
(início)	$\alpha$a $\beta$b $\gamma$c
1	$\beta$b $\gamma$c	$\alpha$a →
2	$\beta$b $\gamma$c	← a	$\alpha$
3	$\beta$ $\gamma$c	ab →	$\alpha$
4	$\beta$ $\gamma$c	← b	$\alpha$a
5	$\gamma$c	$\beta$b →	$\alpha$a
6	$\gamma$c	← b	$\alpha$a $\beta$
7	$\gamma$	bc →	$\alpha$a $\beta$
8	$\gamma$	← c	$\alpha$a $\beta$b
9		$\gamma$c →	$\alpha$a $\beta$b
(fim)			$\alpha$a $\beta$b $\gamma$c

Variações

Uma generalização óbvia é a de variar o número de casais ciumentos (ou missionários e canibais), a capacidade do barco, ou ambos. Se o barco tem 2 pessoas, então dois casais precisam de 5 viagens; com 4 ou mais casais, o problema não tem solução. Se o barco pode ter 3 pessoas, então até 5 casais podem cruzar o rio, se o barco pode ter 4 pessoas, qualquer número de casais pode atravessar^, p. 300..

Se uma ilha é adicionada no meio do rio, então qualquer número de casais pode cruzar com um barco para duas pessoas. Se cruzamentos de margem para margem não são permitidos, então 8n−6 viagens de um só sentido são necessárias para transportar n casais através do rio^, p. 76; mas se for permitido, então 4n+1 viagens serão necessárias se n exceder 4, embora uma solução mínima exige apenas 16 viagens se n for igual a 4^, p. 79.. Se os casais ciumentos são substituídos pelos missionários e canibais, o número de viagens necessárias não mudam se cruzamentos de margem para margem não são permitidos; se eles são, porém, o número de viagens diminui para 4n−1, assumindo que n é pelo menos 3.^, p. 81.

História

A primeira aparição conhecida do problema dos maridos ciumentos se encontra no texto medieval Propositiones Acuendos Juvenes , normalmente atribuída a Alcuíno (morto em 804). Na formulação de Alcuíno os casais são irmãos e irmãs, mas a restrição é ainda a mesma— nenhuma mulher pode estar na companhia de outro homem a menos que seu irmão esteja presente.^, p. 74. Do século XIII para o século XV o problema tornou-se conhecido em todo o Norte da Europa, com o casal agora está sendo maridos e esposas.^{, pp. 291–293.} O problema mais tarde foi posto na forma de mestres e criados; a formulação com os missionários e os canibais não aparece até o final do século XIX^, p. 81 Variar o número de casais e o tamanho do barco foi considerado no início do século XVI.^, p. 296. Cadet de Fontenay consideradou a colocação de uma ilha no meio do rio, em 1879; esta variante do problema, com um barco para duas pessoas, foi completamente resolvida por Ian Pressman e David Singmaster em 1989

Ver também

• Problema do fazendeiro, o lobo, o carneiro e a alface