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

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

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



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



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

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



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

Hope it helps,


Share:

0 意見:

張貼留言