Make your own free website on Tripod.com


Problemas de Travessia

 

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:

Problema dos canibais e dos missionários

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?