程式扎記: [ Algorithm ] Water Jug problem

標籤

2012年10月8日 星期一

[ Algorithm ] Water Jug problem


前言 :
接著 8 puzzle problem, 為了讓我更了解第三堂提到的 Single-State Problem, 我決定拿 Water Jug problem 來當作範例實作並理解上課的內容. 首先先來了解什麼是 Water Jug problem:
- 你有兩個水壺, 一個3公升; 另一個4公升. 水壺上沒有標記, 所以你不知道裝了多少.
- 你有一個 pump 可以一次把水壺給填滿.
- 問題是你如何得到4公升水壺裡有 2 公升的水.

問題分析 :
首先要來決定 Environment types:
1. 每次的動作都可以決定下一步的狀態. (清空水壺, 倒滿水壺 etc) -> Deterministic
2. 每個水壺的狀態都可以知道 -> Fully observable

因此我們可以知道這是一個 Single-state problem. 而在解 Single-state problem 有幾個要點:
1. States: 每個水壺目前的容量
2. Actions : 可能的動作有 裝滿 3 或 4公升水壺, 清空 3 或 4公升水壺, 將 3 公升水壺倒到 4 公升水壺, 將 4 公升水壺倒到 3 公升水壺.
3. Goal test: 最終希望 4 公升水壺裝 2 公升的水.
4. Path cost: 這邊以一個 action 為 cost.

有了這些分析, 接下來便是實作的部分.

代碼說明 :
這邊我定義類別 Jug 來代表水壺, 並透過上面的方法進行 action. 代碼如下:
  1. package c3.waterjug;  
  2.   
  3. public class Jug {  
  4.     public int size = -1;  
  5.     public int content = 0;  
  6.       
  7.     public Jug(int size){this.size = size;}  
  8.       
  9.     // 將目前水壺倒到輸入參數的水壺.  
  10.     public boolean pullTo(Jug jug)  
  11.     {  
  12.         if(!jug.isFull() && !isEmpty())  
  13.         {  
  14.             if(this.content>jug.left())  
  15.             {  
  16.                 this.content = this.content-jug.left();  
  17.                 jug.setFull();  
  18.             }  
  19.             else  
  20.             {  
  21.                 jug.content+=this.content;  
  22.                 this.content=0;  
  23.             }  
  24.             return true;  
  25.         }  
  26.         return false;  
  27.     }     
  28.       
  29.     // 裝滿目前水壺.  
  30.     public boolean setFull()  
  31.     {  
  32.         if(size!=content)  
  33.         {  
  34.             this.content=this.size;  
  35.             return true;  
  36.         }  
  37.         return false;  
  38.     }  
  39.       
  40.     // 檢視目前水壺是否裝滿.  
  41.     public boolean isFull(){return size==content;}  
  42.       
  43.     // 檢查目前水壺是否為空.  
  44.     public boolean isEmpty(){return content==0;}  
  45.       
  46.     // 倒空目前水壺.  
  47.     public boolean emptyJug()  
  48.     {  
  49.         if(content>0)  
  50.         {  
  51.             this.content=0;  
  52.             return true;  
  53.         }  
  54.         return false;  
  55.     }  
  56.       
  57.     // 目前水壺剩下多少空間.  
  58.     public int left(){return size-content;}  
  59. }  
接著便是主類別, 執行上面的 main 函數可以進行 Water Jug problem, 這邊使用 BFS (Breadth First Search). 另外在 TA 提醒下, 修改了部分代碼當 Path 為不合理時 (如 3 公升的水壺滿了, 還對它進行填滿的動作; 或是水壺已經為空, 還對它作倒出的動作 etc) 則不對該 Path 進行 expand, 效率可以從原本需要將近 800ms 改善到只要 100ms 上下:
  1. package c3.waterjug;  
  2.   
  3. import java.util.LinkedList;  
  4. import java.util.Set;  
  5. import java.util.TreeSet;  
  6. import java.util.Queue;  
  7.   
  8. public class Main {  
  9.     public static Jug jug4 = new Jug(4);  
  10.     public static Jug jug3 = new Jug(3);  
  11.     public static Set pastTermiSet = new TreeSet();  
  12.       
  13.     // 執行特殊單一動作.  
  14.     public static boolean Go(int action)  
  15.     {  
  16.         switch(action)  
  17.         {  
  18.         case 1:  
  19.             return jug4.emptyJug();  
  20.         case 2:  
  21.             return jug3.emptyJug();  
  22.         case 3:  
  23.             return jug3.pullTo(jug4);  
  24.         case 4:  
  25.             return jug4.pullTo(jug3);  
  26.         case 5:  
  27.             return jug4.setFull();  
  28.         default:  
  29.             return jug3.setFull();    
  30.         }  
  31.     }  
  32.       
  33.     public static void resetJug(){jug4.emptyJug(); jug3.emptyJug();}  
  34.       
  35.       
  36.     /** 
  37.      * BD : 執行一連串的動作. 
  38.      * @param actions 
  39.      * @return Integer 
  40.      *      0. Reach goal 
  41.      *      1. Not yet 
  42.      *      2. Illegal path 
  43.      */  
  44.     public static int Execute(String actions)  
  45.     {  
  46.         for(int i=0; i
  47.         {  
  48.             if(!Go(Integer.valueOf(String.valueOf(actions.charAt(i)))))   
  49.             {  
  50.                 resetJug();  
  51.                 return 2;  
  52.             }  
  53.         }  
  54.         boolean result = GoalTest();  
  55.         resetJug();  
  56.         return result?0:1;  
  57.     }  
  58.   
  59.     // Define your goal test here.  
  60.     public static boolean GoalTest()  
  61.     {  
  62.         if(jug4.content==2return true;  
  63.         return false;  
  64.     }  
  65.       
  66.     // 返回目前水壺的狀態.  
  67.     public static String jugStates()  
  68.     {  
  69.         return String.format("jug4[%d/%d],jug3[%d/%d]", jug4.content, jug4.size, jug3.content, jug3.size);  
  70.     }  
  71.       
  72.     // 顯示到達 Goal 所必須進行的 actions.  
  73.     public static void showActions(String actions)  
  74.     {  
  75.         int actInt;       
  76.         for(int i=0; i
  77.         {  
  78.             actInt = Integer.valueOf(String.valueOf(actions.charAt(i)));  
  79.             switch(actInt)  
  80.             {  
  81.             case 1:               
  82.                 jug4.emptyJug();  
  83.                 System.out.printf("\tEmpty jug4---%s\n", jugStates());  
  84.                 break;  
  85.             case 2:               
  86.                 jug3.emptyJug();  
  87.                 System.out.printf("\tEmpty jug3---%s\n", jugStates());  
  88.                 break;  
  89.             case 3:               
  90.                 jug3.pullTo(jug4);  
  91.                 System.out.printf("\tPull jug3 to jug4---%s\n", jugStates());  
  92.                 break;  
  93.             case 4:               
  94.                 jug4.pullTo(jug3);  
  95.                 System.out.printf("\tPull jug4 to jug3---%s\n", jugStates());  
  96.                 break;  
  97.             case 5:               
  98.                 jug4.setFull();  
  99.                 System.out.printf("\tFull jug4---%s\n", jugStates());  
  100.                 break;  
  101.             default:                  
  102.                 jug3.setFull();  
  103.                 System.out.printf("\tFull jug3---%s\n", jugStates());  
  104.             }  
  105.         }  
  106.     }  
  107.       
  108.     /** 
  109.      * BD : Water Jug problem 
  110.      *      - You are given two jugs with no measuring marks, a 4-gallon one and a 3-gallon one. 
  111.      *      - There is a pump to fill the jugs with water. 
  112.      *      - How can you get exactly 2 gallons of water into the 4-gallon jug? 
  113.      * States: 
  114.      *      Content of each jug 
  115.      *  
  116.      * Actions: 
  117.      *      - Empty the jug 
  118.      *        A1 = Empty jug4 
  119.      *        A2 = Empty jug3 
  120.      *      - Pull one jug to another jug 
  121.      *        A3 = Pull jug3 to jug4 
  122.      *        A4 = Pull jug4 to jug3 
  123.      *      - Full the jug 
  124.      *        A5 = Full jug4 
  125.      *        A6 = Full jug3 
  126.      *  
  127.      * Goal test:  
  128.      *      The jug(size=4) has content=2. 
  129.      *  
  130.      * Path cost: 
  131.      *      Each action cost 1. 
  132.      *  
  133.      * @param args 
  134.      */  
  135.     public static void main(String args[])  
  136.     {  
  137.         Queue queue = new LinkedList();  
  138.         queue.add("");  
  139.         String actions = null;  
  140.           
  141.         // Using BFS  
  142.         long st = System.currentTimeMillis();  
  143.         int rtVal;  
  144.         boolean hasAnswer = false;  
  145.         while(!queue.isEmpty())  
  146.         {  
  147.             actions = queue.poll();           
  148.             rtVal=Execute(actions);           
  149.             if(rtVal==0)   
  150.             {  
  151.                 hasAnswer = true;  
  152.                 break;  
  153.             }  
  154.             else if(rtVal==2continue// Illegal path -> Don't expand it.  
  155.             for(int i=1; i<=6; i++)  
  156.             {  
  157.                 queue.add(String.format("%s%d", actions, i));  
  158.             }  
  159.         }  
  160.         if(hasAnswer)  
  161.         {  
  162.             System.out.printf("\t[Info] Done! (Cost=%d, Spending time=%dms)\n", actions.length(), System.currentTimeMillis()-st);  
  163.             System.out.printf("\t[Info] Actions:\n");  
  164.             showActions(actions);  
  165.         }  
  166.         else  
  167.         {  
  168.             System.out.printf("\t[Info] No answer!\n");  
  169.         }  
  170.     }  
  171. }  
執行代碼後, 結果如下:
[Info] Done! (Cost=6, Spending time=109ms)
[Info] Actions:
Full jug4---jug4[4/4],jug3[0/3]
Pull jug4 to jug3---jug4[1/4],jug3[3/3]
Empty jug3---jug4[1/4],jug3[0/3]
Pull jug4 to jug3---jug4[0/4],jug3[1/3]
Full jug4---jug4[4/4],jug3[1/3]
Pull jug4 to jug3---jug4[2/4],jug3[3/3]
This message was edited 14 times. Last update was at 09/10/2012 13:47:32

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!