Pages

2012年6月10日 星期日

[演算法] Floyd-Warshall 演算法

以下記錄我研究著名的 Floyd-Warshall 演算法自己整理的心得:

Floyd-Warshall Algorithm
1.   在All-Pairs Shortest Path的問題中,為了減低 DP 的時間複雜度,可使用Floyd-Warshall演算法。這種演算法,在edge weight為正或負時皆可實行。

2.   假如要從 i 節點走到 j 節點,且中間有可能經過 k 個中間節點(intermediate vertex)。那麼從 i 到 j 的最短路徑長度等於(設中間節點數目不等於0):

min { (i 不經過第 k 個 intermediate vertex但有經過其他k-1個intermediate vertex 走到 j 的最短路徑) , (先到第 k 個intermdiate vertex 且經過其他 k-1個中間節點的最短路徑 + 由第 k 個點過 k-1 個 intermediate vertex 到達 j 的最短路徑) }

如圖所示:
Floyd
整體而言就是決定是否要經過第 k 個點而已。如果經過第 k 個 intermediate vertex會讓總長度變小,那麼就選擇經過第 k 個點。如果 k = 0 當然最短路徑長就是 i 跟 j 之間的 weight。

3.   predecessor matrix 裡存的是到達 j 點時, j 點的前一個 vertex 是誰。這又分為兩種情況,如果最短路徑是不經過第 k 點的,那麼predecessor matrix要檢查的區間就是 i~j 之間(經過k-1個intermediate vertex),反之有經過第 k 點,檢查區間為 k~j 之間(經過k-1個intermediate vertex)。

[演算法] Constraint graphs

以下整理Constraint Graph的觀念:
1.   Ax <= b,Constraint graph的vertices數目為x向量內元素個數+1。
2.   額外多出來的vertex為v0,目的為確保vertex之間都能互通。
3.   Constraint graph中的edge對應一組Constraint。
4.   weight的表示法:w(vi,vj) = bk,代表xj - xi = bk。(i、j、k為下標的index)。
5.   只要用找出v0到各vertex的shortest path的方法,且不能有負的edge weight,就可以找出每個vertex對應的xi的解。

2012年5月27日 星期日

[Vim] 複製、貼上、搜尋、復原


Vim的複製、貼上、搜尋是簡單的指令,也是常用的指令:
        選擇一段文字,可以在一般模式下鍵入大寫V,或者小寫v來選擇文字區塊。鍵入大寫V是游標經過一行就選擇一行,小寫v則是游標經過的位置就選擇起來。
        選擇好文字區塊後,按下小寫y可以複製起選擇的文字,按下d可以刪除掉選取的文字。
        在想要貼上文字的地方,按下p就可以貼上剛才複製好的文字。
        如果要復原剛才的動作,可以在一般模式下鍵入u。
        要搜尋字串,可以在一般模式下輸入"/",並在斜線後方鍵入要搜尋的字串,並按下Enter。當找到一個符合的字串後,若要繼續往下搜尋,可以鍵入小寫n。

[嵌入式系統] Linux kernel內的資料Export到外部


在撰寫嵌入式系統的驅動程式(以linux為系統)時,我們有時候需要將kernel內的變數Export給我們自己撰寫的驅動程式,也就是我們可以在Linux的kernel內定義extern變數或函式,來給外部自己定義的module使用。
要將變數或函式Export給外部使用,必須做以下2個步驟:
1.   用EXPORT_SYMBOL()函式,將自己定義的Variable1匯出給外部使用。例如我們可以在 linux/kernel/net/netsyms.c內,將Variable1 Export出來:
//要先 #include <linux/module.h>
int Variable1 = 0;
EXPORT_SYMBOL(Variable1);
可以研究一下netsyms.c這個檔案,裡面會發現都是整理一系列的EXPORT_SYMBOL的動作。

2.   在kernel內的檔案內定義extern的變數,將剛剛Export出來的變數,直接拿來操作。
例如在for PCM7230的linux kernel內,可以在linux/kernel/net/core/dev.c內定義extern:
extern int Variable1;
接著就可以將Variable1拿來使用了。
在自己撰寫的驅動程式裡面,也可是一樣先在變數前寫上"extern",就可以操作從kernel導出的變數。我們可以在驅動程式的程式碼內,修改從kernel Export出來的變數,也可以用create_proc_entry函式新增一個程序在linux的文件系統 /proc 裡面,並且將create_proc_entry函式回傳的指標,來將這個程序的參數,指定為在驅動程式的程式碼內自己定義的函式。

2012年3月4日 星期日

[Bug研究] Merge Sort的Bug

        我寫過很多次Merge Sort,有時寫完會有一些Bug。
以下是我這次用C++寫的一個有Bug的Merge Sort函式,這個錯誤一開始我並沒有很快找出:


   1: void MergeSort(int *A, int p, int r)
   2: {
   3:      int q = 0;
   4:      if(p<r)
   5:      {
   6:             q = ((p+r)/2);
   7:             MergeSort(A,p,q);
   8:             MergeSort(A,q+1,r);
   9:             Merge(A,p,q,r);
  10:      }
  11: }
  12: void Merge(int *A, int p, int q, int r)
  13: {
  14:      int n1 = q-p+1;   //number of elements of left array. Include q.
  15:      int n2 = r-q;     //number of elements of right array.
  16:      int L[n1+1];
  17:      int R[n2+1];
  18:      
  19:      for(int i=0;i<n1;i++)
  20:      {
  21:              L[i] = A[p+i];
  22:      }
  23:      for(int j=0;j<n2;j++)
  24:      {
  25:              R[j] = A[q+j];
  26:      }
  27:      L[n1] = infinite;
  28:      R[n2] = infinite;
  29:      int i = 0;  int j = 0;
  30:      
  31:      for(int k=p;k<=r;k++)
  32:      {
  33:              if(L[i]<=R[j])
  34:              {
  35:                  A[k] = L[i];
  36:                  i++;
  37:              }
  38:              else
  39:              {
  40:                  A[k] = R[j];
  41:                  j++;
  42:              }
  43:      }
  44: }




這個程式執行結果會是錯的,原因是第25行:
  25:              R[j] = A[q+j];

在複製陣列內容到R array時,應該要寫:
  25:              R[j] = A[q+j+1];
因為L陣列裡面已經包含index為 q 的element了。只要更改這一行,就是一個完整的Merge Sort的code了。

我將這種bug歸類為"陣列index的錯誤問題"。這種bug通常簡單,但簡單的錯誤難免發生。為了避免類似的錯誤,我之後將會使用特定格式的註解(先將此註解法則命名為Uncle註解法好了...),來表示出陣列操作時的操作範圍,例如
,以此Merge Sort為例:
   
      R[j] = A[q+j+1];       // A[] : q+1<->q+n2 // j : 0<->n2-1 // total # : n2

上面這一行的註解中 A[] : q+1<->q+n2代表陣列A的索引值在for迴圈中從q+1一直trace到q+n2範圍,每一部分的註解描述用雙斜線 "//" 分開,j : 0<->n2-1代表j從0一直到n2-1,最後 total # : n2代表整體迴圈操作次數有n2+1次操作。

一直以來我都想定義一個共同的註解規範,能夠註解的格式統一,方便debug,我希望從現在開始實現這個願望,目前註解法的格式還在制定中。

2012年3月3日 星期六

[演算法] Loop Invariants

        Loop Invariant 是證明某個不變的條件(稱為Invariant Condition),這個條件在程式進入迴圈前跟進入迴圈後,此條件仍不變。

通常以while迴圈為例子。
假如有一個while迴圈如下:

while( A )
{
        //Body..
}

        那麼假設一個 Invariant 條件叫做 X ,這個X條件在while檢查A條件時都維持原狀,一進入Body 時可能改變X條件,但一執行完 Body 後 X 又恢復原貌,這種條件就是一個典型的 Invariant Condition。

  • 證明Loop Invariant需要三個步驟:
    1.   Initialization:描述 Invariant Condition 在迴圈執行第一個 iteration前,就成立。
    2.   Maintenance:描述 Invariant Condition 在迴圈的任一iteration執行前跟執行後都維持成立。
    3.   Termination:迴圈執行結束後,Invariant Condition 能夠展示整體演算法的正確性。

[演算法] 以UVA第10107程式題目複習Insertion Sort

首先複習一下 Insertion Sort。

Insertion Sort       
Insertion Sort的精神是當在排序一個數字陣列時,每當處理一個數字,就代表在這個數字之前的數都已經排序好了。因此只需要將這個數字跟前面排好的數字序列比較,並將目前處理的這個數字insert到之前排序好的序列中,就像一般在玩撲克牌時通常會使用的排序法。

        以下是我練習將InsertionSort的Code用C++寫出:
void InsertionSort()
{
     int key = 0;
     for(int j=1;j<size;j++)
     {
             key = data[j];
             int i = j-1;
             while(i>=0 && data[i]>key)
             {
                        data[i+1] = data[i];
                        i--;
             }
             data[i+1] = key;
     }
}
UVA #10107(What is the median)
這個題目給的Sample Input跟Sample Output如下:

Sample Input

1
3
4
60
70
50
2

Sample Output

1
2
3
3
4
27
4
        本題的目標為每從Sample Input讀進一個數字到序列中,就找出當下的中位數(median),如果總共有奇數個數字,則將取排序好的數列的中間兩個數字相加除以2,除以2後只取整數部分。
思考方式:
使用Insertion Sort的原因,是因為這題是每讀到一個數字就做排序,所以當讀進一個新數字時,之前的讀過的數字都已經排序好了,所以只須將新讀入的數字Insert到前面排序好的序列的適當位置,這很符合Insertion Sort的基本概念。
以下是我解決此題目的Code:(implement using C++)

//main.cpp
//The excution result is correct, and is accepted by UVA Online Judge.
//This is the code for UVA Online Judge #10107
//This code was created by Uncle on 2012/03/03
#include<iostream>
#include<sstream>
#include<fstream>
using namespace std;
int *data = NULL;
int size = 0;

int *Expand(int *arrReceive,int &s,int key)
{
    int *newArr = new int [s+1];
    for(int i=0;i<s;i++)
    {
        newArr[i] = arrReceive[i];
    }
    newArr[s] = key;
    delete []arrReceive;
    s++;
    return newArr;
}
void InsertionSort()
{
     int key = 0;
     for(int j=1;j<size;j++)
     {
             key = data[j];
             int i = j-1;
             while(i>=0 && data[i]>key)
             {
                        data[i+1] = data[i];
                        i--;
             }
             data[i+1] = key;
     }
}
int main()
{
    int key;
    ifstream inputFile;
    //inputFile.open("input.txt",ifstream::in);
    while(cin >> key)
    {
                    data = Expand(data,size,key);
                    InsertionSort();
                    if(size%2)  //total size is odd
                    {
                              cout << data[size/2] << endl;
                    }
                    else
                    {
                        int tmp = data[(size/2)-1] + data[size/2];
                        tmp = tmp/2;
                        cout << tmp << endl;
                    }
    }
    //getchar();
    return 0;
}