water jug problem

눈금이 없는 두 물주머니 A, B가 있다.

A물주머니는 3gallon 이고 B물주머니는 5gallon이다.

물은 무한정 제공될 때 4gallon을 만들어라

 

 

1. production rule 을 세워 해결하는 방법

A, B 물주머니에 들어있는 물의 양을 (x,y)로 표현할 때, 생성식을 세운 후 최종상태를 탐색하는 방법으로 해결할 수 있다.

생성식은,

1) (x,y) if x<3 then (3,y); //fill the 3gallon jug

2) (x,y) if y<5 then (x,5); //fill the 5gallon jug

3) (x,y) if x+y >= 3 and y>0 then (3, y-(3-x)); //pour water from 5gallon jug into 3gallon jug until the 3gallon jug is full.

4) (x,y) if x+y >=5 and x>0 then (x-(5-y), 5); //pour water from 3gallon jug into 5gallon jug until the 5gallon jug is full.

...

와 같이 가능한 상황들(다음 상태를 생성해낼 수 있는 식들)을 세운 후 상태탐색을 진행하는데 사용하는것이다.

상태탐색은 DFS나 BFS등 systematic search나 genetic search같은 stochastic search를 해도 된다.

 

이 방법은 물주머니에 최적화된 풀이라기보다는, 이런류의 문제를 푸는 일반적인 방법이라고 할 수 있어 의미가 있다.

물론 매우 느리며 생성식에 따라 무한루프에 빠질수도 있으니 조심해야한다.

 

 

 

2. 상식적인 해결

water jug 문제를 많이 풀어보다 보면, 일정한 패턴이 있다.

큰 용량의 물주머니를 B라고 할 때,

1. fill A

2. pour A into B

3. if B has goal gallon then finish

4. else if B is full then empty B and goto 2.

5. fill A and goto 2.

와 같은 방법으로 해결할 수 있다.

 

 

 

3. GCD(최대공약수) 풀이

water jug 문제는 사실 gcd문제를 실제의 예로 옮겨놓은 문제이다. 즉, gcd풀이방법으로 풀 수 있다

1. if A is not full and B is empty then fill B

2. if A is full then empty A

3. pour B into A

4. repeat 1-3 until A is goal gallon or B is goal gallon