演算法設計方法
逐步改良法:只使用循序,選擇,重覆三步驟設計
切割征服法:將問題切割,在以相同方式處理,在把各結果合併,適用在遞迴
貪婪法:一種階段性方法,主要核心為選擇程序,適用在有限制條件最佳化的簡單問題
動態規畫法：主要核心是遞迴關係式和最佳化原則，適用在有限制條件最佳化的複雜問題
回溯法:採depth first search(深度優先搜尋)內含遞迴結構及state space tree(狀態空間樹),適用在排列或部份集合問題
分枝限制法:採breadth first search(廣度優先搜尋)內含迴圈結構及state space tree和bounding(邊界) function,適用在排列或部份集合問題
……………………………………………………..
greedy method(貪婪法)
說明:一種階段性方法,在各階段逐一檢查一個輸入是否適合加入答案中,重複經過多個階段後,即可順利獲得最佳解
適用:具有限制條件的最佳化問題的演算法
具有限制條件的最佳化問題:可將問題成為一個objective function(目標函數)與一些constraint(限制) function的式子
核心:stages(階段性)的設計過程，selection procedure(選擇程序)
做法:根據問題的目標函數找出一個選擇程序,再根據這個程序選取最佳的輸入,若可符合限制寒數則加入此輸入.各階段可重覆上述並最後得到最佳解
常見:
optimal merge pattern(最佳化合併問題)
將n個己排序資料段run,合併成一個己排序好的資料段,同時需要讓合併成本最小
optimal storage on tapes(最佳化磁帶儲存問題):
將n個程式儲存到一個磁帶上,讓往後每個程式的平均存取時間能夠最小
前面的程式長＝後面程式和磁帶讀寫頭之間距離,因此把長度小的程式放在前面即可讓平均存取時間最小(就是由小到大排序)
最佳化中央處理器規劃問題:
如何分配中央處理器給多個正等待執行的process工作元,讓所有工作元的平均等待時間最佳
前面的工作元執行時間＝後面工作元的等待時間,因此先執行時間最短的工作元即可讓平均等待時間最小(就是由小到大排序)
knapsack problem(背包問題):
n個物品和有限制重量的背包,各物品有重量和利潤,找出不超過背包限重下放入物品的最大利潤(物品可被切割)
將利潤重量比最大的逐一放入背包,但不要超過限重即可,複雜度為O(n*2底log n)
job sequencing with deadline(最後期限工作規畫問題):
n個有最終期限和利潤的工作,在最終期限下,安排工作的執行順序以獲得最大利潤
minimum cost spanning tree(最小成本擴張樹):
找出一張加權圖裡所有邊的加權總和是最小的擴張樹
kruskal方法:
1取最小加權的邊,若此邊不會形成迴路則加入當樹邊(2底log(e))
2一直到邊都取完(e),整個複雜度等級為O(e*2底log(e)),(以邊為處理對象)
用堆積結構表示邊的加權,取出最小加權邊的複雜度為O(2底log(e)),最差情況是邊的個數為n*(n-1)/2,也就是任兩點都有一個邊
prim方法:將第一點視為樹
1樹開始選鄰近最小加權邊加入形成點多一點的樹(n)
2重覆步驟1直到成為具有N個點的樹(n-1),(以點為處理對象)
sollin方法:各點視為一樹
1對每顆樹找出與其它樹間最小加權的邊加入當成樹邊,兩樹找出的邊相同則去除其中一邊(e)
2重覆步驟1到只有一棵樹(2底log(n))
shortest path(最短距離路徑):
一點到其他所有點之間的最短路徑與距離
dijkstra方法：
1………….
2重覆步驟1(n-1),複雜度為O(N^2)
只適用邊上加權為正的圖形
bellman-ford方法(動態規畫法)：
1……….考慮所有的邊(E)
2重覆步驟1(n-1),複雜度為O(n*e)
可適用邊上加權是負的所有情況
………………………………………………………..
dynamic programming(動態規劃法)
適用:無法找到選擇程序的複雜最佳化問題
說明:需要將最佳化問題的目標寒數表示成為一個遞迴關係式,並採forward approach(前進順序)或backward approach計算
會使用表格將子問題的計算結果加以儲存,在後面階段若要用在從表格中取出使用
需遵守最佳化原則,也就是各輸入的計算都必須是根據其餘輸入的最佳結果再進一步計算
核心:principle of optimality(最佳化原則),recurrence relation(遞迴關係式)
常見:
longest common subsequence problem(最長共同子字串):
找出兩個字串中具有最大長度的子字串
做法:找出遞迴關係式與最佳化原則,再用後退順序計算即得最佳解
假設x=(x1,x2,…xm),y=(y1,y2,….yn)表示兩個長度分別是m與n的字串,len=字串x與y最長共同子字串的長度
遞迴關係式:len={
0,if m=0 or n=o
len+1 , if m,n>0 and x_m=y_m
max(len,len) , if m,n>0 and x_m != y_m
執行過程的遞迴樹深度為O(m+n)
子問題個數為O(m*n),因執行過程要考慮兩個字串所有不同的長度
演算法：…..
multistage graphs(多階圖形):
在頂點分為k個階段的有向加權圖中,找出第一階段的起始點到第k階段的目的點最短路徑
all pairs of shortest path(任意兩點最短距離路徑):
在有向加權圖中,找出任意兩點間的最短距離路徑
0/1背包問題:
同背包問題,但物品不可被切割,屬於部份集合問題
遞迴關係式:f_n(m)=maximum{f_n-1(m),f_n-1(m-weight_n)+profit_n},n=第n個物品,m=最大限重,f_n(m)=n個物品在m下具有最大利潤
演算法則:(複雜度=O(2^n),遞迴關係式=t(n)=2t(n-1)+c,if n>0)
#define limit 重量限制;
#define n 個數;
int p[n]=利潤,w[n]=重量;
int choose[n]=是否選取; //初始值為0
int f(int n,int weight,int profit){
int no,yes;
if(n==0&&weight>limit)return(0); //超過重量，利潤為0
else if(n==0)return(profit); //終止條件，回傳利潤
else{
no=f(n-1,weight,profit); //不選第n件物品的利潤
yes=f(n-1,weight+w[n],profit+p[n]); //選的利潤
if(no>yes){ //回傳較大的利潤
choose[n]=0;
return(no);
}else{
choose[n]=1;
return(yes);
}
}
}
optiomal binary search tree(最佳二元搜尋樹):
…….?
the traveling saleperson problem(旅行推銷員問題):
一推銷員從城市出發,將各城市走訪一次最後回到原城市(找出一個最小成本的迴路)
n=n個頂點,cost=由編號i的點經過點集合v中所有點,再到達出發點的最短距離
遞迴關係式:cost=minimum{weight+cost},j屬於v
cost=(weight)點i到達所有可能的頂點j之間的距離+(cost)點j 到達出發點的最短距離路徑,選擇其中最小者得到最短距離路徑
……………………………………………………………………………….
backtracking(回溯法)
適用:被歸列為排列問題或是部份集合問題，或是具限制條件的最佳化問題
核心:將問題表示成一個state space tree(狀態空間樹)與深度優先搜尋
說明:問題的解答可表示成為一個具有n個項的向量(x1,x2,…xn),同時將問題表示成一個狀態空間樹，
各節點表示問題的各狀態,樹根表起始狀態,樹葉表最終狀態,分支度表示解答中的某個項xi,1<=i<=n可能具有的範圍,
再對狀態空間樹由樹根開始進行深度優先搜尋,從可能答案中找出符合條件的解
應用:
8queen problem(八個皇后問題):將八顆西洋棋皇后棋子放在棋盤中,但彼此不能在同對角線與同行同列,有8!種可能的狀態空間
sum of subset(部份集合之問題):在n個整數中,找出加起來=m的部份組合,有2^n種可能的狀態空間
0/1背包問題:同上
hamiltonian cycles(漢米爾敦迴路問題):在n個點的有向圖中,從某點出發經過各點一次在回到起點的迴路,有n!種可能的狀態空間
graph coloring(圖形著色問題):在n個圖形中找出一種著色方法,讓圖形中任兩相鄰點都具有不同的顏色
……………………………………………………………………………….
branch and bound(分支限制法)
核心:狀態空間樹,廣度優先搜尋
說明:將問題表示成狀態空間並使用廣度優先搜尋對此樹中各節點進行檢查,並用bounding function(邊界函數)用來刪除一些不必要的子樹搜尋
並根據使用佇列或堆疊協助儲存節點,可分成FIFO search(先進先出搜尋)與LIFO search(後進先出搜尋),若加入成本寒數則稱為LC search(最小成本搜尋)
best-first search with branch-and-bound pruning:在分支限制法中給與狀態空間樹各點一個評估值,父節點可依值決定那個子節點先走訪
breadth-first search with branch-and-bound pruning:在分支限制法中使用廣先搜尋順序走訪狀態空間樹各點,因沒用評估值決定走訪順序所以效率較差
應用:
puzzle problem(數字鍵盤問題):在x*y的方框中,將數字依序排列,可能狀態有x*y!個
最後期限工作規畫問題:同上,可能狀態有2^n個,屬部分集合問題
game tree(遊戲樹):可將一遊戲部份狀態表示出來的樹,再由其中決定下一步該如何走才能獲勝,屬於回溯法和分支限制法較複雜的應用