Cho đồ thị không gian trạng thái G = {V, E}

1.     Cho đồ thị không gian trạng thái G={V,E} với tập các đỉnh V={A, C, D, E, F, G, H, I, K, B} và tập các cung E={(A,C), (A,D), (A,E), (C,F), (D,F), (D,I), (E,I), (E,G), (E,K), (F,B), (I,B), (I,G), (G,B), (G,H), (H,B). Giá trị hàm đánh giá ghi tại các đỉnh như sau: A:21, C:17, D:8, E:9, F:10, I:9, G:5, K:14, H:3, B:0.

a)     Hãy vẽ đồ thị không gian trạng thái trên, lựa chọn một thuật toán và xây dựng cây tìm kiếm mô phỏng các bước thực hiện thuật toán tìm kiếm đường đi với đỉnh xuất phát là {A} và đỉnh đích là {B}.

b)    Nhận xét về ưu điểm và nhược điểm của thuật toán được lựa chọn ở câu a)