#76 演算法裡一個基本的觀念 - Reduction

Reduction 是一個在演算法知識裡基本且簡單的觀念．其實在各位的工作中也一定常用到這觀念，只是你不知道而己．在這文章裡一如往昔，不用學術理論的描述方式，而是用平常寫程式的例子來讓非電腦科系畢業的資訊人了解什麼是 Reduction．

接下來用寫程式的角度來看什麼是 Reduction．假設你需要寫一個影像辨識的程式，這個程式需要辨識一個圖片裡是否含有某個數字，所以你寫的 function 可能會像下列:



以上的程式碼尚未完成，部份內容先暫以文字描述表示．你可能不是一個影像辨識的專家，完全不知道該怎麼做數字辨識．所以你一定會尋找可能的方法來執行這項任務．最後，你找到一個程式可以做這項工作，它的程式碼如下 (數字辨識的內容用文字描述代替):



由於 DetectNumber() 是別人完成的程式，假設你僅知道它是可用的，但無法了解其中的運作內容．你可以將它視為一個黑盒子．至於黑盒子裡面是怎麼運作的，由於能力與知識不及，所以暫時無法了解．但不了解也不代表不能使用，你只要知道這個黑盒子需要的輸入和輸出是什麼資料型別，就可以將它套用到你的程式裡．

接下來，我們將 DetectNumber() 套用到 ContainNumber() 裡面，所以完成後的 ContainNumber() 如下:



如此一來， ContainNumber() 就能做到它需要的功能了．從寫程式的角度來看，你會覺得這不就是每天工作在做的事情嗎 ? 是的，你每天寫程式所做的事情都是讓程式呼叫東呼叫西，在這一連串呼叫的過程完成自己所需要達成的功能．當一個演算法呼叫另外一個演算法來達成某項功能時，這就是一個 Reduction．也就是說，ContainNumber() 要做的事情，其實 DetectNumber() 也能做的到，差別只是輸入輸出的資料型別不同而己．將 ContainNumber() 的輸入型別轉換一下，就能形成 DetectNumber() 的輸入型別，然後將 DetectNumber() 的輸出型別轉換一下，就能變成 ContainNumber() 的輸出型別．再換個角度想，ContainNumber() 和 DetectNumber() 要處理的問題核心其實是同一個，只是問法和要求的答案有點小差別而己．在演算法的世界裡，某些問題的解法能變成另一些問題的解法，靠的就是這種 Reduction 的技巧．只要你能找出問題的本質是一樣時，解法就很接近了．

Hope it helps,