Voronoi Diagram

網路上論Voronoi Diagram的文章不多(中文), 但國外倒是很多這樣子的文章在討論, 這問題是由Voronoi解掉的, 其實用於細胞及一些最近群組的問題是非常有用的..

Longest Common Subsequence (LCS)

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

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

問題分析：

 

1. 令序列1為S1，序列2為S2
2. 令S1 = Sub1 + elm1, S2 = Sub2 + elm2
3. 其中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>

#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吧..

 

Sorting Algorithm, 排序演算法

在資工的世界裡，第一個要學的演算法就是排序，而這也是進入演算法的一個開始，世上到底有多少排序的方法呢？其實很多，而且大多數都不在教科書上出現。有興趣的人可以上Wiki找一下，可以看到很多不同種的排序及時間。大部分會教的有Bubble Sort，Selection Sort，Insertion Sort，Merge Sort，Heap Sort，Quick Sort。在不同的應用上，比較常見的有Bubble Sort，Heap Sort及Quick Sort，原因無他，都是因為實作方便及好維護。至於時間上的考量，一般來說會使用Quick Sort及Heap Sort，但因為Quick Sort在Worst Case中是O(n^2)，所以很多情形下，還是比較偏好Heap Sort。

Bubble pseudo code:

procedure bubbleSort( A : list of sortable items ) defined as:
  n := length( A )
  do
    swapped := false
    n := n - 1
    for each i in 0 to n - 1  inclusive do:
      if A[ i ] > A[ i + 1 ] then
        swap( A[ i ], A[ i + 1 ] )
        swapped := true
      end if
    end for
  while swapped
end procedure

Heap pseudo code:

 function heapSort(a, count) is
     input: an unordered array a of length count

     (first place a in max-heap order)
     heapify(a, count)

     end := count - 1
     while end > 0 do
         (swap the root(maximum value) of the heap with the last element of the heap)
         swap(a[end], a[0])
         (put the heap back in max-heap order)
         siftDown(a, 0, end-1)
         (decrease the size of the heap by one so that the previous max value will
         stay in its proper placement)
         end := end - 1

function heapify(a,count) is
     (start is assigned the index in a of the last parent node)
     start := (count - 2) / 2
    
     while start ≥ 0 do
         (sift down the node at index start to the proper place such that all nodes below
         the start index are in heap order)
         siftDown(a, start, count-1)
         start := start - 1
     (after sifting down the root all nodes/elements are in heap order)

function siftDown(a, start, end) is
     input: end represents the limit of how far down the heap
                   to sift.
     root := start

     while root * 2 + 1 ≤ end do          (While the root has at least one child)
         child := root * 2 + 1           (root*2+1 points to the left child)
         (If the child has a sibling and the child's value is less than its sibling's...)
         if child + 1 ≤ end and a[child] < a[child + 1] then
             child := child + 1           (... then point to the right child instead)
         if a[root] < a[child] then       (out of max-heap order)
             swap(a[root], a[child])
             root := child                (repeat to continue sifting down the child now)
         else
             return

Quick pseudo code:

 function quicksort(array)
     var list less, greater
     if length(array) ≤ 1 
         return array 
     select and remove a pivot value pivot from array
     for each x in array
         if x ≤ pivot then append x to less
         else append x to greater
     return concatenate(quicksort(less), pivot, quicksort(greater))

  function partition(array, left, right, pivotIndex)
     pivotValue := array[pivotIndex]
     swap array[pivotIndex] and array[right] // Move pivot to end
     storeIndex := left
     for i from left to right − 1
         if array[i] ≤ pivotValue
             swap array[i] and array[storeIndex]
             storeIndex := storeIndex + 1
     swap array[storeIndex] and array[right] // Move pivot to its final place
     return storeIndex

 procedure quicksort(array, left, right)
     if right > left
         select a pivot index (e.g. pivotIndex := left)
         pivotNewIndex := partition(array, left, right, pivotIndex)
         quicksort(array, left, pivotNewIndex - 1)
         quicksort(array, pivotNewIndex + 1, right)

相關的程式碼，寫好再放上...