Tip:
Highlight text to annotate it
X
Đây là đáp án.
Tìm kiếm theo chiều rộng (Breadth-first search) mở rộng node theo thứ tự sau.
1, 2, 3, 4, 5, 6, 7
Như vậy, nó mở rộng theo hướng sọc ngang, theo chiều rộng trước.
Phương pháp này có tối ưu?
Nó luôn mở rộng theo con đường ngắn nhất trước.
và do đó, bất cứ khi nào chưa đạt tới đích mong muốn, nó sẽ tìm ra con đường đi bằng cách
kiểm tra những đường đi ngắn hơn, và vì vậy, phương pháp này tối ưu.
Phương pháp Cheapest First, đầu tiên chúng ta mở rộng đường đi với chiều dài bằng 0,
sau đó với chiều dài bằng 2
với chiều dài bằng 4, chiều dài bằng 5
chiều dài bằng 6, chiều dài bằng 7, và cuối cùng là chiều dài bằng 8.
và như chúng ta thấy, nó đảm bảo tìm ra con đường với chi phí thấp nhất,
giả thiết là tất cả những bước đi có chi phí không âm.
Phương pháp tìm kiếm theo chiều sâu (Depth-first search) duyệt theo chiều sâu trước,
vì thế nó sẽ duyệt 1, 2, 3, và rồi qua 4,
sau đó qua 5, 6, 7.
Và bạn có thể thấy nó không cố gắng tìm ra con đường ngắn nhất.
Giả sử rằng đích đến là vị trí 5 hay vị trí 3.
Nó sẽ đi đến đích theo con đường dài hơn đến vị trí 3
và sẽ không đi đến đích ở vị trí 5, dù con đường đến vị trí 5 ngắn hơn.
Vì thế, phương pháp này không tối ưu.