Tip:
Highlight text to annotate it
X
Cho trước yêu cầu tìm kiếm xa nhất không mang tính tối ưu
tại sao ai lại dùng nó?
câu trả lời là nó liên quan đến yêu cầu lưu trữ.
ở đây tôi đã minh họa không gian trạng thái
gồm một cây nhị phân lớn, thậm chí vô hạn.
khi ta đạt đến cấp độ 1, 2, 3 đến n,
cây này ngày càng mở rộng.
giờ thi chúng ta cùng xem xét phần rìa xa nhất cho mỗi thuật toán tìm kiếm này.
Cho tìm kiếm gần nhất, chúng ta biết phần rìa trông sẽ như thế,
thế nên khi đạt đến cấp độ n, chúng ta sẽ cần không gian tích trữ cho
2 đến n trong tìm kiếm gần nhất.
Cho tìm kiếm chi phí tốt nhất, phần rìa sẽ phức tạp hơn.
nó sẽ phải tìm ra chi phí này,
nhưng nó cũng sẽ có tổng số nút tương tự.
Nhưng với tìm kiếm xa nhất, khi đi xuống cây, chúng ta bắt đầu xuống nhánh này,
và chúng ta trở lại, nhưng ở bất cứ điểm nào, phần rìa của ta cũng sẽ có n nút
thay vì là từ 2 đến n nút, nên sẽ tiết kiệm rất nhiều cho kiểu tìm kiếm này.
giờ thì dĩ nhiên, nếu vẫn theo lộ trình đã đi qua,
ta không có tiết kiệm được nhiều thế.
nhưng không có phần lộ trình đã đi qua thì tìm kiếm xa nhất có ưu điểm lớn
về mặt không được tiết kiệm.
Một thuộc tính nữa của thuật toán cần xem xét
là tính toàn vẹn, nghĩa là nếu có mục tiêu
thì thuật toán sẽ tìm ra chứ?
chúng ta hãy di chuyển từ các cây lớn xuống những cây vô hạn,
và giả dụ là có 1 mục đích ẩn ở đâu đó sâu trong cây đó.
và câu hỏi là, mỗi một thuật toán này thì hoàn thành?
nghĩa là, chúng có đảm bảo sẽ tìm ra đường đến mục tiêu?
hãy đánh dấu và ô các thuật toán bạn cho là hoàn thành trong ngữ cảnh này.