| Problema dos dois baldes de água
Enunciado do problema: Você recebe dois baldes de água, um de quatro litros e outro de três litros. Nenhum deles possui qualquer marcação de medida. Há uma torneira que pode ser utilizada para encher os baldes de água. Como colocar exatamente dois litros d'água dentro do balde de quatro litros? [RIC 94] O espaço de estados para este problema pode ser modelado como o conjunto de pares ordenados de números naturais (x,y) tal que x = 0, 1, 2, 3 ou 4 e y = 0, 1, 2 ou 3, onde x representa a quantidade de água no balde de 4 litros, e y representa a quantidade de água no balde de 3 litros. O estado inicial do problema é o estado no qual ambos os baldes estão vazios: (0,0), e o conjunto de estados finais é constituído por todos os estados onde a quantidade de água no primeiro balde é 2, ou seja: (2,n), onde n = 0, 1, 2 ou 3. Possível conjunto de regras de produção para o problema: r1 (x,y|x<4)?? (4,y) Encher o balde de 4 litros r2 (x,y|y<3)?? (x,3) Encher o balde de 3 litros r3 (x,y|x>0)?? (0,y) Esvaziar o balde de 4 litros no chão r4 (x,y|y>0)?? (x,0) Esvaziar o balde de 3 litros no chão r5 (x,y|x+y>4)?? (4,y-(4-x)) Despejar água do balde de 3 litros dentro do balde de 4 litros até que este esteja cheio r6 (x,y|x+y>3)?? (x-(3- y),3) Despejar água do balde de 4 litros dentro do balde de 3 litros até que este esteja cheio r7 (x,y|x+y?4 e y>0)?? (x+y,0) Despejar toda a água do balde de 3 litros dentro do balde de 4 litros r8 (x,y|x+y?3 e x>0)?? (0,x+y) Despejar toda a água do balde de 4 litros dentro do balde de três litros Uma possível solução seria aplicar as regras na seguinte seqüência: r2 ,r9,r2 ,r7,r5 e r9 Situação dos baldes à cada aplicação:
[Voltar] |