TOC

圖論 Graph Theory

G(V, E)

  • 由頂點(vertex, node)和連接頂點的邊(Edge)關聯成的圖形
  • 其中關聯分作有方向性(directed)及無方向性(undirected)
  • 須考慮最大流問題(maximum flow)

在程式語言有幾種方式來建構Graphs:

相鄰矩陣 adjacency matrixes

image
圖片來源

陣列 edge list representation

應用

  • 最短路徑演算法 Shortest Path Algorithm: GPS, 高頻交易
  • 生成樹協定 Spanning Tree Protocol, STP
  • 爬蟲

參考:
Flow Networks:Maximum Flow & Ford-Fulkerson Algorithm

廣度優先搜尋 Breadth-first Search, BFS

  • 時間複雜度:O(V+E)(分別遍歷所有節點和各節點的所有鄰居)
  • 空間複雜度:O(V)(Queue中最多可能存放所有節點)
  • 用於有效率的迭代(traversal)
  • 迭代的方式為鄰近的先訪問(level-ordered)
  • 劣勢在於儲存指標記憶體空間,有時用DFS替代
  • 使用FIFO的Queue來實作,Queue為空代表完成迭代

應用

  • machine learning
  • Edmonds-Karp演算法
  • Cheney演算法

以Python實作,輸出請參考gist

參考:
Graph: Breadth-First Search(BFS,廣度優先搜尋)

深度優先搜尋 Depth-first Search, DFS

  • 時間複雜度:O(V+E)
  • 空間複雜度:O(logV)(訪問至末端節點後LIFO,Stack最多只會同時存在logV個節點,也就是樹的高度)
  • 為了解Maze Problem而生的演算法
  • 效能比BFS稍佳
  • 使用LIFO的Stack來實作

應用

  • 拓撲排序 Topological Order
  • Kosaraju演算法: 推薦系統 Recommand System
  • 判斷Grapth是否有cycle(DAG)
  • Maze

以Python實作,輸出請參考gist

參考:

最短路徑演算法 Shortest Path

  • 主要用於找出Graph中兩節點之間的最短路徑
    • 已知起點或終點,求最短的遍歷:DijkstraBellman-Ford
    • 求某起點到某終點的最短路徑:A* search
    • 找全局最短路徑:Floyd-Warshall

最短路徑的應用

  • GPS
  • Routing Imformation Protocal, RIP
  • Avidan-Shamir method

先實作以下DijkstraBellman-Ford演算法會用到的類別:Node、Edge

image
圖片來源

Dijkstra

  • 使用Priority Queue(Heap)能達到時間複雜度:O(V*logV + E)
  • 通常用Max binary heap、Fibonacci heap、Priority queue來實現
  • 是一種貪婪式演算法(都以目前的最短路徑去計算cost),同時可獲得最佳解
  • 邊的權值一定要為正值(positive weight edge)
  • relax a single edge at the same time

Pseudo code請參考gist

以Python實作,輸出請參考gist

Bellman-Ford

  • 時間複雜度:O(V*E)
  • 效能比Dijkstra差,但能處理負邊(negtive weight edge)
  • relax all edges at the same time for V-1 iteration
  • 迭代針對每個邊做負環(negtive cycle, path的cost小於0)的檢查

應用

  • cycle detection
  • argitrage situations

Pseudo code請參考gist

以Python實作,輸出及負環測試請參考gist

有向無環圖 Directed Acyclic Graph, DAG

  • 沒有環,相較於有環圖能更快找到最短路徑
  • 藉由拓樸排序(Topological),找到最短路徑的時間複雜度:O(E+V)
  • 正負邊皆能處理
  • 效能比DijkstraBellman-Ford都好

應用

  • 解決背包問題(Kanpsack-problem)

參考:

生成樹 Spanning Tree

  • 從Graph取出一棵樹,可能有多種組合
  • 樹的權重:所有邊的權重總和
  • 最小生成樹:圖中權重最小的生成樹

生成樹的應用

  • Big Data
  • Clustering

Kruskal

  • 貪婪式演算法
  • 使用disjoint set或heap實作
  • 時間複雜度:O(N*logN)(迭代時檢查cycle),最差的結果是O(E*logE)

image

以Python實作,Edge、Node、Disjoint Set類別實作與輸出請參考gist

keon/algorithms/graph/minimumspanningtree.py有更簡易的實作

排序演算法 Sorting Algorithms

  • 比較排序(comparision)
    • bubble sortinsertion sortselection sortmerge sortquicksort
    • lower bound: 最少要付出O(NlogN)來排序
  • 非比較排序(non-comparision)
    • radix sortbucket sort
    • lower bound最佳可至O(N)
  • 適應性(Adaptive)排序:
    • 運用input已有的順序,節省比較次數
    • O(NlogN)~O(N)
  • 根據記憶體的使用分為:
    • in-place
    • stable: 當資料中有相等數值的兩元素,經過排序之後是否能夠保持原有的相對位置
    • recursive

主要的精神為比較、對調:

冒泡排序 Bubble Sort

  • 平均時間複雜度: O(N^2)
  • stable、in-place

選擇排序 Selection Sort

  • 平均時間複雜度: O(N^2)
  • 適用長度小的陣列(長度10~20),效能甚至比quicksort、mergesort佳
  • 寫入次數較插入排序要少
  • in-place

插入排序 Insertion Sort

  • 平均時間複雜度: O(N^2)
  • 適用長度小的陣列(長度10~20),效能甚至比quicksort、mergesort佳
  • 寫入次數較選擇排序多
  • in-place、stable

快速排序 Quick Sort

  • 屬分治法(divide and conquer algorithm),可以由遞迴來實作
  • 時間複雜度:O(N^2)~O(NlogN)
  • in-place

合併排序 Merge Sort

  • 屬分治法(divide and conquer algorithm),可以由遞迴來實作
  • 時間複雜度: O(NlogN)
  • 空間複雜度: O(N),merge時需要配置額外記憶體
  • stable
  • 適合用來排序linked list

image

堆積排序 Heap Sort

請參考Heap

混合式算法 Hybrid algorithms

  • 旨在解決同一個問題,但提昇整體演算法效能
Time Complexity Memory Stable
Quicksort quadratic time O(N^2)~O(NlogN) in-place, O(logN)~O(N) No
Heapsort O(NlogN) in-place, O(1) No
Merge sort O(NlogN) O(1)~O(N) Yes

內省排序 Intro Sort(used by Python)

  • 當遞迴深度超過一定深度由quicksort切換至heapsort

Tim Sort(used by Python)

  • 當超過一定長度由insertion sort切換至merge sort

Non-comparision based sorting

  • 時間複雜度最佳能至O(N)

計數排序 Counting Sort

  • 只適用於排序整數
  • 時間複雜度:O(N+k),k=max-min+1
  • 所需的長度取決於資料範圍k,範圍大會佔用許多記憶體

請參考keon/algorithms

基數排序 Radix Sort

  • 時間複雜度:O(k*N),k=digit length of the number
  • stable
  • 依排序順序分成LSD(least-significant-digit-first)及MSD(most-significant-digit-first)

請參考keon/algorithms

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。