Là tìm kiếm theo độ sâu được hướng dẫn bởi hàm đánh giá

Có thể tìm ra nghiệm ở không gian vô hạn

Luôn tìm ra nghiệm tối ưu toàn cục

Có thể mắc kẹt ở độ sâu vô hạn của cây tìm kiếm

Hàm đánh giá được tính bằng chi phí từ đỉnh hiện thời tới trạng thái đích

Thường nhanh hơn và hiệu quả hơn

Tìm nghiệm tối ưu

Không cần xây dựng hàm đánh giá

Phụ thuộc vào chất lượng của hàm đánh giá

Có thể dẫn đến kết quả không tối ưu nếu hàm đánh giá không chính xác

Luôn chậm hơn tìm kiếm mù

Không thể áp dụng cho bài toán thực tế

Leo đồi chỉ xem xét các đỉnh con của đỉnh hiện tại

Tốt nhất - đầu tiên có thể quay lại các đỉnh ở mức trước

Leo đồi không sử dụng hàm đánh giá

Tốt nhất - đầu tiên không sử dụng hàm đánh giá

h(u) càng nhỏ thì trạng thái u càng gần đích

h(u) dùng để đo khoảng cách từ trạng thái u đến trạng thái đích

h(u) càng lớn thì trạng thái u được ưu tiên phát triển trước

h(u) có thể dẫn đến sai lầm nếu không được thiết kế đúng

Làm cho tìm kiếm nhanh hơn nhờ hướng dẫn đi đúng hướng

Dùng để tính chi phí thực tế đã đi từ trạng thái ban đầu

Được dùng để quyết định nào sẽ được phát triển tiếp theo

Là công cụ thay thế hoàn toàn thuật toán tìm kiếm theo chiều sâu

Chọn trạng thái có giá trị nhỏ nhất để phát triển tiếp

Luôn phát triển tất cả các trạng thái ở cùng một mức như tìm kiếm theo bề rộng

Có thể phát triển trạng thái ở mức sâu hơn nếu h(u) nhỏ

Không dùng bất kỳ thông tin nào ngoài thứ tự các mức

Beam search chỉ phát triển k đỉnh tốt nhất ở mỗi mức

Beam search dùng hàm đánh giá để giới hạn nhánh mở rộng

Beam search phát triển toàn bộ các đỉnh như theo chiều rộng

Beam search không cần hàm đánh giá

Vì chúng là 2 node đầu tiên theo thứ tự từ điển

Vì chúng có điểm số cao nhất trong 5 nhánh đầu tiên

Vì chúng tạo ra nhiều node con hơn so với node khác

Vì các node khác có điểm thấp hơn: C = -123, D = -23, B = -11.4

Hill-Climbing chỉ chọn trạng thái tốt nhất trong số các con của trạng thái hiện tại

Best-First Search có thể chọn lại trạng thái cũ nếu nó có hàm đánh giá tốt nhất

Hill-Climbing luôn chọn trạng thái có giá trị nhỏ nhất

Best-First Search không sử dụng hàm đánh giá

Có thể đòi hỏi bộ nhớ lớn để lưu trữ các nút đã khám phá

Hiệu quả phụ thuộc vào chất lượng của hàm heuristic

Luôn chậm hơn tìm kiếm mù

Không thể áp dụng cho bài toán thực tế

Loại bỏ được các nhánh không triển vọng

Giảm đáng kể không gian tìm kiếm

Luôn phải khám phá tất cả các khả năng

Thuật toán nhánh và cận không sử dụng hàm

Sử dụng hàm tính tổng chi phí từ trạng thái ban đầu đến trạng thái hiện tại

Không cần hàm heuristic

Luôn tìm ra đường đi ngắn nhất mà không cần hàm heuristic

h(n) là ước tính chi phí từ đỉnh n đến đích

Khi cận dưới của nhánh đó lớn hơn giá trị nghiệm tốt nhất hiện tại

Khi không đủ bộ nhớ để lưu trữ kết quả

Khi nhánh đó quá dài

Khi đã khám phá đủ số nhánh

Hàm g(u) đo độ dài đường đi từ trạng thái ban đầu đến u.

Hàm h(u) phải luôn đánh giá lớn hơn độ dài thực tế đến đích để đảm bảo tối ưu.

Hàm h(u) là ước lượng khoảng cách từ u đến trạng thái đích.

Hàm f(u) càng nhỏ thì nút u càng được ưu tiên mở rộng.

Là hàm đo khoảng cách thực sự từ u đến đích.

. Là hàm đánh giá thấp nếu h(u) ≤ khoảng cách thật đến đích.

   C. Có thể ảnh hưởng đến tính tối ưu của thuật toán nếu không được thiết kế đúng.

   D. Luôn phải bằng 0 ở trạng thái đích.

A. A* có thể dẫn robot đi theo đường vòng nếu h(n) đánh giá sai

B. Nếu h(n) chấp nhận được, robot sẽ đi đường tối ưu

C. h(n) cần phản ánh đúng không gian (có tường, vật cản)

D. Nếu h(n)=0, robot sẽ chọn bất kỳ đường nào miễn gần

A. Nếu h(n) đánh giá quá thấp, A* có thể tốn nhiều thời gian do mở rộng không cần thiết

B. Nếu h(n) quá cao, A* có thể bỏ sót đường đi tối ưu

C. Nếu h(n)=0 với mọi n, A* trở thành thuật toán Dijkstra

D. A* không thể áp dụng cho mạng động (thay đổi thời gian truyền)

A. Nếu h(n) không tính đến kẹt xe, đường đi tìm được có thể không tối ưu

B. Nếu g(n) được cập nhật liên tục theo dữ liệu giao thông, A* sẽ phản ứng tốt với thay đổi

C. A* vẫn đảm bảo tìm được lời giải nếu h(n) không chấp nhận được

D. A* phù hợp với bài toán có nhiều mục tiêu di chuyển đồng thời

A. Khi h(n) đánh giá đúng hoặc thấp hơn khoảng cách thực tế đến đích

B. Khi môi trường không thay đổi trong quá trình di chuyển

C. Khi g(n) và h(n) đều được cập nhật theo thời gian thực

D. Khi h(n) lớn thực tế để giảm số nút mở rộng

   A. Nhánh và cận giúp loại bỏ các tuyến không khả thi trước khi xét đến cùng

   B. Cận dưới được tính càng chặt thì thuật toán càng nhanh

   C. Thuật toán luôn đảm bảo tìm được nghiệm tối ưu nếu không cắt sớm

   D. Thuật toán chỉ áp dụng tốt cho bài toán có dưới 10 điểm giao hàng

Có thể loại bỏ nhanh các lịch thi không hợp lệ mà không cần kiểm tra toàn bộ

Giảm số lượng tổ hợp cần xét bằng cách đánh giá sớm tính khả thi

Luôn đảm bảo có ít môn thi nhất

Đảm bảo kiểm tra toàn bộ không gian lời giải để tìm phương án tối ưu

Giải quyết bài toán tương tự như Balo (Knapsack)

Có thể dừng sớm nhánh nếu tổng trọng lượng vượt giới hạn

Đảm bảo tìm được nghiệm đúng nếu cận trên không được tính chính xác

Thời gian thực thi phụ thuộc vào chiến lược chọn nhánh mở rộng

Vì không gian tìm kiếm dạng tổ hợp, có thể cắt bỏ nhánh kém hiệu quả

Vì mỗi nhánh thường ứng với một phần công tạm thời

Vì luôn tồn tại chiến lược chọn nhánh viên tốt nhất cho mỗi nhiệm vụ

Vì có thể tính cận dưới để dừng sớm các nhánh kém

Tìm kiếm theo chiều rộng

Tìm kiếm toàn bộ không gian trạng thái

Tìm kiếm theo chiến lược heuristic như Leo đồi (Hill-Climbing)

Tìm kiếm A*

   A. Vị trí chính xác của các quân trên bàn cờ

   B. . Lượt chơi hiện tại thuộc về người hay máy

C. Danh sách các nước đi hợp lệ tiếp theo

   D. Tốc độ xử lý CPU của thiết bị chơi

Áp dụng giới hạn độ sâu tìm kiếm

Sắp xếp các nước đi sao cho nước tốt được duyệt trước

Tăng kích thước bàn cờ

Loại bỏ các trạng thái đã duyệt qua trước đó

Vị trí tương đối giữa quân Trắng và quân Đen

Tổng số quân Trắng còn lại

Số lượt đi tối ưu còn lại đến thắng

Khả năng quân Trắng trực tiếp chặn đường đi của quân Đen

   A. Ở mỗi mức, chỉ 2 đỉnh có điểm số tốt nhất được chọn để mở rộng

   B. Mỗi node con được đánh giá bằng điểm số riêng biệt và giữ lại theo điểm

   C. Chuỗi có điểm cao nhất toàn cục luôn được chọn mở rộng tiếp theo

   D. Beam search có thể bỏ qua chuỗi có điểm tổng cao hơn vì chỉ xét theo mức