truongngocdai
03-04-2005, 20:42
Không biết đã ai nghe nói đến thuật toán: Tìm kiếm ưu tiên tối ưu (best-first search) chưa vậy.
Nó có 3 thuật giải con dựa vào nó:
1. Thuật giải AT
2. Thuật giải AKT
3. Thuật giải A*
Ưu điểm của tìm kiếm theo chiều sâu là không phải quan tâm đến sự mở rộng của tất cả các nhánh. Ưu điểm của tìm kiếm chiều rộng là không bị sa vào các đường dẫn bế tắc (các nhánh cụt). Tìm kiếm ưu tiên tối ưu sẽ kết hợp 2 phương pháp trên cho phép ta đi theo một con đường duy nhất tại một thời điểm, nhưng đồng thời vẫn "quan sát" được những hướng khác. Nếu con đường đang đi "có vẻ" không triển vọng bằng những con đường ta đang "quan sát" ta sẽ chuyển sang đi theo một trong số các con đường này. Để tiện lợi ta sẽ dùng chữ viết tắt BFS thay cho tên gọi tìm kiếm ưu tiên tối ưu.
Một cách cụ thể, tại mỗi bước của tìm kiếm BFS, ta chọn đi theo trạng thái có khả năng cao nhất trong số các trạng thái đã được xét cho đến thời điểm đó. (khác với leo đồi dốc đứng là chỉ chọn trạng thái có khả năng cao nhất trong số các trạng thái kế tiếp có thể đến được từ trạng thái hiện tại). Như vậy, với tiếp cận này, ta sẽ ưu tiên đi vào những nhánh tìm kiếm có khả năng nhất (giống tìm kiếm leo đồi dốc đứng), nhưng ta sẽ không bị lẩn quẩn trong các nhánh này vì nếu càng đi sâu vào một hướng mà ta phát hiện ra rằng hướng này càng đi thì càng tệ, đến mức nó xấu hơn cả những hướng mà ta chưa đi, thì ta sẽ không đi tiếp hướng hiện tại nữa mà chọn đi theo một hướng tốt nhất trong số những hướng chưa đi. Đó là tư tưởng chủ đạo của tìm kiếm Best First Search.
Cách cài đặt thuật giải Best First Search
Để cài đặt các thuật giải theo kiểu tìm kiếm BFS, người ta thường cần dùng 2 tập hợp sau :
OPEN : tập chứa các trạng thái đã được sinh ra nhưng chưa được xét đến (vì ta đã chọn một trạng thái khác). Thực ra, OPEN là một loại hàng đợi ưu tiên (priority queue) mà trong đó, phần tử có độ ưu tiên cao nhất là phần tử tốt nhất. Người ta thường cài đặt hàng đợi ưu tiên bằng Heap. Các bạn có thể tham khảo thêm trong các tài liệu về Cấu trúc dữ liệu về loại dữ liệu này.
CLOSE : tập chứa các trạng thái đã được xét đến. Chúng ta cần lưu trữ những trạng thái này trong bộ nhớ để đề phòng trường hợp khi một trạng thái mới được tạo ra lại trùng với một trạng thái mà ta đã xét đến trước đó. Trong trường hợp không gian tìm kiếm có dạng cây thì không cần dùng tập này.
Thuật giải BEST-FIRST SEARCH
1. Đặt OPEN chứa trạng thái khởi đầu.
2. Cho đến khi tìm được trạng thái đích hoặc không còn nút nào trong OPEN, thực hiện :
2.a. Chọn trạng thái tốt nhất (Tmax) trong OPEN (và xóa Tmax khỏi OPEN)
2.b. Nếu Tmax là trạng thái kết thúc thì thoát.
2.c. Ngược lại, tạo ra các trạng thái kế tiếp Tk có thể có từ trạng thái Tmax. Đối với mỗi trạng thái kế tiếp Tk thực hiện :
Tính f(Tk); Thêm Tk vào OPEN
BFS khá đơn giản. Tuy vậy, trên thực tế, cũng như tìm kiếm chiều sâu và chiều rộng, hiếm khi ta dùng BFS một cách trực tiếp. Thông thường, người ta thường dùng các phiên bản của BFS là AT, AKT và A*
Thuật giải AT nè
Thuật giải AT là một phương pháp tìm kiếm theo kiểu BFS với độ tốt của nút là giá trị hàm g – tổng chiều dài con đường đã đi từ trạng thái bắt đầu đến trạng thái hiện tại.
Thuật giải AT
1. Đặt OPEN chứa trạng thái khởi đầu.
2. Cho đến khi tìm được trạng thái đích hoặc không còn nút nào trong OPEN, thực hiện :
2.a. Chọn trạng thái (Tmax) có giá trị g nhỏ nhất trong OPEN (và xóa Tmax khỏi OPEN)
2.b. Nếu Tmax là trạng thái kết thúc thì thoát.
2.c. Ngược lại, tạo ra các trạng thái kế tiếp Tk có thể có từ trạng thái Tmax. Đối với mỗi trạng thái kế tiếp Tk thực hiện :
g(Tk) = g(Tmax) + cost(Tmax, Tk);
Thêm Tk vào OPEN.
* Vì chỉ sử dụng hàm g (mà không dùng hàm ước lượng h’) fsđể đánh giá độ tốt của một trạng thái nên ta cũng có thể xem AT chỉ là một thuật toán.
Thuật giải AKT nè
(Algorithm for Knowlegeable Tree Search)
Thuật giải AKT mở rộng AT bằng cách sử dụng thêm thông tin ước lượng h’. Độ tốt của một trạng thái f là tổng của hai hàm g và h’.
Thuật giải AKT
1. Đặt OPEN chứa trạng thái khởi đầu.
2. Cho đến khi tìm được trạng thái đích hoặc không còn nút nào trong OPEN, thực hiện :
2.a. Chọn trạng thái (Tmax) có giá trị f nhỏ nhất trong OPEN (và xóa Tmax khỏi OPEN)
2.b. Nếu Tmax là trạng thái kết thúc thì thoát.
2.c. Ngược lại, tạo ra các trạng thái kế tiếp Tk có thể có từ trạng thái Tmax. Đối với mỗi trạng thái kế tiếp Tk thực hiện :
g(Tk) = g(Tmax) + cost(Tmax, Tk);
Tính h’(Tk)
f(Tk) = g(Tk) + h’(Tk);
Thêm Tk vào OPEN.
Thuật giải A* nè
A* là một phiên bản đặc biệt của AKT áp dụng cho trường hợp đồ thị. Thuật giải A* có sử dụng thêm tập hợp CLOSE để lưu trữ những trường hợp đã được xét đến. A* mở rộng AKT bằng cách bổ sung cách giải quyết trường hợp khi "mở" một nút mà nút này đã có sẵn trong OPEN hoặc CLOSE. Khi xét đến một trạng thái Ti bên cạnh việc lưu trữ 3 giá trị cơ bản g,h’, f’ để phản ánh độ tốt của trạng thái đó, A* còn lưu trữ thêm hai thông số sau :
1. Trạng thái cha của trạng thái Ti (ký hiệu là Cha(Ti) : cho biết trạng thái dẫn đến trạng thái Ti. Trong trường hợp có nhiều trạng thái dẫn đến Ti thì chọn Cha(Ti) sao cho chi phí đi từ trạng thái khởi đầu đến Ti là thấp nhất, nghĩa là :
g(Ti) = g(Tcha) + cost(Tcha, Ti) là thấp nhất.
2. Danh sách các trạng thái kế tiếp của Ti : danh sách này lưu trữ các trạng thái kế tiếp Tk của Ti sao cho chi phí đến Tk thông qua Ti từ trạng thái ban đầu là thấp nhất. Thực chất thì danh sách này có thể được tính ra từ thuộc tính Cha của các trạng thái được lưu trữ. Tuy nhiên, việc tính toán này có thể mất nhiều thời gian (khi tập OPEN, CLOSE được mở rộng) nên người ta thường lưu trữ ra một danh sách riêng. Trong thuật toán sau đây, chúng ta sẽ không đề cập đến việc lưu trữ danh sách này. Sau khi hiểu rõ thuật toán, bạn đọc có thể dễ dàng điều chỉnh lại thuật toán để lưu trữ thêm thuộc tính này.
1. Đặt OPEN chỉ chứa T0. Đặt g(T0) = 0, h’(T0) = 0 và f’(T0) = 0.
Đặt CLOSE là tập hợp rỗng.
2. Lặp lại các bước sau cho đến khi gặp điều kiện dừng.
2.a. Nếu OPEN rỗng : bài toán vô nghiệm, thoát.
2.b. Ngược lại, chọn Tmax trong OPEN sao cho f’(Tmax) là nhỏ nhất
2.b.1. Lấy Tmax ra khỏi OPEN và đưa Tmax vào CLOSE.
2.b.2. Nếu Tmax chính là TG thì thoát và thông báo lời giải là Tmax.
2.b.3. Nếu Tmax không phải là TG. Tạo ra danh sách tất cả các trạng thái kế tiếp của Tmax. Gọi một trạng thái này là Tk. Với mỗi Tk, làm các bước sau :
2.b.3.1. Tính g(Tk) = g(Tmax) + cost(Tmax, Tk).
2.b.3.2. Nếu tồn tại Tk’ trong OPEN trùng với Tk.
Nếu g(Tk) < g(Tk’) thì
Đặt g(Tk’) = g(Tk)
Tính lại f’(Tk’)
Đặt Cha(Tk’) = Tmax
2.b.3.3. Nếu tồn tại Tk’ trong CLOSE trùng với Tk.
Nếu g(Tk) < g(Tk’) thì
Đặt g(Tk’) = g(Tk)
Tính lại f’(Tk’)
Đặt Cha(Tk’) = Tmax
Lan truyền sự thay đổi giá trị g, f’ cho tất cả các trạng thái kế tiếp của Ti (ở tất cả các cấp) đã được lưu trữ trong CLOSE và OPEN.
2.b.3.4. Nếu Tk chưa xuất hiện trong cả OPEN lẫn CLOSE thì :
Thêm Tk vào OPEN
Tính : f' (Tk) = g(Tk)+h’(Tk).
Có một số điểm cần giải thích trong thuật giải này. Đầu tiên là việc sau khi đã tìm thấy trạng thái đích TG, làm sao để xây dựng lại được "con đường" từ T0 đến TG. Rất đơn giản, bạn chỉ cần lần ngược theo thuộc tính Cha của các trạng thái đã được lưu trữ trong CLOSE cho đến khi đạt đến T0. Đó chính là "con đường" tối ưu đi từ TG đến T0 (hay nói cách khác là từ T0 đến TG).
Điểm thứ hai là thao tác cập nhật lại g(Tk’) , f’(Tk’) và Cha(Tk’) trong bước 2.b.3.2 và 2.b.3.3. Các thao tác này thể hiện tư tưởng : "luôn chọn con đường tối ưu nhất". Như chúng ta đã biết, giá trị g(Tk’) nhằm lưu trữ chi phí tối ưu thực sự tính từ T0 đến Tk’. Do đó, nếu chúng ta phát hiện thấy một "con đường" khác tốt hơn thông qua Tk (có chi phí nhỏ hơn) con đường hiện tại được lưu trữ thì ta phải chọn "con đường" mới tốt hơn này. Trường hợp 2.b.3.3 phức tạp hơn. Vì từ Tk’ nằm trong tập CLOSE nên từ Tk’ ta đã lưu trữ các trạng thái con kế tiếp xuất phát từ Tk’. Nhưng g(Tk’) thay đổi dẫn đến giá trị g của các trạng thái con này cũng phải thay đổi theo. Và đến lượt các trạng thái con này lại có thể có các các trạng thái con tiếp theo của chúng và cứ thế cho đến khi mỗi nhánh kết thúc với một trạng thái trong OPEN (nghĩa là không có trạng thái con nào nữa). Để thực hiện quá trình cập nhật này, ta hãy thực hiện quá trình duyệt theo chiều sâu với điểm khởi đầu là Tk’. Duyệt đến đâu, ta cập nhật lại g của các trạng thái đến đó ( dùng công thức g(T) = g(Cha(T)) +cost(Cha(T), T) ) và vì thế giá trị f’ của các trạng thái này cũng thay đổi theo.
Một lần nữa, xin nhắc lại rằng, bạn có thể cho rằng tập OPEN lưu trữ các trạng thái "sẽ được xem xét đến sau" còn tập CLOSE lưu trữ các trạng thái "đã được xét đến rồi".
Chà chà, Best First Search có vẻ hay đấy chứ
(Bài viết này có đính kèm 1 file .rar trong đó có bài viết về Best First Search mà tôi tìm được. Nếu ai có hứng thú về Best First Search thì cùng vào đây trao đổi)
Nó có 3 thuật giải con dựa vào nó:
1. Thuật giải AT
2. Thuật giải AKT
3. Thuật giải A*
Ưu điểm của tìm kiếm theo chiều sâu là không phải quan tâm đến sự mở rộng của tất cả các nhánh. Ưu điểm của tìm kiếm chiều rộng là không bị sa vào các đường dẫn bế tắc (các nhánh cụt). Tìm kiếm ưu tiên tối ưu sẽ kết hợp 2 phương pháp trên cho phép ta đi theo một con đường duy nhất tại một thời điểm, nhưng đồng thời vẫn "quan sát" được những hướng khác. Nếu con đường đang đi "có vẻ" không triển vọng bằng những con đường ta đang "quan sát" ta sẽ chuyển sang đi theo một trong số các con đường này. Để tiện lợi ta sẽ dùng chữ viết tắt BFS thay cho tên gọi tìm kiếm ưu tiên tối ưu.
Một cách cụ thể, tại mỗi bước của tìm kiếm BFS, ta chọn đi theo trạng thái có khả năng cao nhất trong số các trạng thái đã được xét cho đến thời điểm đó. (khác với leo đồi dốc đứng là chỉ chọn trạng thái có khả năng cao nhất trong số các trạng thái kế tiếp có thể đến được từ trạng thái hiện tại). Như vậy, với tiếp cận này, ta sẽ ưu tiên đi vào những nhánh tìm kiếm có khả năng nhất (giống tìm kiếm leo đồi dốc đứng), nhưng ta sẽ không bị lẩn quẩn trong các nhánh này vì nếu càng đi sâu vào một hướng mà ta phát hiện ra rằng hướng này càng đi thì càng tệ, đến mức nó xấu hơn cả những hướng mà ta chưa đi, thì ta sẽ không đi tiếp hướng hiện tại nữa mà chọn đi theo một hướng tốt nhất trong số những hướng chưa đi. Đó là tư tưởng chủ đạo của tìm kiếm Best First Search.
Cách cài đặt thuật giải Best First Search
Để cài đặt các thuật giải theo kiểu tìm kiếm BFS, người ta thường cần dùng 2 tập hợp sau :
OPEN : tập chứa các trạng thái đã được sinh ra nhưng chưa được xét đến (vì ta đã chọn một trạng thái khác). Thực ra, OPEN là một loại hàng đợi ưu tiên (priority queue) mà trong đó, phần tử có độ ưu tiên cao nhất là phần tử tốt nhất. Người ta thường cài đặt hàng đợi ưu tiên bằng Heap. Các bạn có thể tham khảo thêm trong các tài liệu về Cấu trúc dữ liệu về loại dữ liệu này.
CLOSE : tập chứa các trạng thái đã được xét đến. Chúng ta cần lưu trữ những trạng thái này trong bộ nhớ để đề phòng trường hợp khi một trạng thái mới được tạo ra lại trùng với một trạng thái mà ta đã xét đến trước đó. Trong trường hợp không gian tìm kiếm có dạng cây thì không cần dùng tập này.
Thuật giải BEST-FIRST SEARCH
1. Đặt OPEN chứa trạng thái khởi đầu.
2. Cho đến khi tìm được trạng thái đích hoặc không còn nút nào trong OPEN, thực hiện :
2.a. Chọn trạng thái tốt nhất (Tmax) trong OPEN (và xóa Tmax khỏi OPEN)
2.b. Nếu Tmax là trạng thái kết thúc thì thoát.
2.c. Ngược lại, tạo ra các trạng thái kế tiếp Tk có thể có từ trạng thái Tmax. Đối với mỗi trạng thái kế tiếp Tk thực hiện :
Tính f(Tk); Thêm Tk vào OPEN
BFS khá đơn giản. Tuy vậy, trên thực tế, cũng như tìm kiếm chiều sâu và chiều rộng, hiếm khi ta dùng BFS một cách trực tiếp. Thông thường, người ta thường dùng các phiên bản của BFS là AT, AKT và A*
Thuật giải AT nè
Thuật giải AT là một phương pháp tìm kiếm theo kiểu BFS với độ tốt của nút là giá trị hàm g – tổng chiều dài con đường đã đi từ trạng thái bắt đầu đến trạng thái hiện tại.
Thuật giải AT
1. Đặt OPEN chứa trạng thái khởi đầu.
2. Cho đến khi tìm được trạng thái đích hoặc không còn nút nào trong OPEN, thực hiện :
2.a. Chọn trạng thái (Tmax) có giá trị g nhỏ nhất trong OPEN (và xóa Tmax khỏi OPEN)
2.b. Nếu Tmax là trạng thái kết thúc thì thoát.
2.c. Ngược lại, tạo ra các trạng thái kế tiếp Tk có thể có từ trạng thái Tmax. Đối với mỗi trạng thái kế tiếp Tk thực hiện :
g(Tk) = g(Tmax) + cost(Tmax, Tk);
Thêm Tk vào OPEN.
* Vì chỉ sử dụng hàm g (mà không dùng hàm ước lượng h’) fsđể đánh giá độ tốt của một trạng thái nên ta cũng có thể xem AT chỉ là một thuật toán.
Thuật giải AKT nè
(Algorithm for Knowlegeable Tree Search)
Thuật giải AKT mở rộng AT bằng cách sử dụng thêm thông tin ước lượng h’. Độ tốt của một trạng thái f là tổng của hai hàm g và h’.
Thuật giải AKT
1. Đặt OPEN chứa trạng thái khởi đầu.
2. Cho đến khi tìm được trạng thái đích hoặc không còn nút nào trong OPEN, thực hiện :
2.a. Chọn trạng thái (Tmax) có giá trị f nhỏ nhất trong OPEN (và xóa Tmax khỏi OPEN)
2.b. Nếu Tmax là trạng thái kết thúc thì thoát.
2.c. Ngược lại, tạo ra các trạng thái kế tiếp Tk có thể có từ trạng thái Tmax. Đối với mỗi trạng thái kế tiếp Tk thực hiện :
g(Tk) = g(Tmax) + cost(Tmax, Tk);
Tính h’(Tk)
f(Tk) = g(Tk) + h’(Tk);
Thêm Tk vào OPEN.
Thuật giải A* nè
A* là một phiên bản đặc biệt của AKT áp dụng cho trường hợp đồ thị. Thuật giải A* có sử dụng thêm tập hợp CLOSE để lưu trữ những trường hợp đã được xét đến. A* mở rộng AKT bằng cách bổ sung cách giải quyết trường hợp khi "mở" một nút mà nút này đã có sẵn trong OPEN hoặc CLOSE. Khi xét đến một trạng thái Ti bên cạnh việc lưu trữ 3 giá trị cơ bản g,h’, f’ để phản ánh độ tốt của trạng thái đó, A* còn lưu trữ thêm hai thông số sau :
1. Trạng thái cha của trạng thái Ti (ký hiệu là Cha(Ti) : cho biết trạng thái dẫn đến trạng thái Ti. Trong trường hợp có nhiều trạng thái dẫn đến Ti thì chọn Cha(Ti) sao cho chi phí đi từ trạng thái khởi đầu đến Ti là thấp nhất, nghĩa là :
g(Ti) = g(Tcha) + cost(Tcha, Ti) là thấp nhất.
2. Danh sách các trạng thái kế tiếp của Ti : danh sách này lưu trữ các trạng thái kế tiếp Tk của Ti sao cho chi phí đến Tk thông qua Ti từ trạng thái ban đầu là thấp nhất. Thực chất thì danh sách này có thể được tính ra từ thuộc tính Cha của các trạng thái được lưu trữ. Tuy nhiên, việc tính toán này có thể mất nhiều thời gian (khi tập OPEN, CLOSE được mở rộng) nên người ta thường lưu trữ ra một danh sách riêng. Trong thuật toán sau đây, chúng ta sẽ không đề cập đến việc lưu trữ danh sách này. Sau khi hiểu rõ thuật toán, bạn đọc có thể dễ dàng điều chỉnh lại thuật toán để lưu trữ thêm thuộc tính này.
1. Đặt OPEN chỉ chứa T0. Đặt g(T0) = 0, h’(T0) = 0 và f’(T0) = 0.
Đặt CLOSE là tập hợp rỗng.
2. Lặp lại các bước sau cho đến khi gặp điều kiện dừng.
2.a. Nếu OPEN rỗng : bài toán vô nghiệm, thoát.
2.b. Ngược lại, chọn Tmax trong OPEN sao cho f’(Tmax) là nhỏ nhất
2.b.1. Lấy Tmax ra khỏi OPEN và đưa Tmax vào CLOSE.
2.b.2. Nếu Tmax chính là TG thì thoát và thông báo lời giải là Tmax.
2.b.3. Nếu Tmax không phải là TG. Tạo ra danh sách tất cả các trạng thái kế tiếp của Tmax. Gọi một trạng thái này là Tk. Với mỗi Tk, làm các bước sau :
2.b.3.1. Tính g(Tk) = g(Tmax) + cost(Tmax, Tk).
2.b.3.2. Nếu tồn tại Tk’ trong OPEN trùng với Tk.
Nếu g(Tk) < g(Tk’) thì
Đặt g(Tk’) = g(Tk)
Tính lại f’(Tk’)
Đặt Cha(Tk’) = Tmax
2.b.3.3. Nếu tồn tại Tk’ trong CLOSE trùng với Tk.
Nếu g(Tk) < g(Tk’) thì
Đặt g(Tk’) = g(Tk)
Tính lại f’(Tk’)
Đặt Cha(Tk’) = Tmax
Lan truyền sự thay đổi giá trị g, f’ cho tất cả các trạng thái kế tiếp của Ti (ở tất cả các cấp) đã được lưu trữ trong CLOSE và OPEN.
2.b.3.4. Nếu Tk chưa xuất hiện trong cả OPEN lẫn CLOSE thì :
Thêm Tk vào OPEN
Tính : f' (Tk) = g(Tk)+h’(Tk).
Có một số điểm cần giải thích trong thuật giải này. Đầu tiên là việc sau khi đã tìm thấy trạng thái đích TG, làm sao để xây dựng lại được "con đường" từ T0 đến TG. Rất đơn giản, bạn chỉ cần lần ngược theo thuộc tính Cha của các trạng thái đã được lưu trữ trong CLOSE cho đến khi đạt đến T0. Đó chính là "con đường" tối ưu đi từ TG đến T0 (hay nói cách khác là từ T0 đến TG).
Điểm thứ hai là thao tác cập nhật lại g(Tk’) , f’(Tk’) và Cha(Tk’) trong bước 2.b.3.2 và 2.b.3.3. Các thao tác này thể hiện tư tưởng : "luôn chọn con đường tối ưu nhất". Như chúng ta đã biết, giá trị g(Tk’) nhằm lưu trữ chi phí tối ưu thực sự tính từ T0 đến Tk’. Do đó, nếu chúng ta phát hiện thấy một "con đường" khác tốt hơn thông qua Tk (có chi phí nhỏ hơn) con đường hiện tại được lưu trữ thì ta phải chọn "con đường" mới tốt hơn này. Trường hợp 2.b.3.3 phức tạp hơn. Vì từ Tk’ nằm trong tập CLOSE nên từ Tk’ ta đã lưu trữ các trạng thái con kế tiếp xuất phát từ Tk’. Nhưng g(Tk’) thay đổi dẫn đến giá trị g của các trạng thái con này cũng phải thay đổi theo. Và đến lượt các trạng thái con này lại có thể có các các trạng thái con tiếp theo của chúng và cứ thế cho đến khi mỗi nhánh kết thúc với một trạng thái trong OPEN (nghĩa là không có trạng thái con nào nữa). Để thực hiện quá trình cập nhật này, ta hãy thực hiện quá trình duyệt theo chiều sâu với điểm khởi đầu là Tk’. Duyệt đến đâu, ta cập nhật lại g của các trạng thái đến đó ( dùng công thức g(T) = g(Cha(T)) +cost(Cha(T), T) ) và vì thế giá trị f’ của các trạng thái này cũng thay đổi theo.
Một lần nữa, xin nhắc lại rằng, bạn có thể cho rằng tập OPEN lưu trữ các trạng thái "sẽ được xem xét đến sau" còn tập CLOSE lưu trữ các trạng thái "đã được xét đến rồi".
Chà chà, Best First Search có vẻ hay đấy chứ
(Bài viết này có đính kèm 1 file .rar trong đó có bài viết về Best First Search mà tôi tìm được. Nếu ai có hứng thú về Best First Search thì cùng vào đây trao đổi)