Just My Life & My Work

削減與搜尋 (Prune and Search)

首先我們要先了解:「切割與征服 (Divide and Conquer)」是將一個大的問題,分割成許多小的問題;將這些小的問題解決之後,原本大的問題也就解決了。如果小問題還是很難,那就再切割成更小的問題來解決就行了。

削減與搜尋 (Prune and Search)」可以視作 Divide and Conquer 的特例。一個問題被分割成許多子問題之後,如果只有其中幾個子問題是重要的,而其他子問題是沒有必要計算的,此時就稱做 Prune and Search。意思是削減不重要的子問題,只搜尋有用的子問題。

Prune and Search的概念

  • 可視為切割與征服 (Divide and Conquer) 策略的特例。
  1. 在一個資料集合當中,依照目前問題的特性,事先去除掉一些答案不可能存在的資料子集,再由目前剩下的資料子集繼續嘗試搜尋答案。
  2. 包含多次的處理,每次的處理都會將資料集合刪除固定的百分比,並運用同樣的方法遞迴地以刪除後的資料當作輸入資料重新解問題。經過若干次處理後,資料量將可縮小到能用固定常數的時間解得答案。
  • 它的精神所在便是如何有效地刪減資料集合,就像切割與征服 (Divide and Conquer) 策略強調的如何有效的合併。不過由於利用削減搜尋法得出來的演算法,有時會和分割解決法所得的結果相同,因此這兩種方法時常被混淆。

一個簡單的例子:二分搜尋法 (Binary Search)

有一排序後之序列如下 : (Search 8)

在每一次比較以後,總是會有一群資料被削減掉 (pruned away)。Binary search可視為特殊的切割與征服策略!這是因為:

  1. 切割與征服策略強調將母問題切割成較小的問題(Divide),再使用相同的解決程序對所有小問題加以分別處理(Conquer)。所有小問題的解可以成為母問題的最後解;若有必要,則再將每個小問題的處理結果加以合併
  2. 二分搜尋法將問題切割及經過一次比較後,會直接將答案不存在之一方的所有資料削減掉 (Prune),再使用相同的程序去搜尋另一方 (Search)。

這讓我想到人生,其實有很多事情需要作抉擇,我們的時間有限,若只是使用切割與征服 (Divide and Conquer)會花費龐大的時間,如果再加上特別的條件來過濾不想要的部份,那麼就會減少許多不必要的時間浪費,這就是削減與搜尋 (Prune and Search)的精神!

參考:演算法筆記本 – Divide and Conquer

廣告

Comments on: "削減與搜尋 (Prune and Search)" (1)

  1. […] 如果用電腦資訊演算法來思考,我先前文章削減與搜尋 (Prune and Search)有解釋是切割與征服 (Divide and Conquer)的特例。若只是切割與征服會耗費很多時間去嘗試錯誤,然若能削減與搜尋必能縮短嘗試錯誤的時間,就能比一般人更早找到人生任務,那關鍵就是清楚知道自己要的是什麼,把多餘的可能恰當地捨棄,專注在對自己有益的部分上。 […]

隨意留個言吧:)~

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google photo

您的留言將使用 Google 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

標籤雲

%d 位部落客按了讚: