Mostrar código-fonte de 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ça de travessia de rio|quebra-cabeças de travessia de rio]].<ref name=a>{{citar web|url=http://links.jstor.org/sici?sici=0025-5572%28198906%292%3A73%3A464%3C73%3A%22JHA%22M%3E2.0.CO%3B2-S|titulo="The Jealous Husbands" and "The Missionaries and Cannibals"|autor=PRESSMAN,  Ian; SINGMASTER, David|publicado=''The Mathematical Gazette'', '''73''', #464 (Junho 1989), pp. 73–81.|acessodata=2010-10-02}}</ref> 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.<ref>{{citar web|url=http://www.cc.gatech.edu/~jimmyd/summaries/amarel1968-1.html|titulo=On representations of problems of reasoning about actions|autor=AMAREL, Saul Amarel|publicado=''Machine Intelligence 3'', editada por Donald Michie, Amsterdam, London, New York: Elsevier/North-Holland, 1968, pp. 131–171|acessodata=2010-10-02|arquivourl=https://web.archive.org/web/20080308224227/http://www.cc.gatech.edu/~jimmyd/summaries/amarel1968-1.html|arquivodata=2008-03-08|urlmorta=yes}}</ref><ref>{{citar livro|url=http://dx.doi.org/10.1007/11829263_1|título=Searching in a Maze, in Search of Knowledge: Issues in Early Artificial Intelligence|autor=CORDESCHI, Roberto Cordeschi; STOCK, Oliviero (ed.); SCHAERF, Marco(ed.)|paginas=1–23|capítulo=''Reasoning, Action and Interaction in AI Theories and Systems: essays dedicated to Luigia Carlucci Aiello''|subtitulo=Lecture Notes in Computer Science #4155|local=Berlin/Heidelberg|editora=Springer|ano=2006|id=ISBN 978-3-540-37901-0}}</ref>



==O Problema==
[[Ficheiro:Canibals missionaires.png|350px|Configuração inicial do problema dos canibais e missionários|thumb]]
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.<ref name=a /><ref name=rich>{{Citar livro|url= |autor=RICH, Elaine; KNIGHT, Kevin|título=Inteligência Artificial |idioma= |edição=2ª |local=Rio de Janeiro |editora=Makron Books |ano=1994 |páginas=72, 74 |página= |id=ISBN 85-346-0122-4}}</ref>

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.<ref name=a />

==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 ''<math>\alpha</math>'' (marido) e ''a'' (mulher), ''<math>\beta</math>'' e ''b'', e ''<math>\gamma</math>'' e ''c''.<ref name=b>{{citar livro|capitulo=Jealous Husbands Crossing the River: A Problem from Alcuin to Tartaglia|autor=FRANCI, Raffaella; Dold-Samplonius, Yvonne (ed.); DAUBEN, Joseph W. (ed.); FOLKERTS, Menso (ed.); VAN DALEN, Benno (ed.)|paginas=289–306|titulo=From China to Paris: 2000 Years Transmission of Mathematical Ideas|local=Stuttgart|editora=Franz Steiner Verlag|ano=2002|id=ISBN 3515082239}}.</ref>

{| class="wikitable"
! Viagem nº
! Margem de saída
! Viagem
! Margem de chegada
|-
| (início)
| <math>\alpha</math>a  <math>\beta</math>b <math>\gamma</math>c
|
|
|-
|1
|<math>\beta</math>b <math>\gamma</math>c
|<math>\alpha</math>a &rarr;
|
|-
|2
|<math>\beta</math>b <math>\gamma</math>c
|&larr;<math>\alpha</math>
|a
|-
|3
|<math>\alpha</math> <math>\beta</math> <math>\gamma</math>
|bc &rarr;
|a
|-
|4
|<math>\alpha</math> <math>\beta</math> <math>\gamma</math>
| &larr; a
|b c
|-
|5
|<math>\alpha</math>a
| <math>\beta</math><math>\gamma</math> &rarr;
|b c
|-
|6
|<math>\alpha</math>a
|&larr; <math>\beta</math>b
|<math>\gamma</math>c
|-
|7
|a b
|<math>\alpha</math><math>\beta</math> &rarr;
|<math>\gamma</math>c
|-
|8
|a b
|&larr; c
|<math>\alpha</math> <math>\beta</math> <math>\gamma</math>
|-©
|9
|b
|a c &rarr;
|<math>\alpha</math> <math>\beta</math> <math>\gamma</math>
|-
|10
|b
|&larr; <math>\beta</math>
|<math>\alpha</math>a <math>\gamma</math>c
|-
|11
|
|<math>\beta</math>b &rarr;
|<math>\alpha</math>a <math>\gamma</math>c
|-
|(fim)
|
|
|<math>\alpha</math>a <math>\beta</math>b <math>\gamma</math>c
|}

Esta é a mais curta solução para o problema, mas não é a única solução mais curta.<ref name=b /><sup>,&nbsp;p.&nbsp;291.</sup>

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 ''<math>\gamma</math>'' 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.<ref>{{citar livro|url=http://portal.acm.org/citation.cfm?id=144045.144106Cannibalsandmissionaries|autor=LIM, Ruby (pp.); Lynne C. Shaw, |numero-autores=et al.|titulo=Conference proceedings: APL '92, the International Conference on APL, 6-10 July 1992, St. Petersburg, Russia|local=New York|editora=Association for Computing Machinery|ano=1992|id=ISBN 0-89791-477-5}}</ref>

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:

{| class="wikitable"
! Viagem nº
! Margem de saída
! Viagem
! Margem de chegada
|-
| (início)
|<math>\alpha</math>a <math>\beta</math>b <math>\gamma</math>c
|
|
|-
|1
|<math>\beta</math>b <math>\gamma</math>c
|<math>\alpha</math>a &rarr;
|
|-
|2
|<math>\beta</math>b <math>\gamma</math>c
|&larr; a
|<math>\alpha</math>
|-
|3
|<math>\beta</math> <math>\gamma</math>c
|ab &rarr;
|<math>\alpha</math>
|-
|4
|<math>\beta</math> <math>\gamma</math>c
| &larr; b
|<math>\alpha</math>a
|-
|5
|<math>\gamma</math>c
| <math>\beta</math>b &rarr;
|<math>\alpha</math>a
|-
|6
|<math>\gamma</math>c
|&larr; b
|<math>\alpha</math>a <math>\beta</math>
|-
|7
|<math>\gamma</math>
|bc &rarr;
|<math>\alpha</math>a <math>\beta</math>
|-
|8
|<math>\gamma</math>
|&larr; c
|<math>\alpha</math>a <math>\beta</math>b
|-©
|9
|
|<math>\gamma</math>c &rarr;
|<math>\alpha</math>a <math>\beta</math>b
|-
|(fim)
|
|
|<math>\alpha</math>a <math>\beta</math>b <math>\gamma</math>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.<ref>{{citar web|url=http://www.sciencenews.org/articles/20031213/mathtrek.asp|titulo=Tricky Crossings|autor=PETERSON, Ivars|publicado=Science News, '''164''', #24 (13 de Dezembro de 2003)|acessodata=2008-02-07}}</ref> 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<ref name=b /><sup>,&nbsp;p.&nbsp;300.</sup>.

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 8''n''&minus;6 viagens de um só sentido são necessárias para transportar ''n'' casais através do rio<ref name=a /><sup>,&nbsp;p.&nbsp;76</sup>; mas se for permitido, então 4''n''+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<ref name=a /><sup>,&nbsp;p.&nbsp;79.</sup>. 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 4''n''&minus;1, assumindo que ''n'' é pelo menos 3.<ref name=a /><sup>,&nbsp;p.&nbsp;81.</sup>

== 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.<ref name=a /><sup>,&nbsp;p.&nbsp;74.</sup> 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.<ref name=b /><sup>,&nbsp;pp.&nbsp;291–293.</sup> 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<ref name=a /><sup>,&nbsp;p.&nbsp;81</sup> Variar o número de casais e o tamanho do barco foi considerado no início do século XVI.<ref name=b /><sup>,&nbsp;p.&nbsp;296.</sup> 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<ref name=a />

==Ver também==
*[[Problema do fazendeiro, o lobo, o carneiro e a alface]]

{{Referências}}

[[Categoria:Quebra-cabeças]]
[[Categoria:Jogos de lógica]]