程式扎記

前言 :
接著 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. 代碼如下:

view plaincopy to clipboardprint?
package c3.waterjug;  
  
public class Jug {  
    public int size = -1;  
    public int content = 0;  
      
    public Jug(int size){this.size = size;}  
      
    // 將目前水壺倒到輸入參數的水壺.  
    public boolean pullTo(Jug jug)  
    {  
        if(!jug.isFull() && !isEmpty())  
        {  
            if(this.content>jug.left())  
            {  
                this.content = this.content-jug.left();  
                jug.setFull();  
            }  
            else  
            {  
                jug.content+=this.content;  
                this.content=0;  
            }  
            return true;  
        }  
        return false;  
    }     
      
    // 裝滿目前水壺.  
    public boolean setFull()  
    {  
        if(size!=content)  
        {  
            this.content=this.size;  
            return true;  
        }  
        return false;  
    }  
      
    // 檢視目前水壺是否裝滿.  
    public boolean isFull(){return size==content;}  
      
    // 檢查目前水壺是否為空.  
    public boolean isEmpty(){return content==0;}  
      
    // 倒空目前水壺.  
    public boolean emptyJug()  
    {  
        if(content>0)  
        {  
            this.content=0;  
            return true;  
        }  
        return false;  
    }  
      
    // 目前水壺剩下多少空間.  
    public int left(){return size-content;}  
}  

接著便是主類別, 執行上面的 main 函數可以進行 Water Jug problem, 這邊使用 BFS (Breadth First Search). 另外在 TA 提醒下, 修改了部分代碼當 Path 為不合理時 (如 3 公升的水壺滿了, 還對它進行填滿的動作; 或是水壺已經為空, 還對它作倒出的動作 etc) 則不對該 Path 進行 expand, 效率可以從原本需要將近 800ms 改善到只要 100ms 上下:

view plaincopy to clipboardprint?
package c3.waterjug;  
  
import java.util.LinkedList;  
import java.util.Set;  
import java.util.TreeSet;  
import java.util.Queue;  
  
public class Main {  
    public static Jug jug4 = new Jug(4);  
    public static Jug jug3 = new Jug(3);  
    public static Set pastTermiSet = new TreeSet();  
      
    // 執行特殊單一動作.  
    public static boolean Go(int action)  
    {  
        switch(action)  
        {  
        case 1:  
            return jug4.emptyJug();  
        case 2:  
            return jug3.emptyJug();  
        case 3:  
            return jug3.pullTo(jug4);  
        case 4:  
            return jug4.pullTo(jug3);  
        case 5:  
            return jug4.setFull();  
        default:  
            return jug3.setFull();    
        }  
    }  
      
    public static void resetJug(){jug4.emptyJug(); jug3.emptyJug();}  
      
      
    /** 
     * BD : 執行一連串的動作. 
     * @param actions 
     * @return Integer 
     *      0. Reach goal 
     *      1. Not yet 
     *      2. Illegal path 
     */  
    public static int Execute(String actions)  
    {  
        for(int i=0; i
        {  
            if(!Go(Integer.valueOf(String.valueOf(actions.charAt(i)))))   
            {  
                resetJug();  
                return 2;  
            }  
        }  
        boolean result = GoalTest();  
        resetJug();  
        return result?0:1;  
    }  
  
    // Define your goal test here.  
    public static boolean GoalTest()  
    {  
        if(jug4.content==2) return true;  
        return false;  
    }  
      
    // 返回目前水壺的狀態.  
    public static String jugStates()  
    {  
        return String.format("jug4[%d/%d],jug3[%d/%d]", jug4.content, jug4.size, jug3.content, jug3.size);  
    }  
      
    // 顯示到達 Goal 所必須進行的 actions.  
    public static void showActions(String actions)  
    {  
        int actInt;       
        for(int i=0; i
        {  
            actInt = Integer.valueOf(String.valueOf(actions.charAt(i)));  
            switch(actInt)  
            {  
            case 1:               
                jug4.emptyJug();  
                System.out.printf("\tEmpty jug4---%s\n", jugStates());  
                break;  
            case 2:               
                jug3.emptyJug();  
                System.out.printf("\tEmpty jug3---%s\n", jugStates());  
                break;  
            case 3:               
                jug3.pullTo(jug4);  
                System.out.printf("\tPull jug3 to jug4---%s\n", jugStates());  
                break;  
            case 4:               
                jug4.pullTo(jug3);  
                System.out.printf("\tPull jug4 to jug3---%s\n", jugStates());  
                break;  
            case 5:               
                jug4.setFull();  
                System.out.printf("\tFull jug4---%s\n", jugStates());  
                break;  
            default:                  
                jug3.setFull();  
                System.out.printf("\tFull jug3---%s\n", jugStates());  
            }  
        }  
    }  
      
    /** 
     * BD : Water Jug problem 
     *      - You are given two jugs with no measuring marks, a 4-gallon one and a 3-gallon one. 
     *      - There is a pump to fill the jugs with water. 
     *      - How can you get exactly 2 gallons of water into the 4-gallon jug? 
     * States: 
     *      Content of each jug 
     *  
     * Actions: 
     *      - Empty the jug 
     *        A1 = Empty jug4 
     *        A2 = Empty jug3 
     *      - Pull one jug to another jug 
     *        A3 = Pull jug3 to jug4 
     *        A4 = Pull jug4 to jug3 
     *      - Full the jug 
     *        A5 = Full jug4 
     *        A6 = Full jug3 
     *  
     * Goal test:  
     *      The jug(size=4) has content=2. 
     *  
     * Path cost: 
     *      Each action cost 1. 
     *  
     * @param args 
     */  
    public static void main(String args[])  
    {  
        Queue queue = new LinkedList();  
        queue.add("");  
        String actions = null;  
          
        // Using BFS  
        long st = System.currentTimeMillis();  
        int rtVal;  
        boolean hasAnswer = false;  
        while(!queue.isEmpty())  
        {  
            actions = queue.poll();           
            rtVal=Execute(actions);           
            if(rtVal==0)   
            {  
                hasAnswer = true;  
                break;  
            }  
            else if(rtVal==2) continue; // Illegal path -> Don't expand it.  
            for(int i=1; i<=6; i++)  
            {  
                queue.add(String.format("%s%d", actions, i));  
            }  
        }  
        if(hasAnswer)  
        {  
            System.out.printf("\t[Info] Done! (Cost=%d, Spending time=%dms)\n", actions.length(), System.currentTimeMillis()-st);  
            System.out.printf("\t[Info] Actions:\n");  
            showActions(actions);  
        }  
        else  
        {  
            System.out.printf("\t[Info] No answer!\n");  
        }  
    }  
}  

執行代碼後, 結果如下:

[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

程式扎記

標籤

2012年10月8日星期一

[ Algorithm ] Water Jug problem

沒有留言:

張貼留言

[Git 常見問題] error: The following untracked working tree files would be overwritten by merge

檢舉濫用情形

學習筆記

標籤

2012年10月8日 星期一