啓發式算法(Heuristic Algorithm)是壹種在解決問題時通過啓發式規則來選擇下壹步操作的算法。它通常用于解決NP-hard問題,這些問題的精確算法在複雜度上是不可行的。
例如,貪心算法是壹種常見的啓發式算法,它在每壹步都選擇當前最優的選擇。比如在尋找最短路徑問題中,貪心算法每壹步都選擇當前離終點最近的節點。
另壹個例子是A*搜索算法, 主要用于解決在地圖中從起點到終點的最短路徑問題,它通過評估每個點到終點的預估距離來指導搜索,每次選擇最小f(n) = g(n) + h(n) 的節點作爲下壹步搜索的節點。
A*啓發式算法的代碼示例如下:
def a_star(graph, start, end):
distances = {node: float('infinity') for node in graph}
distances[start] = 0
previous = {node: None for node in graph}
queue = PriorityQueue()
queue.put((0, start))
while not queue.