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?
Nenhum comentário:
Postar um comentário