2011年6月18日 星期六

演算法 - 售貨員旅行問題 (traveling salesman problem)

貨員旅行問題是一種最佳化的問題,可以利用回溯或動態規劃來解決,在蔡宗翰譯的「演算法--使用C++虛擬碼」書中(碁峯資訊,2004年),第六章「BRANCH-AND-BOUND」,分枝界限修剪法之最佳優先搜尋的方法能更快地解決問題。

在許多個城市中,售貨員必須節省他的時間走訪美一個城市去銷售他的物品,最後再回到原本的城市中,但城市與城市之災來回的時間不一樣,這可能是因為城市與城市之間的高速公路常常塞車,亦或是可能碰到一些單行道....等,所以依照時間的不確定性,找出一個最有效率的走法,這類問題稱之為售貨員旅行問題。

利用回溯,可先求出一段路徑作為比較基準,比之大就不再走下去,比之小就已它作為基準繼續再找更小的路徑,一直找到最後,最佳路徑即會出現,建構 TravelingSalesperson 類別傳入 W 陣列,W[i][j] 代表從城市 i 到城市 j 所花的時間,最後 bestPath 紀錄最佳路徑的走法,minlength 則是最佳路徑的時間長度,以下為 C# 範例程式碼:
class TravelingSalesperson
{
    int n;
    int[,] W;
    public int[] recordPath, bestPath;
    public int length, minlength;
    public TravelingSalesperson(int[,] W)
    {
        this.W = W;
        length = 0;
        minlength = int.MaxValue;
        n = W.GetLength(0);

        recordPath = new int[n];
        bestPath = new int[n];

        for (int i = 0; i < n; i++)
        {
            recordPath[i] = i;
            bestPath[i] = i;
        }
    }

    public void teavel(int i)
    {
        if (i > n - 1)
        {
            length += W[recordPath[n - 1], 0];
            if (length < minlength)
            {
                minlength = length;
                for (int k = 0; k < n; k++)
                    bestPath[k] = recordPath[k];
            }
            length -= W[recordPath[n - 1], 0];
            return;
        }

        for (int j = i; j < n; j++)
        {
            swapRecordPath(j, i);
            length += W[recordPath[i - 1], recordPath[i]];

            if (length < minlength)
                teavel(i + 1);

            length -= W[recordPath[i - 1], recordPath[i]];
            swapRecordPath(j, i);
        }
    }

    public void swapRecordPath(int i, int j)
    {
        int temp = recordPath[i];
        recordPath[i] = recordPath[j];
        recordPath[j] = temp;
    }
}
而分枝界限修剪法之最佳優先搜尋的方法,則提供 C# 原始碼,有興趣可以買書來參考,傳入 W 陣列,W[i][j] 代表從城市 i 到城市 j 所花的時間,minlength 則是傳入一個大於任何最佳解的數即可:
struct node
{
    public int level, bound;
    public string path;
    public bool[] isUse;
}

class Travel
{
    int[,] W;
    public node init;
    public int minlength;
    public string opttour;
    int num;

    public Travel(int[,] W, int minlength)
    {
        this.W = W;
        num = W.GetLength(0);

        init = new node();
        init.isUse = new bool[num];

        init.level = 0;
        init.path = "0";
        init.isUse[0] = true;
        init.bound = bound(init);

        this.minlength = minlength;
    }

    public void solve(node n)
    {
        List<node> PQ = new List<node>();
        node v = new node();
       

        if (n.bound < minlength)
        {
            if (n.level == num - 2)
            {
                int i;
                for (i = 0; n.isUse[i]; i++) ;
                n.path += string.Format(",{0}", i);

                int temp = length(n);
                if (temp < minlength)
                {
                    minlength = temp;
                    opttour = n.path;
                }

            }
            else
            {
                for (int i = 1; i < num; i++)
                {
                    if (n.isUse[i]) continue;


                    v.level = n.level + 1;
                    v.path = n.path + string.Format(",{0}", i);
                    v.isUse = new bool[num];
                    for (int j = 0; j < num; j ++)
                        v.isUse[j] = n.isUse[j];

                    v.isUse[i] = true;
                    v.bound = bound(v);

                    PQ.Add(v);
                    for (int j = PQ.Count - 1; j >= 1; j--)
                        if (PQ[j].bound < PQ[j - 1].bound)
                        {
                            node temp = PQ[j];
                            PQ[j] = PQ[j - 1];
                            PQ[j - 1] = temp;
                        }
                        else break;
                }
            }


            for (int i = 0; i < PQ.Count; i++)
                solve(PQ[i]);
        }
    }

    public int bound(node n)
    {
        int intBound = 0;
        int[] aIntPath = readPath(n.path);
        int intPathLen = aIntPath.Length;

        for (int i = 0; i < intPathLen - 1; i++)
            intBound += W[aIntPath[i], aIntPath[i + 1]];

        for (int i = 0; i < num; i++)
        {
            if (n.isUse[i] && i != aIntPath[intPathLen - 1]) 
                continue;

            int min = int.MaxValue;

            for (int j = 0; j < num; j++)
            {
                if (intPathLen > 1 && aIntPath[intPathLen - 1] == i 
                    && aIntPath[0] == j) continue;

                if (n.isUse[j] && j != aIntPath[0]) continue;

                if (i != j && W[i, j] < min)
                    min = W[i, j];
            }
            intBound += min;
        }
        aIntPath = null;
        return intBound;
    }

    public int length(node n)
    {
        int intLength = 0;
        int[] aIntPath = readPath(n.path);
        int intPathLen = aIntPath.Length;

        for (int i = 0; i < intPathLen - 1; i++)
            intLength += W[aIntPath[i], aIntPath[i + 1]];

        intLength += W[aIntPath[intPathLen - 1], aIntPath[0]];

        return intLength;
    }

    int[] readPath(string strPath)
    {
        string[] aStrPath = strPath.Split(new char[] { ',' },
            StringSplitOptions.RemoveEmptyEntries);

        int intPathLen = aStrPath.Length;

        int[] aIntPath = new int[intPathLen];
        for (int i = 0; i < intPathLen; i++)
            aIntPath[i] = Convert.ToInt32(aStrPath[i]);

        aStrPath = null;
        return aIntPath;
    }
}
回首頁

2011年6月12日 星期日

演算法 - 判斷是否為質數

利用以下 C# 程式碼中的 isPrime(int n) 可以找出 1 ~ 2147483647 之間的質數:
class Prime
{
    static int MAXSIZE = 46340;
    bool[] prime;
    int[] prime_table;
    int prime_table_len;

    public Prime()
    {
        prime_table_len = 0;
        prime = new bool[MAXSIZE + 1];
        prime_table = new int[MAXSIZE];
        initBoolArray(prime);

        for (int i = 3; i <= MAXSIZE; i += 2)
            if (prime[i])
            {
                for (int j = i + i; j <= MAXSIZE; j += i)
                    prime[j] = false;
                prime_table[prime_table_len++] = i;
            }
    }

    public bool isPrime(int n)
    {
        if (n == 2) return true;
        if (n % 2 == 0) return false;

        if (n <= MAXSIZE)
            return prime[n];

        for (int i = 0; i != prime_table_len && 
            prime_table[i] * prime_table[i] <= n; ++i)
            if (n % prime_table[i] == 0)
                return false;
        return true;
    }

    private void initBoolArray(bool[] value)
    {
        int len = value.Length;
        for (int i = 0; i < len; i ++ )
            value[i] = true;
    }
}
回首頁

2011年6月11日 星期六

演算法 - 最大公因數 ( 歐幾里得 )

大公因數可以利用輾轉相除法求出,利用遞迴的方式,產生同於輾轉相除的作法,以下為 C# 程式碼範例:
public int gcd(int a, int b)
{                                                                
    if (a % b == 0){ return b;}                                                                       
    return gcd(b , a % b);                                                                            
}
回首頁

Cookie 與 Session

最近要把一個ASP的網站改寫成ASP.NET,一段時間沒接觸,發現自己有些網頁的基本觀念還不是很清楚,希望現在複習一下還不太晚。

State、Stateless、Stateful
要了解Cookie和Session物件就不得不先提HTTP是Stateless的協定這點,因為這是,那State、Stateless、Stateful分別又是什麼意思?

“Stateless”在這裡直接翻譯成中文的話是「無狀態」,不說清楚的話還以為是張懸的歌每次Client端對Server發出的要求(Request)都是各自獨立的,前面的要求不會影響到後面的回應。用買東西當範例:先送出一個Request選定一個標錯價的螢幕,再送出一個Request要結帳,但是上一個選定的Request並不會被儲存,也就是說Server不會記得你剛剛做了什麼

所以State就是「目前的狀態」的意思,“Stateful”這個詞相應而生,意思是Client端與Server端之間的對話能夠記住現在在做什麼,也就是「充滿狀態的」。

Cookie?好吃嗎?
Cookie只是一個小小的文字檔,存在你的記憶體或硬碟空間裡(也就是Client端),通常會儲存一些對網站的個人喜好設定還有session的id,以前可能會拿來驗證是否登入但是隨著XSS攻擊的災情逐漸慘重大家也就開始注重Cookie的安全性,除了不要把重要的東西放進去之外把HttpOnly這個屬性設為true,這樣除了HTTP協定以外的東西就沒辦法存取這個Cookie了。
browser_show_cookie
(網址列打javascript:alert(document.cookie),用javascript顯示出目前頁面的Cookie)
下面的C#語法示範了如何產生一個Cookie
HttpCookie myCookie = new HttpCookie("WhenItWasMade");
DateTime now = DateTime.Now;

myCookie.Value = now.ToString();
aCookie.Expires = DateTime.Now.AddDays(1)
myCookie.HttpOnly = true;
Response.Cookies.Add(myCookie);

expires是過期的意思,所以這是個一天之後就會過期的Cookie。如果不設定的話,在關掉瀏覽器的時候Cookie就會被清除。

HttpOnyly屬性設為true之後在網址列打javascript:alert(document.cookie)
就顯示不出任何東西了。

Seesion,Sever端的物件
畢竟Cookie是儲存在Client端,難免會有安全性的問題,所以一些比較重要的資料就會選擇使用Session,比如說是否登入的驗證。比較特別的是Session是跟著瀏覽器產生的,所以當關掉瀏覽器或是過了20分鐘之後(也可以設定久一點)就會被拋棄。下面有個簡單的例子:
protected void Submit_Click(object sender, EventArgs e)
{
Session["age"] = AgeTextBox.Text;
Session.Timeout = 1;
}
protected void ShowButton_Click(object sender, EventArgs e)
{
if (Session["age"] != null)
{
Response.Write("You are " + Session["age"] + " years old<br/>");
Response.Write("Session ID: " + Session.SessionID.ToString() + "<br/>");
Response.Write("Time out: "+ Session.Timeout.ToString()+"<br/>");
}
else
Response.Write("Session not exist!");
}

image image

按下Submit再按Show就可以看到存在Session["age"]的資料,每個Session都會有個Session ID,Client端的瀏覽器拿著這個ID向Sever端相認,證明這個Session儲存的資料是屬於自己的。

image

Session.Timeout則是以分鐘為單位設定Session的生命週期,在這裡設為一分鐘,一分鐘後再按下Show就會發現剛剛存進去的Session已經不見了。

Time out也可以從Web.config裡設定:
<sessionState timeout="42" />

這樣只要不特別設定Time outr就是42分鐘。


參考資料:
[ASP.NET]Stateful與Stateless
[MSDN]ASP.NET Cookie 概觀
[MSDN]ASP.NET 工作階段狀態概觀

回目錄
回首頁

演算法 - 基數排序法 (radix sort )

數排序(Radix sort)是一種排序演算法,它是這樣實現的:
將所有待比較數值(正整數)統一為同樣的數位長度,數位較短的數前面補零. 然後, 從最低位開始, 依次進行一次排序.這樣從最低位排序一直到最高位排序完成以後, 數列就變成一個有序序列.
基數排序的方式可以採用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由鍵值的最右邊開始,而MSD則相反,由鍵值的最左邊開始。

時間複雜度:O(n log(r)m)( r 為基數, m 為堆數 )
空間複雜度:O(n * r)

以上引用自維基百科:http://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95

以下利用 C# 程式碼示範:
Queue[] qDigits;
public void sort(int[] s)
{
    int digit = 10, i;
    init(s);
    i = Convert.ToInt32(Math.Log10((s.Max() / 1.0)));

    i--; 
    while (i-- != 0)
        radix(ref digit);
}

public void init(int[] s)
{
    resetQueue();
    foreach (int i in s)
        qDigits[i % 10].Enqueue(i);
}

public void radix(ref int digit)
{
    Queue[] qTmp = qDigits;
    int digitTen = digit * 10;
    resetQueue();
    
    foreach (Queue q in qTmp)
    {
        while (q.Count != 0)
        {
            int i = Convert.ToInt32(q.Dequeue());
            qDigits[i % digitTen / digit].Enqueue(i);
        }
    }
    digit *= 10;
}

public void resetQueue()
{
    qDigits = new Queue[10];
    for (int i = 0; i < 10; i++)
        qDigits[i] = new Queue();
}

public void print()
{
    Console.Write("content: ");
    foreach (Queue q in qDigits)
    {
        while (q.Count != 0)
            Console.Write(q.Dequeue() + " ");
    }
}
回首頁

2011年6月6日 星期一

演算法 - 堆積排序法 (heap sort )

積排序(Heapsort)是指利用堆積樹(堆)這種資料結構所設計的一種排序演算法。堆積樹是一個近似完全二元樹的結構,並同時滿足堆積屬性:即子結點的鍵值或索引總是小於(或者大於)它的父節點。

時間複雜度:O(n logn)
空間複雜度:O(1)

通常堆積樹(heap)是通過一維陣列來實現的。在起始陣列為 0 的情形中:

堆積樹的根節點(即堆積樹的最大值)存放在陣列位置 1 的地方;

  注意:不使用位置 0,否則左子樹永遠為 0[2]

父節點i的左子節點在位置 (2*i);
父節點i的右子節點在位置 (2*i+1);
子節點i的父節點在位置 floor(i/2);

以上引用自維基百科:http://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F

以下利用 C# 程式碼示範:
class Heap
{
    public int[] s;
    public int size;

    public Heap(int n, int[] s)
    {
        this.s = new int[n];
        for (int i = 0; i < n; i++)
            this.s[i] = s[i];
    }
}

class HeapSort
{
    public Heap h;

    public HeapSort(int n, int[] s)
    {
        h = new Heap(n, s);
    }

    public void sort(int n)
    {
        makeheap(n, h);
        removeKeys(n, h, h.s);
    }

    void siftdown(Heap tp, int i)
    {
        int parentIndex, lChildIndex, key;
        bool bFound;

        key = tp.s[i];
        parentIndex = i;

        bFound = false;
        
        while (leftNode(parentIndex) <= tp.size && !bFound)
        {
            if (leftNode(parentIndex) < tp.size &&
                tp.s[leftNode(parentIndex)] < tp.s[rightNode(parentIndex)])
                lChildIndex = rightNode(parentIndex);
            else
                lChildIndex = leftNode(parentIndex);

            if (key < tp.s[lChildIndex])
            {
                tp.s[parentIndex] = tp.s[lChildIndex];
                parentIndex = lChildIndex;
            }
            else
                bFound = true;
        }
        tp.s[parentIndex] = key;
    }

    int root(Heap tp)
    {
        int keyout;
        keyout = tp.s[0];
        tp.s[0] = tp.s[tp.size];
        tp.size = tp.size - 1;
        siftdown(tp ,0);
        return keyout;
    }

    void removeKeys(int n, Heap tp, int[] s)
    {
        int i;
        for (i = n - 1; i >= 0; i--)
            s[i] = root(tp);
    }

    void makeheap(int n, Heap tp)
    {
        int i;
        tp.size = (n - 1);
        for (i = (n - 1) / 2; i >= 0; i--)
            siftdown(tp, i);
    }

    int parentNode(int i)
    {
        return Convert.ToInt32(Math.Floor((i - 1) / 2.0));
    }

    int leftNode(int i)
    {
        return (2 * i + 1);
    }

    int rightNode(int i)
    {
        return (2 * i + 2);
    }
}
回首頁

2011年6月4日 星期六

演算法 - 快速排序法 (quick sort )

速排序是一種排序演算法,由C. A. R. Hoare所發展的,以平均效能來說,排序 n 個項目要Θ(n log n)次比較。然而,在最壞的效能下,它需要Θ(n2)次比較。一般來說,快速排序實際上明顯地比其他Θ(n log n) 演算法更快,因為它的內部迴圈(inner loop)可以在大部分的架構上很有效率地被實作出來,且在大部分真實世界的資料,可以決定設計的選擇,減少所需時間的二次方項之可能性。

時間複雜度:最佳 - O(n logn)、最差 - O(n2)
空間複雜度:O(n logn)

快速排序使用分治法(Divide and conquer)策略來把一個序列(list)分為兩個子序列(sub-lists)。
步驟為:

1.從數列中挑出一個元素,稱為 "基準"(pivot),
2.重新排序數列,所有元素比基準值小的擺放在基準前面,所有元素比基準值大的擺在基準的後面(相同的數可以到任一邊)。在這個分割結束之後,該基準就處於數列的中間位置。這個稱為分割(partition)操作。
3.遞迴地(recursive)把小於基準值元素的子數列和大於基準值元素的子數列排序。

遞迴的最底部情形,是數列的大小是零或一,也就是永遠都已經被排序好了。雖然一直遞迴下去,但是這個演算法總會結束,因為在每次的迭代(iteration)中,它至少會把一個元素擺到它最後的位置去。

以上引用自維基百科:http://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F

以下利用 C# 程式碼示範:
public void sort(int l, int h, int[] s)
{
    int pivotIndex = 0;

    if (h > l)
    {
        quick(l, h, ref pivotIndex, s);
        sort(l, pivotIndex, s);
        sort(pivotIndex + 1, h, s);
    }
}

void quick(int l, int h, ref int pivotIndex, int[] s)
{
    int i, j, pivotItem;

    pivotItem = s[l];
    j = l;
    for (i = l + 1; i < h; i++)
    {
        if (s[i] < pivotItem)
        {
            j++;
            swap(ref s[i], ref s[j]);
        }
    }
    pivotIndex = j;
    swap(ref s[l], ref s[pivotIndex]);
}

void swap(ref int i, ref int j)
{
    int temp;
    temp = i;
    i = j;
    j = temp;
}
回首頁

演算法 - 合併排序法 ( merge sort )

併排序(Merge sort)(另譯:歸併排序)是建立在歸併操作上的一種有效的排序演算法。該演算法是採用分治法(Divide and Conquer)的一個非常典型的應用。

歸併操作的過程如下:

1.申請空間,使其大小為兩個已經排序序列之和,該空間用來存放合併後的序列
2.設定兩個指針,最初位置分別為兩個已經排序序列的起始位置
3.比較兩個指針所指向的元素,選擇相對小的元素放入到合併空間,並移動指針到下一位置
4.重複步驟3直到某一指針達到序列尾
5.將另一序列剩下的所有元素直接複製到合併序列尾


時間複雜度:O(n logn)
空間複雜度:O(n)

以上引用自維基百科:http://zh.wikipedia.org/wiki/%E5%90%88%E4%BD%B5%E6%8E%92%E5%BA%8F

以下利用 C# 程式碼示範:
public void sort(int n, int[] s)
{
    if (n > 1)
    {
        int left = n / 2, right = n - left;
        int[] l = new int[left];
        int[] r = new int[right];
        for (int i = 0; i < left; i++)
            l[i] = s[i];
        for (int i = 0; i < right; i++)
            r[i] = s[left + i];
        sort(left, l);
        sort(right, r);
        merge(left, right, l, r, s);
    }
}

void merge(int left, int right, int[] l, int[] r, int[] s)
{
    int i = 0, j = 0, k = 0;

    while (i < left && j < right)
    {
        if (l[i] < r[j])
        {
            s[k] = l[i];
            i++;
        }
        else
        {
            s[k] = r[j];
            j++;
        }
        k++;
    }
    if (i >= left)
        for (int m = j, c = 0; m < right; m ++, c ++)
            s[k + c] = r[m];
    else
        for (int m = i, c = 0; m < left; m ++, c ++)
            s[k + c] = l[m];
}
回首頁

演算法 - 選擇排序法 ( selection sort )

擇排序(Selection sort)是一種簡單直觀的排序演算法。它的工作原理如下。首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然後,再從剩餘未排序元素中繼續尋找最小元素,然後放到排序序列末尾。以此類推,直到所有元素均排序完畢。

時間複雜度:O(n2)
空間複雜度:O(1)

以上引用自維基百科:http://zh.wikipedia.org/wiki/%E9%81%B8%E6%93%87%E6%8E%92%E5%BA%8F

以下利用 C# 程式碼示範:
public void sort(int n, int[] s)
{
    int i, j, flag;
    for (i = 0; i < n - 1; i++)
    {
        flag = i;
        for (j = i + 1; j < n; j++)
            if (s[j] < s[flag])
                swap(ref s[j], ref s[flag]);
    }
}

void swap(ref int i, ref int j)
{
    int temp;
    temp = i;
    i = j;
    j = temp;
}
回首頁

演算法 - 插入排序法 ( insertion sort )

入排序(Insertion Sort)的演算法描述是一種簡單直觀的排序演算法。它的工作原理是通過構建有序序列,對於未排序數據,在已排序序列中從後向前掃描,找到相應位置並插入。插入排序在實現上,通常採用in-place排序(即只需用到O(1)的額外空間的排序),因而在從後向前掃描過程中,需要反覆把已排序元素逐步向後挪位,為最新元素提供插入空間。

時間複雜度:O(n2)
空間複雜度:O(1)

一般來說,插入排序都採用in-place在數組上實現。具體演算法描述如下:

1.從第一個元素開始,該元素可以認為已經被排序
2.取出下一個元素,在已經排序的元素序列中從後向前掃描
3.如果該元素(已排序)大於新元素,將該元素移到下一位置
4.重複步驟3,直到找到已排序的元素小於或者等於新元素的位置
5.將新元素插入到該位置中
6.重複步驟2

如果比較操作的代價比交換操作大的話,可以採用二分查找法來減少比較操作的數目。該演算法可以認為是插入排序的一個變種,稱為二分查找排序。


以上引用自維基百科:http://zh.wikipedia.org/wiki/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F

以下利用 C# 程式碼示範:
public void sort(int n, int[] s)
{
    int i, j;
    int x;
    for (i = 1; i < n; i++)
    {
        x = s[i];
        j = i - 1;
        while (j >= 0 && s[j] > x)
        {
            s[j + 1] = s[j];
            j--;
        }
        s[j + 1] = x;
    }
}
回首頁