Modelagem de Problemas Clássicos: Canibais/Missionários e Potes de Vinho

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$, ($m = c$) ou ($m = 0$) ou ($m = 3$) }
• A = { (e1,e2) | e1 = (c1,m1) é o estado da margem onde o barco está antes da travessia ser iniciada, e e2 = (c2,m2) é o estado da margem oposta após o barco completar a travessia, sendo que: $c2 \ge 3-c1$, $m2 \ge 3-m1$, $1 \le | (m2 - (3-m1)) + (c2 - (3-c1)) | \le 2$ }

Modelo 2: Grafo G(V,A) com Foco na Margem Esquerda

Um segundo modelo para este problema é dado pelo grafo G(V,A):

• V = { (c,m) | c e m representam o número de canibais e de missionários na margem esquerda do rio, sendo que: $0 \le c \le 3$, $0 \le m \le 3$, ($m = c$) ou ($m = 0$) ou ($m = 3$) }
• A = { (e1,e2) | e1 = (c1,m1) é o estado antes da travessia ser iniciada, estando o barco na margem esquerda, e e2 = (c2,m2) é o estado após o barco completar a travessia, sendo que: $c1 \ge c2$, $m1 \ge m2$, $1 \le (c1 + m1) - (c2 + m2) \le 2$ }

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 está 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 transvases sucessivos de um pote no outro. Qual o menor número de transvases necessários para completar a divisão?

Sejam $c_1 = 8$, $c_2 = 5$ e $c_3 = 3$ respectivamente as capacidades dos três potes $p_1$, $p_2$ e $p_3$. Então, um possível modelo para este problema é definir o grafo G(V,A) como:

Modelo do Grafo G(V,A)

• V = { ($q_1$, $q_2$, $q_3$) | $q_1$, $q_2$ e $q_3$ representam as quantidades de vinho dos três potes, sendo que: $0 \le q_1 \le c_1$, $0 \le q_2 \le c_2$, $0 \le q_3 \le c_3$, $q_1 + q_2 + q_3 = 8$ }
• A = { (e1,e2) | o estado e2 é alcançado partindo-se do estado e1 por meio de um único transvase de um pote para outro, cuja; o transvase é completado quando o pote de origem é esvaziado ou quando o pote de destino é enchido }