教甄◆電腦科專業題庫下載題庫

Alpha-beta剪枝是一種搜尋演算法，用以減少極小化極大演算法（Minimax演算法）搜尋樹的節點數。這是一種對抗性搜尋演算法，主要應用於機器遊玩的二人遊戲（如井字棋、象棋、圍棋）。當演算法評估出某策略的後續走法比之前策略的還差時，就會停止計算該策略的後續發展。該演算法和極小化極大演算法所得結論相同，但剪去了不影響最終決定的分枝^[1]。

Ford–Fulkerson方法（Ford-Fulkerson method）或 Ford–Fulkerson算法（FFA）是一類計算網絡流的最大流的貪心算法。 之所以稱之為「方法」而不是「算法」，是因為它尋找增廣路徑的方式並不是完全確定的，而是有幾種不同時間複雜度的實現方式^[1][2]它在1956年由L.R. Ford, Jr. 及 D.R. Fulkerson^[3]發表。「Ford–Fulkerson」這個名詞通常也用於Edmonds–Karp算法，這是一個特殊的Ford–Fulkerson算法實現。

算法的思想如下：只要有一條從源點（開始節點）到匯點（結束節點）的路徑，在所有的邊上都有可用容量，就沿著這條路徑發送一個流。 然後再找到另一條路徑，一直到網絡中不存在這種路徑為止。 一條有可用容量的路徑被稱為一個增廣路徑。