Reduction: 借力使力

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

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

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