WorksheetsThuật toán tìm kiếm và A* – Trích xuất câu hỏi từ worksheet
Total questions: 44
Worksheet time: 22mins
Thuật toán nhánh cận là:
Tìm kiếm theo độ sâu kết hợp hàm đánh giá f(u)
Tìm kiếm theo bề rộng kết hợp hàm đánh giá (u)
Tìm kiếm sâu lặp kết hợp hàm đánh giá f(u)
Tìm kiếm tốt nhất đầu tiên kết hợp hàm đánh giá (u)
Trong thuật toán A*, thành phần g(u) của hàm đánh giá đại diện cho điều gì?
Khoảng cách ước lượng từ trạng thái hiện tại đến đích
Chi phí từ trạng thái bắt đầu đến trạng thái hiện tại
Tổng chi phí từ trạng thái gốc đến đích
Chi phí từ trạng thái hiện tại đến trạng thái con
Thuật toán A* kết thúc khi nào?
Khi hàm đánh giá g(u)=0 và h(u)!=0
Khi Tìm thấy trạng thái có g(u)=h(u)
Khi Tìm thấy trạng thái đích hoặc danh sách chờ rỗng
Khi số lượng trạng thái chờ quá lớn
Trong thuật toán nhánh cận điều kiện cắt nhánh là
Đỉnh mang ra để xét có f(u) > cost
Đỉnh mang ra để xét có f(u) < cost
Đỉnh mang ra để xét có h(u) > cost
Đỉnh mang ra để xét có g(u) < cost
Điểm dừng của thuật toán nhánh cận
Danh sách L rỗng
Danh sách L khác rỗng
Danh sách L1 rỗng
Đỉnh được xét thuộc T
Trong Tìm kiếm tối ưu g(u) là giá trị số đánh giá.....
Độ dài đường đi từ u0 đến u
Độ dài đường đi từ v đến u
Độ dài đường đi đến u
Độ dài đường đi từ đỉnh u đến đỉnh bất kỳ
Thuật toán nào sử dụng hàm đánh giá f(u)=g(u)+h(u) trong quá trình Tìm kiếm
Tìm kiếm nhánh cận
Tìm kiếm tốt nhất đầu tiên
Tìm kiếm leo đồi
Tìm kiếm cắt cụt
Hàm đánh giá trong thuật toán A* được biểu diễn dưới dạng nào?
F(u) = g(u) + h(u)
f(u) = g(u) x h(u)
F(u) = g(u)
F(u) = h(u)
Thuật toán nào sau đây thuộc tìm kiếm tối ưu?
Thuật toán tìm kiếm sâu lặp
Thuật toán tìm kiếm nhánh cận
Thuật toán tìm kiếm leo đồi
Trong thuật toán A*, hàng đợi ưu tiên được sắp xếp theo giá trị nào?
f(u)
g(u)
h(u)
a
Thuật toán A* là:
Tìm kiếm theo độ sâu kết hợp hàm đánh giá f(u)
Tìm kiếm theo bề rộng kết hợp hàm đánh giá f(u)
Tìm kiếm leo đồi kết hợp hàm đánh giá f(u)
Tìm kiếm sâu lặp kết hợp hàm đánh giá f(u)
Thành phần h(u) trong hàm đánh giá của A* được gọi là gì?
Giá trị chi phí
Giá trị heuristic
Chi phí thực tế
Chi phí tối ưu
Cost trong thuật toán nhánh cận để:
Lưu giá trị f(u)
Lưu giá trị đường đi tốt nhất cho thời điểm hiện tại
Lưu giá trị h(u)
Lưu số đỉnh đã xét
Trong thuật toán tìm kiếm nhánh cận hàm đánh giá f(u) xác định
g(u)+h(u)
h(u)+k(u)
g(u)+k(u,v)
g(u)+k(u,v)+h(u)
Trong bài toán người du lịch (Travelling Salesman Problem - TSP), thuật toán nhánh và cận (Branch and Bound) giúp giải quyết vấn đề gì?
Tìm ra tất cả các đường đi có thể giữa các thành phố
Tìm đường đi ngắn nhất qua tất cả các thành phố đúng một lần
Tìm ra một đường đi gần đúng
Tính toán đường vận chuyển giữa các thành phố
Uo = A; T = {I, E, J}. Tính giá trị f(u) tại đỉnh K. Sử dụng sơ đồ cây trọng số như trên hình.
18
32
38
12
Uo = A; T = {I, E, J}. Tính giá trị f(u) tại đỉnh F dựa trên sơ đồ cây trọng số trong hình.
13
12
29
7
Với trạng thái ban đầu U0 = {A} và tập trạng thái kết thúc T = {B}, áp dụng thuật toán A*, giá trị f(G) là bao nhiêu?
24
36
41
53
Cho đồ thị không gian trạng thái với U0 = A và T = {H, J}. Áp dụng chiến lược Tìm kiếm nhánh cận, độ dài đường đi ngắn nhất tìm được là bao nhiêu?
3
4
5
6
Cho U0 = A và T = {I, E, J}. Áp dụng Tìm kiếm A*, độ dài đường đi ngắn nhất tìm được là bao nhiêu?
3
8
15
10
U0 = A; T = {I, E, J}. Giá trị g(u) tại đỉnh F là bao nhiêu?
9
29
21
7
Uo = A, T = {H, J}. Áp dụng chiến lược tìm kiếm A*, hãy cho biết thứ tự các đỉnh được xét để tìm đường đi ngắn nhất từ Uo đến đích.
A-B-C-H
A-B-D-C-H
A-B-D-G-H
A-B-D-H
Cho Uo = A, T = {H, J}. Áp dụng chiến lược tìm kiếm nhánh cận, hãy cho biết thứ tự các đỉnh được xét để tìm đường đi ngắn nhất từ Uo đến đích.
A-B-H-I-D-G-C
A-B-H
A-B-H-D-G-C-F-K-J-E
A-B-D-H
Uo = A, T = {H, J}. Áp dụng chiến lược tìm kiếm A*, hãy chọn đường đi ngắn nhất tìm được.
A-B-D-H
A-B-D-G-H
A-B-D-C-H
A-B-H
U0 = A; T = {H, J}. Áp dụng chiến lược tìm kiếm nhánh cận, đường đi ngắn nhất từ U0 đến đích tìm được là:
A-B-H-D-G-C
A-B-H-D-G-C-F-K-J-E
A-B-H
A-B-D-H
U0 = A; T = {H, J}. Áp dụng chiến lược tìm kiếm nhánh cận, các đỉnh được xét để tìm đường đi ngắn nhất từ U0 đến đích là:
A-B-H-D-G-C
A-B-H
A-B-H-I-D-G-C-E-F-J-K
A-D-B-C-H
U0 = A; T = {H, J}. Áp dụng chiến lược tìm kiếm A*, các đỉnh được xét để tìm đường đi ngắn nhất từ U0 đến đích là:
A-B-D-H
A-C-E-F-J
A-D-B-C-H
A-D-B-C
U0 = A; T = {H, J}. Áp dụng chiến lược tìm kiếm A*, độ dài đường đi ngắn nhất là:
3
4
5
6
U0 = A; T = {I, E, J}. Áp dụng chiến lược tìm kiếm A*, các đỉnh được xét để tìm đường đi ngắn nhất từ U0 đến đích là:
A-B-D-I
A-D-B-I
A-B-C-D-H-I
A-D-C-E
Trong thuật toán nhánh cận, L1 để lưu:
Các trạng thái kề của u đã được sắp xếp
Tập các trạng thái đã thăm theo thứ tự xuất hiện
Mọi trạng thái của toàn bộ không gian tìm kiếm
Chỉ một trạng thái có chi phí lớn nhất
Phát biểu nào sau đây là đúng về các hàm đánh giá trong tìm kiếm tối ưu?
Hàm f(u) càng nhỏ thì nút u càng được ưu tiên mở rộng
Hàm h(u) là ước lượng khoảng cách từ u đến trạng thái đích
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
Một nhà máy cần xếp hàng hóa lên xe tải sao cho tổng khối lượng không vượt quá tải trọng, và tổng giá trị hàng là lớn nhất. Họ dùng thuật toán nhánh và cận. Chọn nhận định đúng về hiệu quả khi áp dụng thuật toán nhánh và cận.
Có thể dừng mở sớm nhánh nếu tổng trọng lượng vượt giới hạn
Giải quyết bài toán tương tự như Balo (Knapsack)
Thời gian thực thi phụ thuộc vào chiến lược chọn nhánh mở rộng
Không đảm bảo tìm được nghiệm nếu cận trên không được tính chính xác
Bạn xây dựng phần mềm chơi cờ (game AI), trong đó cần nhanh chóng chọn nước đi tốt nhất trong thời gian giới hạn, dù không chắc nước đó là tối ưu. Thuật toán nào sau đây là lựa chọn phù hợp nhất?
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 A*
Tìm kiếm theo chiến lược heuristic như Leo đồi (Hill-Climbing)
Trong thuật toán nhánh và cận, khi nào một nhánh bị cắt tỉa?
Khi đã khám phá đủ số nhánh
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
Hạn chế của thuật toán A* là gì?
Luôn chậm hơn tìm kiếm mù
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
Không thể áp dụng cho bài toán thực tế
Ưu điểm của thuật toán nhánh và cận so với tìm kiếm mù là gì? (Sinh viên chọn 2 phương án đúng nhất)
Thuật toán nhánh và cận không sử dụng hàm
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
Trong một ứng dụng chỉ đường xe tự hành trong kho hàng, xe cần tìm đường từ vị trí A đến G trong khi tránh các kệ hàng và vật cản. Biết: g(n) là khoảng cách thực tế đã đi; h(n) là khoảng cách ước lượng đến G. Khi nào A* cho kết quả tối ưu nhất trong bài toán này?
Khi g(n) và h(n) đều được cập nhật theo thời gian thực
Khi h(n) đánh giá đúng hoặc thấp hơn khoảng cách thực tế đến đích
Khi môi trường không thay đổi trong quá trình di chuyển
Khi h(n) lớn hơn thực tế để giảm số nút mở rộng
Một hệ thống định tuyến mạng viễn thông sử dụng thuật toán A* để xác định đường truyền dữ liệu tối ưu từ trạm gửi đến thiết bị G. Thông tin h(n) được lấy từ độ trễ ước lượng giữa các nút. Những nhận định nào sau đây đúng khi áp dụng A* trong bài toán định tuyến mạng? (Sinh viên chọn 3 phương án đúng nhất)
Nếu h(n) quá cao, A* có thể bỏ sót đường đi tối ưu
Nếu h(n)=0 với mọi n, A* trở thành thuật toán Dijkstra
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
A* không thể áp dụng cho mạng động (thay đổi thời gian thực)
Bạn lập trình một robot hút bụi di chuyển trong nhà. Robot cần đi từ vị trí A đến G, tránh các vật cản. Biết khoảng cách thực tế giữa các phòng và h(n) là khoảng cách ước lượng từ n đến G theo đường thẳng. Chọn các đặc điểm đúng về việc áp dụng A* trong trường hợp này. (Sinh viên chọn 3 phương án đúng nhất)
Nếu h(n)=0, robot sẽ chọn bất kỳ đường nào miễn gần
h(n) cần phản ánh đúng không gian (có tường, vật cản)
Nếu h(n) chấp nhận được, robot sẽ đi đường tối ưu
A* có thể dẫn robot đi theo đường vòng nếu h(n) đánh giá sai
Chọn các đặc điểm đúng về hàm heuristic h(u) trong tìm kiếm tối ưu: (Sinh viên chọn 3 phương án đúng nhất)
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
Là hàm đo khoảng cách thực sự từ u đến đích
Luôn phải bằng 0 ở trạng thái đích
Là hàm đánh giá thấp nếu h(u) <= khoảng cách thật đến đích
Một công ty giao hàng muốn tối ưu tuyến đường để nhân viên đi qua tất cả các địa điểm giao hàng một lần và quay về kho (bài toán người giao hàng - TSP). Họ áp dụng thuật toán nhánh và cận. Những nhận định nào sau đây đúng? (Sinh viên chọn 3 phương án đúng nhất)
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
Thuật toán chỉ áp dụng tốt cho bài toán có dưới 10 điểm giao hàng
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
Cận dưới tính càng chặt thì thuật toán càng nhanh
Bạn lập trình một robot hút bụi di chuyển trong nhà. Robot cần đi từ vị trí A đến G, tránh các vật cản. Biết khoảng cách thực tế giữa các phòng và h(n) là khoảng cách ước lượng từ n đến G theo đường thẳng. Chọn các đặc điểm đúng về việc áp dụng A* trong trường hợp này. (Sinh viên chọn 3 phương án đúng nhất)
Nếu h(n)=0, robot sẽ chọn bất kỳ đường nào miễn gần
h(n) cần phản ánh đúng không gian (có tường, vật cản)
Nếu h(n) chấp nhận được, robot sẽ đi đường tối ưu
A* có thể dẫn robot đi theo đường vòng nếu h(n) đánh giá sai
Trong bài toán phân công công việc cho 5 nhân viên với 5 nhiệm vụ sao cho tổng chi phí là thấp nhất, bạn áp dụng thuật toán nhánh và cận. Tại sao nhánh và cận phù hợp cho bài toán này? (Sinh viên chọn 3 phương án đúng nhất)
Vì luôn tồn tại chiến lược chọn nhân viên tốt nhất cho mỗi nhiệm vụ
Vì mỗi nhánh tương ứng với một phân công tạm thời
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ì có thể tính cận dưới để dừng sớm các nhánh kém
Chọn các đặc điểm đúng về hàm heuristic h(u) trong tìm kiếm tối ưu: (Sinh viên chọn 3 phương án đúng nhất)
Luôn phải bằng 0 ở trạng thái đích
Là hàm do khoảng cách thực sự từ u đến đích
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
Là hàm đánh giá thấp nếu h(u) <= khoảng cách thật đến đích
