Divide and Conquer - 分治法

在計算機科學中,分治法是一種很重要的演算法。分治法即『分而治之』,把一個複雜的問題分成兩個或更多的相同或相似的子問題,再把子問題分成更小的子問題……直到最後子問題可以簡單的直接求解,原問題的解即子問題的解的合併。這個思想是很多高效演算法的基礎,如排序演算法(快速排序,合併排序)等。

分治法思想

分治法所能解決的問題一般具有以下幾個特徵:

  1. 問題的規模縮小到一定的程度就可以容易地解決。
  2. 問題可以分解爲若干個規模較小的相同問題,即該問題具有最優子結構性質。
  3. 利用該問題分解出的子問題的解可以合併爲該問題的解。
  4. 該問題所分解出的各個子問題是相互獨立的,即子問題之間不包含公共的子問題。

分治法的三個步驟是:

  1. 分解(Divide):將原問題分解爲若乾子問題,這些子問題都是原問題規模較小的實例。
  2. 解決(Conquer):遞歸地求解各子問題。如果子問題規模足夠小,則直接求解。
  3. 合併(Combine):將所有子問題的解合併爲原問題的解。

分治法的經典題目:

  1. 二分搜索
  2. 大整數乘法
  3. Strassen矩陣乘法
  4. 棋盤覆蓋
  5. 歸並排序
  6. 快速排序
  7. 循環賽日程表
  8. 河內塔

results matching ""

    powered by

    No results matching ""