Tìm kiếm A* và heuristic

BFS và DFS là tìm kiếm mù: chúng không biết đích nằm hướng nào. A* thông minh hơn: nó dùng một heuristic (ước lượng quãng đường còn lại tới đích) để ưu tiên đi về phía đích, nhờ đó vừa nhanh vừa cho đường rẻ nhất.

Hãy hình dung bạn lái xe từ nhà tới một địa chỉ trong thành phố. Tìm kiếm mù giống như mò từng ngã tư đều nhau ra mọi phía, kể cả phía ngược hướng đích. Còn con người thì khôn hơn: dù chưa biết chính xác đường nào ngắn nhất, ta vẫn ưu tiên rẽ về phía đích vì "cảm giác" nó gần hơn. Cái "cảm giác gần" đó chính là heuristic. A* biến trực giác này thành công thức: nó cân nhắc đồng thời quãng đã đi thật và quãng ước lượng còn phải đi, rồi luôn chọn nút hứa hẹn tổng chi phí thấp nhất. Điều tinh tế là A* không bao giờ bị heuristic đánh lừa hoàn toàn: nếu ước lượng đủ "khiêm tốn", A* vẫn đảm bảo tìm ra đường rẻ nhất, chứ không chỉ một đường "trông có vẻ tốt".

Đặt vấn đề

Hãy đặt hai thái cực lên bàn cân trước khi bước sang A*.

Tìm kiếm theo chiều rộng lan đều ra mọi phía như vết dầu loang. Nó đảm bảo tìm ra đường ít bước nhất, nhưng phải trả giá: để tới một đích cách xa 20 bước trên lưới bốn hướng, nó có thể phải mở hàng trăm nghìn ô, phần lớn nằm ngược hướng đích. Nó không biết đích ở đâu nên đối xử công bằng với mọi hướng, và sự công bằng ấy chính là sự lãng phí.

Con người đi đường thì khác. Bạn ở phía tây thành phố, cần tới địa chỉ ở phía đông, nên bạn ưu tiên rẽ về phía đông dù chưa biết chính xác tuyến nào ngắn nhất. Nhưng nếu chỉ nghe theo cảm giác ấy, ta lại rơi vào bẫy khác: cứ lao về phía đích thì dễ đâm vào ngõ cụt, hoặc chọn con đường vòng vèo dài hơn chỉ vì mỗi bước của nó trông có vẻ tiến gần đích.

A* là câu trả lời cho cả hai cực đoan. Nó giữ sổ sách về quãng đường đã đi thật, đồng thời tham khảo ước lượng về quãng còn lại, rồi cộng hai con số ấy để xếp hạng lựa chọn. Nhờ phần thứ nhất, nó không bị dụ vào đường vòng. Nhờ phần thứ hai, nó không phí công dò về hướng ngược. Điều đẹp đẽ là dưới một điều kiện khá nhẹ về ước lượng, A* vẫn giữ nguyên bảo đảm tối ưu như tìm kiếm mù, mà lại mở ít nút hơn hẳn.

Thử ngay: A sao mở rộng nút có f nhỏ nhất

Hai con số nói ở trên có tên riêng: g là quãng đã đi thật từ điểm xuất phát tới nút đang xét, h là heuristic ước lượng quãng còn lại tới đích. A* xếp hạng các nút bằng tổng của chúng. Để ý cột f = g + h quyết định nút nào được mở rộng tiếp, và A* bỏ qua nhánh kém.

Widget dưới đây chạy thật thuật toán trên đồ thị này. Đừng chỉ xem: hãy đổi sang UCS để thấy đúng cái mà bài tập 1 hỏi (h = 0 thì A* thoái hóa thành Dijkstra, vẫn ra S → B → D → G nhưng mở thêm nút), rồi đổi sang tham lam để thấy nó bỏ qua g ra sao. Đó chính là phép so sánh ở mục "A* so với tham lam và Dijkstra", nhưng để bạn tự chạy.

Một lưu ý về cách đọc: bảng biên bên dưới chỉ liệt kê các bản còn sống, tức những nút thật sự còn cơ hội được mở rộng. Đoạn mã ở mục sau dùng kỹ thuật xóa lười nên trong heap còn lẫn cả bản sao cũ của những nút đã thăm; chúng vẫn bị lấy ra theo thứ tự f, nhưng bị tập da_tham chặn lại ngay và không sinh thêm gì, nên bảng này lược chúng đi cho gọn.

A* mở rộng nút có f = g + h nhỏ nhất

Thuật toánA* (f = g + h)UCS (chi phí đều)Tham lam (theo h)BFS (bề rộng)DFS (chiều sâu)Xuất phátSABCDĐíchABCDG

Bấm vào đồ thị để đặt

1def a_sao(do_thi, h, bat_dau, dich):
2    bien = [(h[bat_dau], 0, bat_dau)]
3    da_tham = set()
4    while bien:
5        f, g, nut = heapq.heappop(bien)   # f nhỏ nhất
6        if nut == dich:
7            return g
8        if nut in da_tham:
9            continue
10        da_tham.add(nut)
11        for ke, w in do_thi[nut]:
12            g_moi = g + w
13            heapq.heappush(bien, (g_moi + h[ke], g_moi, ke))
14    return None

Hàng đợi ưu tiên (theo f)

Sg0+h7=7

Đã thăm (explored)

(rỗng)

Khởi tạo: đưa S vào hàng đợi ưu tiên với g = 0, f = g + h(S) = 0 + 7 = 7.

1/60.5×1×2×

đang mở rộng trong biên đã thăm đường đi

Ý tưởng cốt lõi

A* sắp xếp biên bằng một hàng đợi ưu tiên theo giá trị f(n) = g(n) + h(n):

• g(n): chi phí thực đã đi từ điểm xuất phát tới n.
• h(n): chi phí ước lượng từ n tới đích (heuristic).
• f(n): ước lượng tổng chi phí của đường đi qua n. A* luôn mở rộng nút có f nhỏ nhất.

Nếu heuristic không phóng đại (admissible: h(n) không bao giờ lớn hơn chi phí thực còn lại), A* đảm bảo tìm ra đường đi rẻ nhất.

Hãy nhìn kỹ vai trò của từng thành phần. g(n) là quá khứ: nó đã xảy ra, đo chính xác, không phải đoán. h(n) là tương lai: nó là dự báo, có thể sai lệch, và chất lượng của A* phụ thuộc vào việc dự báo này chính xác tới đâu. Tổng f(n) = g(n) + h(n) là ước lượng tốt nhất về chi phí toàn tuyến nếu ta đi qua n. Vì A* luôn rút nút có f nhỏ nhất ra khỏi hàng đợi ưu tiên, nó tập trung công sức vào những tuyến hứa hẹn nhất và trì hoãn những tuyến kém, thay vì dò đều như tìm kiếm mù.

Vì sao phải là hàng đợi ưu tiên

Chi tiết cấu trúc dữ liệu ở đây không phải chuyện phụ. BFS dùng hàng đợi vào trước ra trước nên luôn mở nút nông nhất; DFS dùng ngăn xếp nên luôn lao xuống nhánh mới nhất. Cả hai xếp thứ tự theo thời điểm nút được sinh ra, một tiêu chí chẳng liên quan gì tới chất lượng của nút.

A* cần tiêu chí khác hẳn: luôn lấy ra nút có f nhỏ nhất, bất kể nó sinh lúc nào, ở nhánh nào, sâu bao nhiêu. Nếu giữ biên trong một danh sách thường rồi mỗi lần quét toàn bộ để tìm giá trị nhỏ nhất, chi phí mỗi lần lấy là tuyến tính theo kích thước biên, mà biên có thể lên tới hàng triệu nút. Hàng đợi ưu tiên cài bằng heap cho phép chèn và lấy phần tử nhỏ nhất với chi phí chỉ cỡ logarit, chính là mô-đun heapq trong đoạn mã dưới.

Một mẹo cài đặt đáng chú ý: ta đẩy vào heap bộ ba (f, g, nut) chứ không chỉ f, vì Python so sánh bộ theo từng thành phần, nên khi hai nút có f bằng nhau nó sẽ so tiếp g để phá thế hòa. Ta cũng chấp nhận đẩy vào heap nhiều bản sao của cùng một nút với g khác nhau: bản có f nhỏ nhất được lấy ra trước, các bản sau bị tập da_tham chặn lại. Kỹ thuật xóa lười này đơn giản hơn nhiều so với cài heap có hỗ trợ giảm khóa.

Heuristic chấp nhận được và nhất quán

Có hai điều kiện thường gặp về heuristic, và cần phân biệt rõ.

• Chấp nhận được (admissible): h(n) ≤ h*(n) với mọi nút n, trong đó h*(n) là chi phí thực rẻ nhất từ n tới đích. Nói cách khác, heuristic không bao giờ phóng đại, luôn lạc quan. Đây là điều kiện đủ để A* tối ưu khi dùng trên cây tìm kiếm.
• Nhất quán (consistent, còn gọi monotonic): với mọi cạnh từ n sang n' có chi phí c(n, n'), ta có h(n) ≤ c(n, n') + h(n'). Đây là một dạng bất đẳng thức tam giác. Nhất quán là điều kiện mạnh hơn: mọi heuristic nhất quán đều chấp nhận được, nhưng chiều ngược lại không luôn đúng.

Vì sao cần nhất quán? Khi h nhất quán, giá trị f không giảm dọc theo bất kỳ đường đi nào, nên lần đầu tiên A* lấy một nút ra khỏi hàng đợi thì đường tới nút đó đã là rẻ nhất. Nhờ vậy A* tối ưu cả khi tìm kiếm trên đồ thị (có gộp trạng thái trùng) mà không cần mở lại nút đã đóng. Với heuristic chỉ chấp nhận được mà không nhất quán, để giữ tối ưu trên đồ thị đôi khi phải cho phép mở lại nút đã đóng khi tìm được đường rẻ hơn tới nó.

Đồ thị ví dụ và heuristic

Trọng số ghi trên cạnh là chi phí mỗi bước. Heuristic h (ước lượng tới đích G):

Nút	S	A	B	C	D	G
h	7	6	6	4	2	0

Kiểm tra bằng tay: heuristic này có chấp nhận được không

Đừng tin một bảng heuristic chỉ vì nó được in ra. Hãy tự tính chi phí thật rẻ nhất từ mỗi nút tới đích, ký hiệu h*, rồi đối chiếu.

Từ D chỉ có cạnh tới G chi phí 2, nên h*(D) = 2. Từ C chỉ có cạnh tới G chi phí 4, nên h*(C) = 4. Từ A, đường duy nhất là A tới C tới G, tức 3 + 4 = 7. Từ B, đường duy nhất là B tới D tới G, tức 5 + 2 = 7. Từ S, qua A mất 3 + 7 = 10 còn qua B mất 1 + 7 = 8, nên h*(S) = 8.

Đối chiếu với bảng h đã cho: 7 ≤ 8, 6 ≤ 7, 6 ≤ 7, 4 ≤ 4, 2 ≤ 2, 0 ≤ 0. Không giá trị nào phóng đại, vậy heuristic chấp nhận được. Ở C và D thì h bằng đúng h*, tức heuristic hoàn hảo tại hai nút ấy, và điều đó vẫn hợp lệ: chấp nhận được cho phép bằng, chỉ cấm vượt.

Kiểm tra tiếp tính nhất quán trên từng cạnh với bất đẳng thức h(n) ≤ c(n, n') + h(n'). Cạnh S tới B: 7 ≤ 1 + 6 = 7, vừa khít. Cạnh S tới A: 7 ≤ 3 + 6 = 9. Cạnh A tới C: 6 ≤ 3 + 4 = 7. Cạnh B tới D: 6 ≤ 5 + 2 = 7. Cạnh C tới G: 4 ≤ 4 + 0. Cạnh D tới G: 2 ≤ 2 + 0. Mọi cạnh đều thỏa, vậy heuristic này nhất quán, và ta yên tâm dùng tập đã đóng mà không cần mở lại nút nào.

Mã nguồn Python

import heapq

def a_sao(do_thi, h, bat_dau, dich):
    # hàng đợi ưu tiên các bộ (f, g, nut), lấy f nhỏ nhất trước
    bien = [(h[bat_dau], 0, bat_dau)]
    da_tham = set()
    while bien:
        f, g, nut = heapq.heappop(bien)   # nút có f nhỏ nhất
        if nut == dich:
            return g                       # chi phí đường đi tối ưu
        if nut in da_tham:
            continue
        da_tham.add(nut)
        for ke, w in do_thi[nut]:          # ke kề, w trọng số cạnh
            g_moi = g + w
            heapq.heappush(bien, (g_moi + h[ke], g_moi, ke))
    return None

A* nằm giữa hai thái cực

• Nếu h(n) = 0 với mọi nút, A* trở thành tìm kiếm theo chi phí đều (mù, nhưng vẫn tối ưu).
• Nếu h(n) càng sát chi phí thực, A* càng ít mở rộng nút thừa, càng nhanh.
• Nếu h(n) phóng đại (lớn hơn chi phí thực), A* nhanh hơn nhưng mất bảo đảm tối ưu.

Heuristic tốt là chìa khóa

Sức mạnh của A* nằm ở heuristic. Một h không phóng đại và sát thực tế giúp A* lao thẳng tới đích, bỏ qua phần lớn không gian trạng thái. Ví dụ kinh điển: tìm đường trên bản đồ, h là khoảng cách đường chim bay tới đích, luôn nhỏ hơn hoặc bằng quãng đường thực phải đi.

A* so với tham lam và Dijkstra

Ba thuật toán dưới đây chỉ khác nhau ở hàm sắp xếp biên, nhưng cho hành vi rất khác.

• Tìm kiếm tham lam theo heuristic (greedy best-first) xếp biên chỉ theo h(n), hoàn toàn bỏ qua g(n). Nó lao thẳng về nút "trông có vẻ gần đích nhất". Rất nhanh, nhưng không tối ưu và thậm chí không đầy đủ, vì nó có thể bị một heuristic đánh lừa đâm vào ngõ cụt mà quên rằng quãng đã đi cũng tốn chi phí.
• Dijkstra (chi phí đều) xếp biên chỉ theo g(n), bỏ qua h(n). Nó tỏa đều ra mọi phía theo chi phí thực, đảm bảo tối ưu nhưng không có định hướng nên mở rộng rất nhiều nút thừa, kể cả những nút đi xa khỏi đích.
• A* dùng cả hai: f(n) = g(n) + h(n). Nó vừa giữ tính tối ưu của Dijkstra (nhờ g) vừa có định hướng của tham lam (nhờ h). Thực tế A* chính là sự tổng quát hóa: đặt h = 0 thì A* thoái hóa thành Dijkstra; bỏ g đi thì còn lại tham lam.

Thuật toán	Sắp xếp theo	Tối ưu	Định hướng về đích
Tham lam	h(n)	không	mạnh
Dijkstra	g(n)	có	không
A*	g(n) + h(n)	có (nếu h chấp nhận được)	có

Vì sao A* tối ưu

Trực giác chứng minh: giả sử A* sắp lấy đích G ra với chi phí thực g(G), mà tồn tại một đường rẻ hơn với chi phí thật C* < g(G). Đường rẻ hơn đó phải có một nút n đang nằm trong hàng đợi. Vì h không phóng đại, f(n) = g(n) + h(n) ≤ g(n) + h*(n) = C*. Vậy f(n) ≤ C* < g(G) = f(G) (do h(G) = 0). Nghĩa là n có f nhỏ hơn G, nên A* đã phải lấy n ra trước G, mâu thuẫn với giả thiết rằng ta lấy G ra. Kết luận: không thể tồn tại đường rẻ hơn bị bỏ sót, A* trả về đường tối ưu.

Ví dụ heuristic: khoảng cách Manhattan

Trên lưới ô vuông chỉ cho đi bốn hướng (lên, xuống, trái, phải), heuristic quen dùng là khoảng cách Manhattan: tổng chênh lệch tọa độ theo hàng và cột.

def manhattan(a, b):
    # a, b are (row, col) cells on a 4-directional grid
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

Vì trên lưới bốn hướng, đi từ ô a tới ô b bắt buộc phải bù đủ hiệu số hàng cộng hiệu số cột, nên khoảng cách Manhattan không bao giờ vượt quá quãng thực: nó chấp nhận được. Nó cũng nhất quán, vì mỗi bước đi một ô chỉ làm giá trị này giảm nhiều nhất là 1, đúng bằng chi phí bước đó. Nếu lưới cho phép đi chéo, ta đổi sang khoảng cách Chebyshev; nếu di chuyển tự do mọi hướng, dùng khoảng cách đường chim bay (Euclid). Chọn heuristic phải khớp với mô hình di chuyển thực tế thì mới giữ được tính chấp nhận được.

Heuristic mạnh và heuristic yếu

Mọi heuristic chấp nhận được đều cho A* kết quả tối ưu, nhưng chúng không ngang nhau về tốc độ. Cách so sánh chuẩn là khái niệm thống trị: cho h1 và h2 cùng chấp nhận được, ta nói h2 thống trị h1 nếu h2(n) ≥ h1(n) với mọi nút n. Nói cách khác h2 luôn ước lượng cao hơn hoặc bằng mà vẫn không vượt chi phí thật, tức nó bám sát sự thật hơn, ít lạc quan hão hơn.

Kết quả quan trọng: nếu h2 thống trị h1 thì A* dùng h2 không bao giờ mở nhiều nút hơn A* dùng h1. Lý do nằm trong chính chứng minh tối ưu: A* buộc phải mở mọi nút có f(n) < C*, với C* là chi phí đường tối ưu. Heuristic lớn hơn đẩy f của các nút xấu lên cao, nên số nút lọt xuống dưới ngưỡng C* ít đi.

Đó là lý do h = 0 là heuristic tệ nhất trong họ chấp nhận được: nó bị mọi heuristic khác thống trị, và A* với nó thoái hóa thành tìm kiếm chi phí đều. Ở cực kia, h = h* là heuristic hoàn hảo, A* đi thẳng một mạch tới đích. Mọi heuristic thực dụng nằm giữa hai cực ấy, và nghệ thuật thiết kế là đẩy h lên càng sát h* càng tốt mà vẫn không vượt qua. Nếu có hai heuristic chấp nhận được mà không cái nào thống trị cái nào, ta lấy h(n) = max(h1(n), h2(n)): heuristic mới vẫn chấp nhận được và thống trị cả hai. Chỉ cần lưu ý một h mạnh nhưng tính quá lâu có thể lỗ vốn so với h yếu mà rẻ.

Heuristic đến từ đâu: bài toán 8-puzzle

Cách thiết kế heuristic phổ biến nhất là nới lỏng bài toán: bỏ bớt vài ràng buộc, giải bài toán dễ hơn ấy một cách chính xác, rồi lấy chi phí lời giải đó làm ước lượng. Vì bài nới lỏng luôn dễ hơn hoặc bằng bài gốc, chi phí của nó không bao giờ vượt chi phí thật, nên heuristic thu được tự động chấp nhận được. Đây là công thức sinh heuristic có bảo đảm, không phải đoán mò.

Xét trò 8-puzzle: khung 3 nhân 3 chứa tám ô số và một ô trống, mỗi nước đi trượt một ô kề vào chỗ trống, mục tiêu là đưa các số về đúng vị trí.

Số ô sai chỗ (h1): đếm xem có bao nhiêu quân đang không nằm đúng ô đích của nó. Đây chính là chi phí lời giải nếu nới lỏng luật thành "được nhấc một quân bất kỳ và đặt thẳng vào đúng chỗ". Mỗi quân sai chỗ cần ít nhất một nước đi, nên h1 không phóng đại.

Tổng khoảng cách Manhattan (h2): với từng quân, tính khoảng cách Manhattan từ vị trí hiện tại tới ô đích của nó rồi cộng lại. Đây là chi phí nếu nới lỏng luật thành "được trượt một quân sang ô kề bất kỳ, kể cả ô đang có quân khác". Mỗi quân dù đi kiểu gì cũng phải tốn ít nhất từng ấy nước để bù chênh lệch hàng và cột, nên h2 cũng không phóng đại.

So sánh: một quân nằm cách đích ba ô chỉ đóng góp 1 cho h1 nhưng đóng góp 3 cho h2. Tổng quát h2(n) ≥ h1(n) với mọi trạng thái, tức h2 thống trị h1. Vì vậy A* với tổng khoảng cách Manhattan mở ít nút hơn hẳn, và nó là lựa chọn mặc định cho bài toán này.

Độ phức tạp

• Thời gian: trường hợp xấu nhất vẫn là hàm mũ theo độ sâu lời giải, O(b^d), khi heuristic kém. Nhưng heuristic càng sát chi phí thực, số nút mở rộng càng giảm; nếu h = h* hoàn hảo, A* đi thẳng tới đích không phí một nút nào.
• Bộ nhớ: đây là điểm yếu chính. A* giữ mọi nút đã sinh trong hàng đợi và tập đã đóng, nên bộ nhớ cũng cỡ hàm mũ O(b^d). Trên bài toán lớn, chính bộ nhớ chứ không phải thời gian mới là thứ khiến A* bó tay. Các biến thể như IDA* hay A* giới hạn bộ nhớ (SMA*) sinh ra để khắc phục điểm này.

Nhầm lẫn thường gặp

• Tưởng heuristic càng lớn càng tốt. Sai. Heuristic lớn hơn chỉ tốt khi vẫn không vượt chi phí thực; vượt qua ngưỡng đó là phóng đại, và A* mất bảo đảm tối ưu.
• Dùng heuristic không khớp mô hình di chuyển. Dùng khoảng cách Euclid trên lưới bốn hướng thì vẫn chấp nhận được (nó còn nhỏ hơn Manhattan), nhưng dùng Manhattan cho lưới đi chéo lại có thể phóng đại và làm hỏng tối ưu.
• Quên h của đích phải bằng 0. Nếu h(dich) ≠ 0, công thức và chứng minh tối ưu đều lệch.
• Chọn h = 0 rồi than A* chậm. Khi đó A* chỉ là Dijkstra, không có định hướng nào cả, đương nhiên phải mở nhiều nút.

Bài tập thực hành

Bài tập 1: A* với heuristic bằng không

Chạy lại A* trên đồ thị ví dụ nhưng đặt h(n) = 0 cho mọi nút. Thứ tự mở rộng có gì khác?

Gợi ý

Khi h = 0, f = g, nên A* mở rộng theo chi phí thực đã đi (chính là tìm kiếm chi phí đều). Nó sẽ mở rộng nhiều nút hơn (kể cả nhánh A) vì không còn "định hướng" về đích, dù vẫn trả về đúng đường rẻ nhất S → B → D → G.

Bài tập 2: heuristic phóng đại làm hỏng tối ưu

Đặt h(B) = 10 (phóng đại, vì chi phí thực B tới G chỉ là 7). Giải thích vì sao A* có thể trả về đường không tối ưu.

Gợi ý

Với h(B) = 10, f(B) = 1 + 10 = 11, lớn hơn f(A) = 9. A* sẽ ưu tiên mở rộng nhánh A trước và có thể tới G qua C với chi phí 3 + 3 + 4 = 10, kết luận sai rằng đó là đường tốt, bỏ lỡ đường thật rẻ hơn qua B (chi phí 8). Heuristic phóng đại phá vỡ bảo đảm tối ưu.

Bài tập 3: trả về đường đi thay vì chi phí

Sửa hàm a_sao để trả về đường đi (danh sách nút) thay vì chỉ chi phí g.

Gợi ý

Lưu thêm bảng cha: mỗi lần đẩy ke vào hàng đợi, ghi cha[ke] = nut. Khi lấy được đích ra, lần ngược theo cha từ đích về gốc rồi đảo ngược, giống hàm lan_nguoc ở bài BFS.

Tự kiểm tra

Vì sao A* không mở rộng nút A trong ví dụ?

Vì f(A) = 9 luôn lớn hơn f của các nút trên đường tối ưu (S, B, D, G đều có f ≤ 8). A* luôn lấy nút f nhỏ nhất ra trước, nên nó tới đích G (f = 8) và dừng trước khi đụng tới A. Đó chính là cách heuristic giúp A* cắt bớt không gian tìm kiếm.

Chấp nhận được và nhất quán khác nhau ra sao, và khi nào sự khác nhau đó mới đáng bận tâm?

Chấp nhận được chỉ đòi hỏi h(n) ≤ h*(n), tức heuristic không bao giờ ước lượng vượt chi phí thật còn lại. Nhất quán đòi hỏi thêm bất đẳng thức tam giác trên từng cạnh: h(n) ≤ c(n, n') + h(n'). Nhất quán mạnh hơn, mọi heuristic nhất quán đều chấp nhận được nhưng chiều ngược lại không luôn đúng.

Sự khác biệt trở nên quan trọng khi ta tìm kiếm trên đồ thị và dùng tập đã đóng để khỏi thăm lại trạng thái trùng. Khi h nhất quán, f không giảm dọc theo bất kỳ đường đi nào, nên lần đầu một nút được lấy ra khỏi hàng đợi thì đường tới nó đã rẻ nhất, đóng nút lại là an toàn. Nếu h chỉ chấp nhận được mà không nhất quán, ta có thể tìm được đường rẻ hơn tới một nút đã đóng, và để giữ tối ưu thì phải cho phép mở lại nút ấy. Trên cây tìm kiếm không gộp trạng thái trùng thì chấp nhận được đã đủ.

Hai heuristic đều chấp nhận được, một cái luôn cho giá trị lớn hơn. Nên chọn cái nào?

Nên chọn cái cho giá trị lớn hơn, tức cái thống trị. A* buộc phải mở mọi nút có f(n) < C*, với C* là chi phí đường tối ưu; heuristic lớn hơn đẩy f của các nút vô vọng lên cao nên ít nút lọt xuống dưới ngưỡng đó, A* mở ít nút hơn. Vì cả hai vẫn chấp nhận được nên tính tối ưu không mất. Ngoại lệ thực dụng duy nhất là khi heuristic mạnh tốn quá nhiều thời gian tính ở mỗi nút, khi ấy phần tiết kiệm nhờ mở ít nút có thể không bù nổi chi phí tính toán.

Câu hỏi tự kiểm

Kiểm tra nhanh: A sao và heuristic0/4 đúngchưa trả lời

1. 1A sao luôn mở rộng nút theo tiêu chí nào?
2. 2Heuristic chấp nhận được (admissible) nghĩa là gì?
3. 3Đặt h(n) = 0 cho mọi nút thì A sao thoái hóa thành gì?
4. 4Có hai heuristic đều chấp nhận được, h2(n) lớn hơn hoặc bằng h1(n) với mọi n. Nên chọn cái nào?

Tóm tắt

A* là điểm gặp nhau của hai ý tưởng. Từ Dijkstra, nó thừa hưởng việc ghi sổ chi phí thật đã đi, ký hiệu g, thứ giữ cho nó không bị dụ vào những đường vòng đắt đỏ. Từ tìm kiếm tham lam, nó thừa hưởng việc nhìn về phía trước bằng ước lượng h, thứ giúp nó khỏi phí công dò về hướng ngược đích. Nó xếp hạng biên bằng tổng f = g + h trong hàng đợi ưu tiên và luôn mở nút có f nhỏ nhất.

Điều kiện để mọi thứ hoạt động nằm ở heuristic. Chấp nhận được, tức không bao giờ ước lượng vượt chi phí thật, là điều kiện đủ cho tính tối ưu trên cây. Nhất quán, mạnh hơn một bậc, cho phép dùng tập đã đóng trên đồ thị mà không cần mở lại nút. Đặt h = 0 thì A* thoái hóa thành tìm kiếm chi phí đều, vẫn tối ưu nhưng mất hết định hướng; cho h phóng đại thì A* nhanh hơn nhưng mất bảo đảm tối ưu. Giữa các heuristic hợp lệ, cái nào lớn hơn ở mọi nút thì thống trị và mở ít nút hơn, nên nghệ thuật thiết kế là đẩy h lên sát h* nhất có thể mà không vượt qua, và cách sinh heuristic đáng tin nhất là nới lỏng bài toán. Cuối cùng, đừng quên cái giá: A* giữ mọi nút đã sinh trong bộ nhớ, nên trên bài toán lớn chính bộ nhớ mới là thứ đánh gục nó.

Ghi nhớ

A* mở rộng nút có f = g + h nhỏ nhất: kết hợp chi phí đã đi g và ước lượng còn lại h. Với heuristic không phóng đại, A* đảm bảo đường rẻ nhất mà thường mở rộng ít nút hơn hẳn tìm kiếm mù. Chất lượng heuristic quyết định tốc độ.