カレイドスコープ: 10月 2009

2009年10月22日星期四

Longest Common Subsequence (LCS)

Longest Common Subsequence，中文可以稱做最長子序列，這個問題的定義如下：

給定兩個序列，求其最長相同的子序列。此問題和Longest Common Substring不同，Substring中間不可以有斷點，但是subsequence可以。

問題分析：

令序列1為S1，序列2為S2
令S1 = Sub1 + elm1, S2 = Sub2 + elm2
其中elmi就是我們要求的LCS，因此有四個可能
1. elm1是LCS的一部分而elm2不是
2. elm2是LCS的一部分而elm1不是
3. elm1, elm2都是LCS
4. elm1, elm2都不是LCS

寫程式的話，就依照Dynamic programming的方式，依次的填入表格就可以，但是如何找出我們要的LCS呢？這須要back tracing才有辦法。留著下回分解吧(如果我有空的話..>"<)。

程式碼如下:

#include <iostream>
#include <iostream>
#include <iostream>
#include <iostream>
using namespace std;
void lcs(string& s, string& t);
void lcs(string& s, string& t) {
    unsigned int** c = new unsigned int*[s.length()];
    for(unsigned int i = 0; i < s.length(); ++i) {
        c[i] = new unsigned int[t.length()];
    }
    for(unsigned int i = 0; i < s.length(); ++i) {
        for(unsigned int j = 0; j < t.length(); ++j) {
            c[i][j] = 0;
        }
    }
    for(unsigned int i = 1; i < s.length(); ++i) {
        for(unsigned int j = 1; j < t.length(); ++j) {
            if(s[i] == t[j]) {
                c[i][j] = c[i-1][j-1] + 1;
            } else {
                c[i][j] = max(c[i][j-1], c[i-1][j]) ;
            }
        }
    }
    for(unsigned int i = 0; i < s.length(); ++i) {
        for(unsigned int j = 0; j < t.length(); ++j) {
            cout << c[i][j] << " ";
        }
        cout << endl;
    }
}

int main(int argc, char* argv[])
{
    
    char szs[1024] = {0}, szt[1024] = {0};
    string s, t;
    cout << "please a string without white space.." << endl;
    cin.getline(szs, 1024);
    s = szs;
    s.insert(s.begin(), '0');
    cin.getline(szt, 1024);
    t = szt;
    cout << "please a string without white space.." << endl;
    t.insert(t.begin(), '0');
    cout << "counting..." << endl;
    lcs(s, t);
	return 0;
}

2009年10月20日星期二

PS Tray Factory

好用的PS Tray Factory，可以把一堆在系統圖示上的icon全都收在一起，這樣看起來System Tray就乾淨多了不是嗎？其實把tray icon收起來的功能在Windows 7上面也有喔，但PS Tray Factory的功能比較多，而且可以把最小化後的application也收進去，但是不太穩定，在還沒有換Win7之前，就先用這個吧...

PS: 這套軟體是要付錢的...

2009年10月19日星期一

#P-Complete

A problem is #P-complete if and only if it is in #P, and every problem in #P can be reduced to it by a polynomial-time counting reduction.

難嗎，其實還好，定義看上去很簡單，只是要找到問題有點難。#P-Complete的難度比起NP-Complete的難度，是在之上，或是和此問題的一樣難。

證明的流程如下：

找一個polynomial-time的function使得這個問題的(每一個)解，可以使用這個function對應到另一個己被證實的#P-complete上面。

看起來和NP-Complete很像對吧。難度在於"每一個"解。也就是說#P的意思在於counting all solutions.

# = number就對啦...

目前已被證實為#P-Complete的問題並不多，因為要找到一個NP-Complete的解就不簡單了，更何況是算出有多少解。

這裡有一個迷思就是，我可以不用知道所有的解，而算出解的個數嗎!?

也許這是另一種解#P-Complete的方法，但是.還是沒有人提出這樣的證明，因為#P-Complete的難度，至少有NP-Complete這麼難...

研究所二年級時，每天都在看這問題..看過的有..

Counting LCS is #P-complete. Counting random walk solutions is #P-Complete. Counting SAT solutions is #P-Complete.

所以我們幾乎可以說，只要一個問題是NP-Complete，那麼記算他所有的解"應該"就是#P-Complete。至於為什麼用應該呢？因為上面有說過了，說不定有公式求個數解..

於是，只要找到一個plynomial time的解法解出#P-Complete，那麼NP=P, P=PH..

哪有可能找到..2SAT不落於NP-Complete但Counting 2SAT都是#P-Complete了..所以難度的成長快很多..還是等哪位天才快來證明NP!=P吧..

2009年10月22日 星期四