Exemplo de representação do Problema “Canibais e Missionários”. Problemas: Três canibais e três missionários estão viajando juntos e chegam à marge...

Exemplo de representação do Problema “Canibais e Missionários”. Problemas: 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? Espaço de Estados: Podemos representar os estados por um par ordenado (c,m). c = representa o número de canibais (0 ≤ c ≥ 3). m = representa o número de missionários (0 ≤ m ≥ 3). Teremos 16 (24) estados possíveis já que existem duas variáveis (c,m) com 4 valores possíveis para cada uma (0 à 3). Estes estados vão de (0,0) à (3,3). Também podemos representar a margem onde (c,m) se encontram através do complemento dos pares ordenados. Os pares ordenados que representam os estados não viáveis: {(2,1);(3,1);(3,2) - (1,2);(0,2);(0,1)}. Condições de Travessia: Se o barco comporta no máximo 2 pessoas, há 5 possíveis situações em cada travessia. Levar 1 canibal → (1,0). Levar 2 canibais; → (2,0). Levar 1 missionário; → (0,1). Levar 2 missionários; → (0,2). Levar 1 canibal e 1 missionário. → (1,1). Usando a forma (cm), onde “c” é o número de Canibais e “m”, o número de missionários, que serão atravessados, temos as seguintes ações. Pré-condições: Em cada uma destas ações, testar se existem indivíduos suficientes para transportar. Em cada uma destas ações, testar para garantir que tem mais Missionários do que Canibais. Efeitos das Ações: Em cada uma destas ações, é preciso calcular o efeito (pós-condições) que cada uma tem nos estados objetivos. Considerando que x é a margem de origem e y a de destino. O Grafo a seguir exemplifica como seria o espaço de espaços total, caso o teste de restrição fosse apenas nos estados de origem do movimento, por exemplo. Os círculos em azul representam a margem esquerda. Os círculos em vermelho representam a margem direita. Os círculos hachurados em laranja representam estados não viáveis. Considerando o estado inicial (3,3) na margem esquerda e a ação (0,1), mover um missionário da esquerda para a direita, o teste de restrição seria: (3-M)-(3-C) ≥ 1. (3-3)-(3-3) ≥ 1. 0 ≥ 1, ou seja, o movimento é não viável pois deixa 3 canibais com 1 Missionário na margem de origem.