Modelagem de Problemas Clássicos: Canibais/Missionários e Potes de Vinho
Classificado em Matemática
Escrito em em
português com um tamanho de 2,91 KB
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, caso contrário, os missionários estariam em grande perigo de vida. Como administrar a travessia?
Modelo 1: Grafo G(V,A)
Um modelo para este problema é definir o grafo G(V,A) como:
- V = { (c,m) | c e m representam o número de canibais e de missionários em uma das margens do rio, sendo que: $0 \le c \le 3$, $0 \le m \le 3$, (