NEW
Font size
Worksheetstuần 4
Total questions: 31
Worksheet time: 16mins
Cho đồ thị không gian trạng thái, uo = A, T = {H,J}
Áp dụng chiến lược tìm kiếm nhánh cận thì các đỉnh được xét để tìm đường đi ngắn nhất từ U, đến đích là:
A-B-H-I-D-G-C
A-B-H
A-B-H-D-G-C-F-K-J-E
A-B-D-H
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
Thuật toán A* kết thúc khi nào?
Khi đánh giá g(u)=0 và h(u)!=0
Khi tìm thấy trạng thái g(u)=h(u)
Khi tìm thấy trạng thái đích hoặc danh sách chờ trống
Khi trạng thái chờ quá lớn
Chi phí trong phần nhánh thuật toán để:
Lưu giá trị f(u)
Lưu giá trị đường đi tốt cho tới thời điểm hiện tại
Lưu giá trị h(u)
Lưu số đỉnh
Đ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á …
Đường đi dài từ u0 đến u
Độ dài đường đi từ đỉnh u bất kỳ đến đích
Số lượng đỉnh đã duyệt
Giá trị heuristic của u
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ục
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ố
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)
Hàm đánh giá trong thuật toán A* được biểu thị dưới dạng nào?
f(u)=g(u)
f(u)=h(u)
f(u)=g(u)+h(u)
f(u)=g(u)×h(u)
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
Trạng thái chờ để phát triển
Các trạng thái đã phát triển
Các trạng thái và các trạng thái chờ được phát triển
Trong thuật toán A*, hàng ưu tiên được sắp xếp theo giá trị nào?
g(u)
h(u)
f(u)
f(u) + g(u)
Thuật toán nào sau đây thuộc tính 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
Thuật toán tìm kiếm f(u)
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)
g(u)+k(u,v)
g(u)
h(u)
Cho đồ thị không gian trạng thái sau: U0=A; T= {I, E, J} Áp dụng chiến lược tìm kiếm A* thì đường đi tìm được có độ dài đường đi ngắn nhất là:
3
8
15
10
Cho đồ thị không gian trạng thái sau: U0=A; T= {I, E, J} Tính giá trị f(u) tại đỉnh F.
13
12
29
7
Uo=A; T= {I, E, J}
Áp dụng chiến lược tìm kiếm A* thì các đỉnh được xét để tìm đường đi ngắn nhất từ Uo đến đích là:
A-B-D-I
D-B-I
A-B-C-D-H-I
D-C-E
Uo=A; T = {H, J}
Áp dụng chiến lược tìm kiếm A* thì các đỉnh được xét để tìm đường đi ngắn nhất từ Uo đến đích là:
A-B-D-H
D-B-C-H
C-E-F-J
D-B-C
Cho đồ thị không gian trạng thái, uo = A, T = {H,J}
Áp dụng chiến lược tìm kiếm A* thì đường đi tìm được có độ dài đường đi ngắn nhất là:
3
4
5
6
Cho đồ thị không gian trạng thái, uo = A, T = {H,J}
Áp dụng chiến lược tìm kiếm nhánh cận thì đường đi ngắn nhất tìm được là.
3
4
5
6
Uo = A; T = {H,J}
Áp dụng chiến lược tìm kiếm nhánh cận thì đường đi ngắn nhất từ Uo đến đích tìm được là:
A-B-H-D-G-C
A-B-H
A-B-H-D-G-C-F-K-J-E
A-B-D-H
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 sâu lặp 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 tốt nhất đầu tiên kết hợp hàm đánh giá f(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
Uo=A; T= {I, E, J}
Tính giá trị f(u) tại đỉnh K
18
32
38
12
Cost trong thuật toán nhánh cận để:
Lưu giá trị f(u)
Lưu giá trị đường đi tốt cho tới thời điểm hiện tại
Lưu giá trị h(u)
Lưu số đỉnh đã xét
Uo=A; T= {I, E, J}. Giá trị g(u) tại đỉnh F là:
9
21
29
7
Uo= T = {H,J}. Áp dụng chiến lược tìm kiếm A* thì đường đi ngắn nhất tìm được là:
A-B-D-H
A-B-D-C-H
A-B-D-G-H
A-B-H
Uo=A; T = {H, J}
Áp dụng chiến lược tìm kiếm nhánh cận thì các đỉnh được xét để tìm đường đi ngắn nhất từ Uo đến đích là:
A-B-H-I-D-G-C
A-B-H-I-D-G-C-E-F-J-K
A-B-H
A-D-B-C-H
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
Với trạng thái ban đầu Un = {A}; 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à:
24
36
41
53
Cho đồ thị không gian trạng thái, uo = A, T = {H,J}
Áp dụng chiến lược tìm kiếm nhánh cận thì các đỉnh được xét để tìm đường đi ngắn nhất từ U, đến đích là:
A-B-H-I-D-G-C
A-B-H
A-B-H-D-G-C-F-K-J-E
A-B-D-H
