A-level 計算機科學/OCR/單元 2.3 演算法
線性搜尋簡單地檢視要搜尋的每個值列表中的每個專案，直到找到正確的值。對於少量資料來說，這足夠有效，但是一旦資料量增加，它就會變得效率低下得多。在大 O 符號中，它可以定義為 O(n)，因為搜尋所花費的時間與要搜尋的資料項數量成正比增加。
二分搜尋要求在搜尋資料之前對資料進行排序。它從將資料列表分成兩半開始，並確定哪一半包含所需的值。不包含所需資料的另一半被忽略，並且該過程重複，直到找到該值。
氣泡排序是最簡單的排序型別。它單獨檢查每個元素，並確定它的鄰居是否比它大或小。如果較小，它將保留在當前位置，並且演算法移動到下一個元素。如果它大於它的鄰居，演算法交換這兩個元素。然後它遍歷整個排序項，直到不再進行任何移位。此時，該項可以被認為已排序。
它透過建立兩個單獨的列表（一個排序列表和一個未排序列表）來工作。最初，一個專案從未排序列表中拉入排序列表。從這裡，另一個專案被拉入，如果該專案大於排序列表中的當前專案，則將其放置在前面，否則將其放置在排序專案的後面。下一個專案被拉入並進行比較，如果它是最大的值，它將放在最前面，最小的值放在最後面，如果它介於兩者之間，則將其放在中間。該過程重複，直到整個列表排序。
快速排序演算法使用列表中稱為樞紐的值。任何大於樞紐的值都放在右邊，任何小於樞紐的值都放在左邊。這會在樞紐兩邊建立兩個子列表。該過程對兩個列表重複，直到所有子列表都變成樞紐。此時，該列表可以被認為已排序。
Dijkstra 演算法作用於一個圖，並找到從一個節點到另一個節點的最短路徑。一個圖是一個節點集合，由弧連線。弧可以與它們相關聯的值，被稱為弧的成本。節點和弧可以表示許多不同的東西，因為它們通常是現實的抽象。例如，節點可以代表網路上的路由器，而弧可以是它們之間的物理連線，它們的成本是訊號沿一條路線傳播所花費的時間。或者，節點可能代表城鎮，而弧可能代表它們之間的道路，它們的成本是沿著道路行駛所需的汽油量。
演算法從使用者設定的起始節點開始，並嘗試計算遍歷圖以到達所有節點的累積最小成本，試圖逐步改進計算的成本。
- 每個節點都賦予兩個值。
- 一個臨時成本（整數或浮點數），表示遍歷弧以到達該節點的最小已知累積成本。最初，這對於除起始節點之外的所有節點都設定為無窮大，起始節點的臨時成本設定為零，因為這是遍歷到它的最小累積成本。
- 一個已訪問標誌（布林值），表示當前節點是否已被訪問。最初，這對於除起始節點之外的所有節點都設定為 false，起始節點設定為 true。
- 計算與當前節點相連的每個未訪問節點的累積臨時成本。
- 每條弧都有一個成本，因此每個節點的臨時成本都設定為該值
- 對於 Dijkstra 演算法的後續迭代，只有在計算的成本小於節點的當前臨時成本時才更新臨時成本。
- 遍歷具有最小臨時成本的節點。
- 它現在是當前節點。
- 它被標記為已訪問。
- 重複步驟 2 和 3，直到與當前節點相連的每個節點都被訪問。
- 此時，每個節點的累積臨時成本可以被認為是最小可能的成本。
- 完成後，可以追溯路徑以找到到達所需節點的最短路徑。
這與 Dijkstra 演算法基本相同，只是它使用啟發式方法來提高搜尋效率。一個啟發式實際上是對從給定節點到目標節點的路徑長度的估計。例如，在尋找城鎮之間的路徑時，啟發式方法可能是城鎮之間的直線距離。像這樣始終是低估的啟發式方法被稱為可容許啟發式方法，並且具有在與 A* 演算法一起使用時始終會導致找到最佳路徑的特性。然而，不可容許的啟發式方法仍然可以使用，因為它們會嚴重減少在找到良好的路徑之前需要檢視的路徑數量。在許多情況下，遵循 Dijkstra 演算法將涉及檢視許多不太可能是正確路徑的路徑，例如明顯遠離目標的路徑。啟發式方法為我們提供了一種使用這種知識來加快我們用來查詢路徑的演算法的方法。
A* 與 Dijkstra 的不同之處在於它為每個節點儲存三個值而不是兩個：臨時路徑成本、最終路徑成本和啟發式成本。當選擇一個節點進行擴充套件時，對於每個沒有最終路徑成本的節點，計算一個總值，該值是臨時路徑成本和啟發式成本的總和。具有最低總值的節點將被擴充套件。