問題詳情

34. 在一個遊戲樹(game tree)上要搜尋較好的走步,以下何者是常用的演算法?
(A)Alpha-beta search
(B)Huffman algorithm
(C)Ford–Fulkerson algorithm
(D)Kruskal's Algorithm

參考答案

答案:A
難度:困難0.27957
統計:A(26),B(18),C(12),D(17),E(0)

用户評論

老師】評論

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

william】評論

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算法實現。算法的思想如下:只要有一條從源點(開始節點)到匯點(結束節點)的路徑,在所有的邊上都有可用容量,就沿著這條路徑發送一個流。 然後再找到另一條路徑,一直到網絡中不存在這種路徑為止。 一條有可用容量的路徑被稱為一個增廣路徑。