Problema dos canibais e missionários

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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.[1] 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.[2] [3] .


O Problema[editar | editar código-fonte]

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.[1] [4]

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.[1]

Solução[editar | editar código-fonte]

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.[5]

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

Esta é a mais curta solução para o problema, mas não é a única solução mais curta.[5] , 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[6] .

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) \alphaa \betab \gammac
1 \betab \gammac \alphaa →
2 \betab \gammac ← a \alpha
3 \beta \gammac ab → \alpha
4 \beta \gammac ← b \alphaa
5 \gammac \betab → \alphaa
6 \gammac ← b \alphaa \beta
7 \gamma bc → \alphaa \beta
8 \gamma ← c \alphaa \betab
9 \gammac → \alphaa \betab
(fim) \alphaa \betab \gammac

Variações[editar | editar código-fonte]

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[7] . 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[5] , 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[1] , 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[1] , 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.[1] , p. 81.

História[editar | editar código-fonte]

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. [1] , p. 74. Do século 13 para o século 15, o problema tornou-se conhecido em todo o Norte da Europa, com o casal agora está sendo maridos e esposas. [5] , 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 19 [1] , p. 81 Variar o número de casais e o tamanho do barco foi considerado no início do século 16. [5] , 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 [1]

Ver também[editar | editar código-fonte]

Referências

  1. a b c d e f g h i PRESSMAN, Ian; SINGMASTER, David. "The Jealous Husbands" and "The Missionaries and Cannibals". The Mathematical Gazette, 73, #464 (Junho 1989), pp. 73–81.. Página visitada em 2010-10-02.
  2. AMAREL, Saul Amarel. On representations of problems of reasoning about actions. Machine Intelligence 3, editada por Donald Michie, Amsterdam, London, New York: Elsevier/North-Holland, 1968, pp. 131–171.
  3. CORDESCHI, Roberto Cordeschi; STOCK, Oliviero (ed.); SCHAERF, Marco(ed.). . Berlin/Heidelberg: Springer, 2006. ISBN 978-3-540-37901-0
  4. RICH, Elaine; KNIGHT, Kevin. Inteligência Artificial. 2ª ed. Rio de Janeiro: Makron Books, 1994. 72, 74 p. ISBN 85-346-0122-4
  5. a b c d e FRANCI, Raffaella; Dold-Samplonius, Yvonne (ed.); DAUBEN, Joseph W. (ed.); FOLKERTS, Menso (ed.); VAN DALEN, Benno (ed.). From China to Paris: 2000 Years Transmission of Mathematical Ideas. [S.l.]: Franz Steiner Verlag, 2002. ISBN 3515082239.
  6. LIM, Ruby (pp.); Lynne C. Shaw, et al. (ed.). Cannibals and missionaries Conference proceedings: APL '92, the International Conference on APL, 6-10 July 1992, St. Petersburg, Russia. New York: Association for Computing Machinery, 1992. ISBN 0-89791-477-5
  7. PETERSON, Ivars. Tricky Crossings. Science News, 164, #24 (13 de Dezembro de 2003). Página visitada em 2008-02-07.