跳到主要內容

科技大觀園商標

分類項目
Menu

電機資工的現況與未來:生活中的演算法

105/11/07 瀏覽次數 11144
「演算法(algorithm)」在韋氏辭典的定義是「在有限步驟內解決數學問題的程序」;在計算機科學領域上,演算法則是一個計算的具體步驟,常用於計算、資料處理和自動推理。簡言之,演算法是為了解決某一問題所設計的一組有限運算規則的集合,其中包含精確的問題輸入與輸出。用白話來說,可以把演算法定義成「解決問題的方法」,它可以是利用文字敘述、流程圖或虛擬碼的方式來表示解決問題的步驟。

演算法有什麼用呢?它可以幫我們提升生活品質,例如節省時間、空間或成本等。既然演算法可以定義成解決問題的方法,我們又用了哪些演算法來解決哪些問題呢?
 
到書店買書的最佳化路徑
就以到書局買書為例吧!通常我們都會把欲購買的書籍列在清單上,到書局後就依照清單上的順序逐一去找,常用的方法就是演算法裡的「貪婪演算法(greedy algorithm)」。這個方法雖然可以找到所有的書,但是過程中可能需要在書局裡來回奔走,因為書局通常是依書籍的性質分類,例如小說、童書、醫療等。

倘若我們是依照清單上的順序,則有可能先在小說區找到書本A,接下來到童書區找書本B,然後到醫療區找書本C,由於第四本書D是英文的文學小說,因此得先找到外文的小說區才能找到書本D。而第五本書E是文學小說,我們又得回到中文的小說區。至於清單上的書本G和J都是中文的文學小說,因此又得進出中文小說區兩次才能找全所有書籍。

如果換個方式找書,先把清單上的書籍依性質分類,這樣一來,就可以先在中文小說區找到書本A、E、G和J,接著再到中文童書區找書本B和K,然後到中文的醫療區找書本C、H和L,最後再到外文區尋找書本D、F和I。這種程序避免了在書局裡來回奔走的狼狽情形。
 
日常生活中買書的情況也可以運用演算法提升效率。日常生活中買書的情況也可以運用演算法提升效率。
 
上述依照書籍性質分類的方法,就是演算法裡的「桶子排序法(bucket sort)」。這方法想像我們有中文和外文兩個桶子,先依照書籍的語文分類,書本A是中文,因此放入中文的桶子中;書本B是中文,因此放入中文的桶子中;書本C是中文,也放入中文的桶子中;但書本D是英文,因此放入外文的桶子中;如此這般依序把其餘的書本各放入其歸屬的桶子中。

接下來,再針對桶子排序。想像有中文小說、中文童書和中文醫療3個桶子,書本A就該放入中文小說的桶子中;書本B則放入中文童書的桶子中;如此依序置放。接著再針對外文的桶子也做相同的排序。經過桶子排序法的整理之後,就可以在同一區塊內找到全部同一性質的書籍,也就避免來回奔走了。

由於每一間書局有各自的擺設格局,如果可以先知道各類書籍的擺放位置,應該可以找到一條最佳化的路徑,作最少路徑的奔波。這個尋找最佳化路徑的問題就是演算法中非常著名的「旅行推銷員問題(travelling salesperson problem)」。
 
以購書清單為例的桶子排序法
 
以購書清單為例的桶子排序法

裝箱數量的最佳解

你終於把清單上的書找齊了,但是因數量太多,搬運並不方便,因此需要請書局宅配回家。然而書局所提供的箱子尺寸是固定的,如果裝箱越多,荷包會越傷,因此箱子的數目越少越好。但如何使用最少的箱子,就是演算法中著名的「裝箱問題(bin packing problem)」。這裝箱問題在計算機科學中也是一個相當難的問題,以下介紹「最先適配演算法(first-fit algorithm)」來解決裝箱問題。

假設所購買的12本書長、寬大小都一致,只有書本厚度不同,而書局所提供的箱子,長、寬與書本的一致,且設箱子高度是10公分。最先適配演算法的概念就是先找到第一個可以放入書本的箱子。設書本A厚度3.2公分,且目前因還沒有用到任何箱子,因此就把書本A直接放入箱子甲。又書本B厚度2.7公分,而箱子甲還有6.8公分的空間可以使用,因此又把書本B放入箱子甲。然後是書本C,厚度4.3公分,但是箱子甲只剩下4.1公分的空間,因此需要另外拿一個箱子乙來裝書本C。

接著是書本D厚度6.7公分,箱子甲、乙所剩空間都不夠裝書本D,因此另需箱子丙來裝書本D。書本E厚度5.3公分,箱子甲只剩4.1公分的空間,而箱子乙還有5.7公分的空間,因此把書本E放入箱子乙。書本F厚度2.5公分,而箱子甲還有4.1公分的空間,因此把書本F放入箱子甲。如此這般,書本G、H、I、J、K、L終於找到其各自歸屬的箱子,算算眼前的箱山,總共使用了8個箱子來裝這12本書。

上述的最先適配演算法顯然沒能找到最佳解,以上面裝書的例子來說,其實只要使用6個箱子就可以了:即把書本A和D放入箱子甲;書本B和L放入箱子乙;書本C和I放入箱子丙;書本E和J放入箱子丁;書本F和H放入箱子戊;書本G和K放入箱子己而達陣。

前述例子由於數量並不大,用人工的方式或許就可以找到最佳解;但是若問題的數量非常龐大時,就非得仰賴演算法不可了。然而演算法並不是萬靈藥,無法確定在有限的時間與空間下可以找到最佳解。但即便如此,退一步想,縱然所得到的答案不是最佳解,離最佳解也不會太遠,這個概念就是演算法中的「近似演算法(approximation algorithm)」。
快速搜尋中獎發票
生活中還有許多運用演算法的例子。例如統一發票對獎,通常都是逐一核對每張發票上的數字,檢查其是否是中獎的號碼。而每核對一張發票時,就需要搜尋中獎號碼,這個過程就是演算法裡的「搜尋演算法(searching algorithm)」。假設有100張發票需要對獎,則至少需看過這100張發票上的末三碼,也就是300個數字。

然而,若能先依照最後一碼的數字把發票分類,則需要看的數字量就可以減少。因為若最後一碼的數字與中獎號碼的數字不同,即使前面7個數字都相同,依然是廢紙一張。而這樣的對獎方式,也就是前述的「桶子排序法」。由此可知,一個設計良善的演算法的確可以幫助我們提高工作效率。
 
未經排序的統一發票
應用桶子排序法可增進統一發票對獎的工作效率應用桶子排序法可增進統一發票對獎的工作效率
未經排序的統一發票
 

排序的方法

在日常生活中,最常使用到的演算法又是什麼呢?答案是:排序演算法!諸如依照身高安排座位或成績排名等都需要使用這個演算法。以下介紹幾種依身高安排座位的排序演算法。在新生入學時,老師會先把全班學生依照高矮排序安排座位。若老師不知道每位學生確實的身高時,該如何排出高矮順序呢?這個問題就是演算法裡的「排序問題(sorting problem)」。

氣泡排序法 請學生排成一列,然後比較同學A和B的身高,較矮的同學A往前排在第一位,較高的同學排在第二位。接下來比較同學C的身高,因為C比同學B矮,則與同學B交換位置;也比同學A矮,再與同學A交換位置。接下來的同學D比排在第三位的同學B高,因此不需要更動排位。依序逐一比較,就可以排出高矮的順序。這個方法稱為「氣泡排序法(bubble sort)」,因為在過程中,較矮的同學就如氣泡般一直往上浮而得名。

插入排序法 挑選同學A排在第一位,接著再挑選同學B與排在第一位的同學A比較身高,由於同學B比同學A高,因此把同學B排在第二位;再挑選同學C與目前排在序列中的同學比較,由於同學C比目前排在第一位的同學A矮,因此把同學C排在第一位,原本序列中的同學每人都往後退一個位置。

接著再挑選同學D,再次與目前序列中的同學比較,由於同學D比目前的每一位同學都高,因此把同學D排在第四位。如此依序挑選同學與目前序列中的每一位同學比身高,再把這位同學插入適當的位置,就可完成身高排列的順序。這個方法就是「插入排序法(insertion sort)」,因為是在過程中逐一找到位置,再把同學插入這個位置而得名。

選擇排序法 利用目測的方式找出身高最矮的同學F,把同學F排在第一位;接著從剩餘的同學中,再次目測找出最矮的同學C,把他排在第二位;在剩餘的同學中持續找出身高最矮的同學,把他排到順序之中,直到所有同學都排進隊伍中。這個方法就是「選擇排序法(selection sort)」,因為在過程中,每一次都從尚未排入隊伍的同學中選擇最矮的同學來排入而得名。

快速排序法 選擇同學A當作標準身高,其他同學都須與A比較身高,把比同學A高的同學B、D和E分到甲區,比同學A矮的同學C和F分到乙區;接著在甲區的同學中,挑選同學B當作標準身高,把比同學B高的同學D分到丙區,比同學B矮的同學E分到丁區;在乙區的同學中,挑選同學F當作標準身高,把比同學F高的同學C分到戊區。如此一來,每個小區域內只有一位同學,而兩個小區域之間有一位被當作標準的同學。最後,把每個小區域及標準身高的同學合併起來,這個方法就是演算法中的「快速排序法(quick sort)」。

在日常生活中,其實我們時時刻刻都在使用演算法解決問題,只是不曉得那個演算法的名稱,也不曉得是否可以得到最好的答案,甚至不曉得那個演算法是否有很好的效率可以省下很多時間。一般最常使用的是貪婪演算法,這方法雖然可以得到答案,但通常不是最好的,效率也不見得理想。如果能夠學習到更多的演算法,明瞭該採取什麼方法以解決日常生活上的問題,就可以有效地節省時間、空間與成本,並提升生活品質。

演算法在有限的時間與空間內,可以有效率地解決問題,因此一直是資訊工程研究中非常重要的議題。例如在設計導航系統時,希望可以提供一條最佳化的行進路徑(時間最少或距離最短),這時需設計一個搜尋路徑的演算法,而Dijkstra演算法(Dijkstra algorithm)就可以幫助我們找到最佳解。又如常用的搜尋引擎,我們希望可以迅速地獲得最準確的搜尋結果,這時就需要設計一個有效率的字串比對演算法。

演算法的應用十分廣泛,而設計演算法能讓我們更有效率地解決各式各樣的問題,因此演算法在資訊工程領域中扮演著非常重要的角色,也一直是值得投入的研究方向。

資料來源
OPEN
回頂部