Os
problemas de travessia são caracterizados
pela existência de uma situação (estado)
inicial, de uma série de etapas
intermediárias e de um estado final. Em
geral eles também incluem um conjunto de
restrições que levam à inviabilidade de
alguns estados, os quais são excluídos do
modelo. A solução para o problema passa ,
então, por determinar uma sequência viável
de decisões, que conduza do estado inicial
ao estado final.
Alguns
exemplos clássicos de problemas de travessia
são descritos a seguir:
Três canibais e
três missionários estão viajando
juntos e chegam à margem de um rio.
Eles desejam atravessar para a outra
margem para, desta forma, continuar a
viagem. O único meio de transporte
disponível é um barco que comporta no
máximo duas pessoas. Há uma outra
dificuldade: em nenhum momento o número
de canibais pode ser superior ao número
de missionários pois desta forma os
missionários estariam em grande perigo
de vida. Como administrar a travessia?
Problema dos potes de
vinho
Considere que
temos três potes com capacidades de
8, 5 e 3 litros, respectivamente, os
quais não possuem qualquer marcação. O
maior deles esta completamente cheio
enquanto que os outros dois estão
vazios. Estamos interessados em dividir o
vinho em duas porções iguais de 4
litros, tarefa esta que pode ser
realizada por transvasos sucessivos de um
vaso no outro. Qual o menor número de
transvasos necessários para completar
a divisão?
Problema dos três
maridos ciumentos
Três
esposas e seus respectivos maridos
desejam ir ao centro da cidade em um
Corvette, o qual comporta apenas duas
pessoas. Como eles poderiam deslocar-se
até o centro considerando que nenhuma
esposa deveria estar com um ou ambos os
outros maridos a menos que seu marido
também esteja presente?
Problema da fuga dos
ladrões
Uma
quadrilha de 3 ladrões assalta um banco
e foge com uma mala de dinheiro para um
aeroporto onde um avião pronto para
decolar está à espera. O esconderijo é
seguro, mas a fuga é difícil porque o
avião só comporta 170 kg. Só um dos
ladrões sabe pilotar e ele pesa 60 kg. O
segundo, que é o guarda-costas do chefe,
pesa 100 kg e o chefe pesa 70 kg. O chefe
teme que o piloto fuja com o dinheiro
(que pesa 40 kg) se tiver uma
oportunidade. O piloto tem a mesma
preocupação em relação ao chefe.
Apenas o guarda-costas merece a
confiança de ambos. A quadrilha, no
entanto, já elaborou um plano de fuga
capaz de satisfazer a todos. Qual é esse
plano?