導覽


05. 搜索演算法

電腦常需要在大量的資料集之中尋找資訊,因此電腦必須為此發展出快速又有效的方法。

以下透過一些活動來推演三種不同的搜尋方式:線性搜尋法、二分搜尋法以及雜湊搜尋法。

【暖身活動 - 傳統海戰棋】

遊戲人數:2人

工具:每人一張紙,上面有兩組6x6的座標方格,第一組稱為佈局盤、第二組稱為炮擊盤,如圖所示

1. 佈局:

遊戲開始前,雙方在版面上放置共計四艘的船艦,分別是佔五格的航空母艦(以字母A表示)、佔四格的戰艦(以字母B表示)、佔三格的巡洋艦(以字母C表示)、以及佔兩格的巡邏艇(以字母D表示)
佈局結果舉例如下

2. 炮擊開始:

雙方玩家輪流進行,一次喊出一個位址作為炮擊地點。

若對方棋盤上所對應的位置有船艦,則需說出被擊中的船艦代號並在己方的佈局盤上的對應位置打叉,猜測方則根據回應在炮擊盤上的猜測位置記錄擊中的代號

若對方棋盤上所對應的位置沒有船艦,對方則說「MISS!」,猜測方則在炮擊盤上的猜測位置上寫下「╳」,被攻擊方則在此位置上寫下「○」

遊戲進行示例:

【回合一 – 玩家1炮擊位置3B,結果為MISS,進行後棋盤記錄如下】

【回合二 – 玩家2炮擊位置4C,結果為擊中船艦代號C,進行後棋盤記錄如下】

【回合三 – 玩家1炮擊位置1D,結果為擊中船艦代號A,進行後棋盤記錄如下】


2. 遊戲結束條件

其中一方的炮擊盤上寫滿5個A、4個B、3個C及2個D(亦即對方的佈局盤上所有的船艦都已被打叉)。

【正式活動 - 程式海戰棋】

海戰棋遊戲連結

1. 遊戲總共有六個關卡,目標是藉由搜尋策略,找出目標的船隻編號,並用飛彈將之擊沉。

2. 線性搜尋法(linear search或稱sequential search):
編號隨機排列,搜尋時除了憑空猜測之外,只要一個接一個走訪所有的位置,一定可以找到目標。

3. 二分搜尋法(binary search):
先將編號按照大小順序排列,每次猜測時都將目標範圍縮小一半,如此可快速鎖定範圍。

4. 雜湊搜尋法(hashing search):
編號已按照特定規則進行分組,只要知道分組的位置,就能馬上縮小搜尋的範圍。

二分搜尋法比線性搜尋法快,但線性搜尋法不需要照順序排列編號的時間。
雜湊搜尋法通常來說會比其他兩種快,但也有可能會變得非常慢。在最糟的情況下,如果所有船都同在一個船泊,那就會變得和線性搜尋法一樣慢了。

電腦儲存了大量資訊,它們必須要能夠快速對其進行搜尋篩選。而搜尋引擎所面對的世界上最大搜尋問題之一,就是他們必須要在極短時間內搜尋數十億個網頁。
而電腦被要求尋找的資料,像是文字、條碼編號或是作者名稱等,則被稱為「搜尋關鍵字」。

電腦可以非常快速的處理資訊,而你可能會認為為了找到想要的資訊,它們必須從頭開始,直到找到想找的目標為止。
這是我們在前兩關進行「線性搜尋」中所使用的方法。但這種方法即使對電腦而言也過於緩慢了。

舉個例子,假設一間超級市場的貨架上有一萬種不同產品,當櫃檯掃描一個條碼時,電腦必須最多搜尋到第一萬次才能找到產品的名稱與價格。這樣即使檢查每筆條碼只花千分之一秒,檢查完所有條碼也要花10秒。想像一下,要花多少時間才能掃描完一個家庭會採買的林林總總的雜貨。

二分搜尋法看起來是比較好的方式。二分搜尋法中,先將每筆數字照順序排列,然後檢查列表中間的項目,就可以知道要找的關鍵字是在列表前半還是後半。接著重複該動作,直到找到要搜尋的項目為止。舉剛才超級市場的例子,一萬個項目最多需要進行十四次檢查,也就是大約兩百分之一秒,幾乎是一瞬間即可完成搜尋。

第三個尋找資料的方法叫做雜湊。在這種方法中,關鍵字本身會直接指示到哪裡找到這個資訊。舉個例子,假設要搜尋電話號碼,你可以將所有數字加起來,然後除以11前取餘數。這個做法得到的雜湊關鍵字有點類似先前在錯誤檢查、修正的單元中所提到的同位檢查數字。用這種方法,通常電腦可以很直接地找到要搜尋的資訊。不過還是有小部份的可能,在同一個位置有好幾筆資料,而電腦必須在這幾筆裡面再繼續搜尋。