Reduction: 借力使力

學數/理/演算法 (還有 perl) 的人, 有一個共通的特性, 就是懶惰。 遇到一個複雜的問題 A, 如果可以對它稍微動點手腳, 讓它變成看起來像是已經解決過的問題 B, 那麼就不需要再為 A 發明一個新的演算法, 只要直接把解 B 的現成演算拿來用就好了。 這種借力使力, 四兩撥千斤的解題方式, 就是今天要談的 reduction。 以下是幾個範例:

Graham scan 其實就是將 convex hull 問題 reduce 成 排序問題。

有大小不一保特瓶數十個, 瓶蓋打開, 散落一地 ...

排序問題 reduce 成 convex hull 問題 ...

median 問題 reduce 成 sorting 問題 ...

maximal bipartite matching reduce 成 maximal flow 問題...

參考資料

  1. Jeff Erickson. Reductions and transformations
  2. Steven S. Skiena. Satisfiability