Tiểu luận Phương pháp tìm kiếm lời giải của bái toán

Phần I. Giới thiệu Nhiều bài toán phức tạp có thể được phát biểu dưới dạng sau: Cho trước hai trạng thái T0 và TG. Hãy xây dựng chuỗi trạng thái T0, T1, T2, ...Tn (TG) sao cho Scost(Ti-1,Ti) thỏa mãn điều kiện cho trước. Trong đó Ti thuộc tập hợp S gồm tất cả các trạng thái có thể có của bài toán và cost(Ti-1,Ti) là chi phí để biến đổi từ trạng thái Ti-1 đến Ti. Các bài toán thuộc dạng này đều có thể được biểu diễn dưới dạng đồ thị. Trong đó một trạng thái là một đỉnh của đồ thị. Tập hợp S gồm tất cả các trạng thái chính là tập hợp các đỉnh của đồ thị. Việc biến đổi từ trạng thái Ti-1 sang trạng thái Ti là việc đi từ đỉnh đại diện cho Ti-1 đến đỉnh đại diện cho Ti theo cung nối giữa hai đỉnh này. Đối với loại bài toán này, một phương pháp tìm kiếm lời giải phổ biến và dễ cài đặt nhất là phương pháp thử-sai quay lui. Để giảm bớt không gian thử sai, có nhiều kỹ thuật như: đơn giản điều kiện, loại bỏ những hướng đi chắc chắn không dẫn đến lời giải, nhánh cận... Tuy nhiên đối với những bài toán có không gian tìm kiếm rất lớn, dù cố gắng tinh chỉnh đến bao nhiêu đi nữa các phương pháp này cũng không đạt được hiệu quả mong muốn. Để tìm kiếm được lời giải nhanh hơn, người ta đưa ra một phương pháp với ý tưởng là “chọn đi theo hướng có nhiều khả năng dẫn đến lời giải’. Đây chính là ý tưởng của thuật giải Heuristic. Số lượng hướng đi mà chắc chắn không dẫn đến lời giải luôn ít hơn những hướng đi có thể dẫn đến lời giải. Nếu như đánh giá được khả năng dẫn đến lời giải của một hướng đi thì ta có thể xây dựng được một thứ tự ưu tiên để duyệt các hướng đi. Khi duyệt các hướng đi theo thứ tự ưu tiên giảm dần ta sẽ có cơ hội tiếp cận đến lời giải nhanh hơn là duyệt một cách mù quáng. Thực ra các phương pháp tìm kiếm lời giải của một bài toán đã được trình bày rất cụ thể và chính xác ở nhiều tài liệu. Thuật giải Heuristic cũng đã được áp dụng rộng rãi trong nhiều ứng dụng. Tiểu luận không nhằm cải tiến các phương pháp tìm kiếm này mà chỉ tóm tắt những tri thức mà bản thân đã thu nhận được qua thời gian học tập và tham khảo tài liệu. Đồng thời vận dụng những tri thức đó để giải quyết một bài toán ứng dụng cụ thể, đó là lập trình trò chơi Caro. Tiểu luận gồm 3 phần. Phần 1: Trình bày những phương pháp tìm kiếm lời giải của bái toán. Trong đó nhấn mạnh phương pháp tìm kiếm ưu tiên tốt nhất BFS và thuật giải A* cũng như các chiến lược phối hợp giữa các phương pháp. Phần 2: Giới thiệu hai thuật toán trong đó có áp dụng heuristic vào lập trình trò chơi. Phần 3: Lấy một ví dụ lập trình trò chơi Caro để minh họa cho hai phần đã được trình bày. Phần II. Nội dung A-Một số phương pháp tìm kiếm lời giải I/ Tìm kiếm theo chiều sâu và tìm kiếm theo chiều rộng Để đưa ra được ý tưởng của thuật giải heuristic, trước hết xin trình bày hai phương pháp tìm kiếm lời giải cơ bản là tìm kiếm theo chiều rộng và tìm kiếm theo chiều sâu. 1.1/ Tìm kiếm theo chiều sâu. Tìm kiếm theo chiều sâu chính là thử-sai quay lui. Nghĩa là ở trạng thái hiện tại, ta chọn một trạng thái kế tiếp làm trạng thái hiện tại cho đến khi trạng thái hiện tại là trạng thái đích. Nếu ở trạng thái hiện tại ta không thể biến đổi thành trạng thái kế tiếp thì ta sẽ quay lui lại trạng thái trước trạng thái hiện tại để chọn đường khác. Nếu ở trạng thái trước này mà cũng không thể biến đổi được nữa thì ta quay lui lại trạng trái kế trước nữa và cứ như thế. Nếu đã quay lui đến trạng thái khởi đầu mà vẫn thất bại thì kết luận là không có lời giải. 1.2/ Tìm kiếm theo chiều rộng Tìm kiếm chiều rộng mang hình ảnh của vết dầu loang. Từ trạng thái ban đầu, ta xây dựng tập S bao gồm các trạng thái kế tiếp của S. Sau đó ứng với mỗi trạng thái Tk, trong tập S ta xây dựng tập Sk bao gồm các trạng thái kế tiếp của Tk, rồi ghép Sk vào S. Quá trình này cứ lặp lại cho đến lúc S có chứa trạng thái kết thúc hoặc S không thay đổi sau khi đã bổ sung tất cả Sk. 1.3/ Đánh giá Tìm kiếm theo chiều sâu và tìm kiếm theo chiều rộng đều là các phương pháp tìm kiếm mà chắc chắn tìm ra lời giải. Tuy nhiên, do bản chất là vét cạn nên với những bài toán có không gian lớn thì ta không thể dùng hai phương pháp này được. Hơn nữa, hai phương pháp này đều có tính chất “mù quáng” vì chúng không chú ý đến những thông tin ở trạng thái hiện thời và thông tin về đích cần đạt tới và mối quan hệ giữa chúng. Các thông tin này rất quan trọng và rất có ý nghĩa để thiết kế các thuật giải có hiệu quả hơn. II/ Tìm kiếm leo núi 2.1/ Leo núi đơn giản. Tìm kiếm leo núi thực chất chỉ là một trường hợp đặc biệt của tìm kiếm theo chiều sâu nhưng không thể quay lui. Trong tìm kiếm leo núi, việc lựa chọn trạng thái tiếp theo được quyết định dựa trên một hàm Heuristic. Hàm Heuristic là một ước lượng về khả năng dẫn đến lời giải của một trạng thái (còn gọi là chí phí ước lượng từ trạng thái hiện tại đến trạng thái đích). Ta quy ước gọi hàm này là h’, hàm h’ quy ước luôn có giá trị không âm. Gọi h là chi phí tối ưu thực sự từ một trạng thái dẫn đến lời giải. Thông thường không thể tính được h mà chỉ dùng nó như một cơ sở để suy luận về mặt lý thuyết. ý tưởng của thuật giải leo núi đơn giản. 1-Nếu trạng thái ban đầu là trạng thái đích thì thoát và thông báo đã tìm được lời giải. Ngược lại, đặt trạng thái hiện tại (Ti) là trạng thái khởi đầu (T0) 2-Lặp lại cho đến khi đạt đến trạng thái kết thúc hoặc cho đến khi không tồn tại một trạng thái tiếp theo hợp lệ (Tk) của trạng thái hiện tại a-Đặt Tk là một trạng thái tiếp theo hợp lệ của trạng thái hiện tại Ti b-Đánh giá trạng thái Tk mới. i-Nếu là trạng thái kết thúc thì trả về trị này và thoát ii-Nếu không phải là trạng thái kết thúc nhưng tốt hơn trạng thái hiện tại thì cập nhật nó thành trạng thái hiện tại. iii-Nếu nó không tốt hơn trạng thái hiện tại thì tiếp tục vòng lặp. Vì việc lập trình để diễn đạt một cách đầy đủ ý tưởng của giải thuật này là khá phức tạp nên trong tiểu luận chỉ xin biểu diễn bằng ngôn ngữ tựa Pascal. Procedure LNDG; Begin Ti:=T0; Stop:=False; While Stop=False do Begin If Ti=TG then Begin Thông báo kết quả; Stop:=True; End Else Begin Beter:=False; While (Beter=False) And (Stop=False) do Begin If then Begin Thông báo không tìm được kết quả; Stop:=True End Else Begin Tk:= If then Begin Ti:=Tk; Beter:=True; End; End; End; End; End; End; 2.2/ Leo núi dốc đứng Về cơ bản, leo núi dốc đứng cũng giống như leo núi đơn giản. Tuy nhiên, leo núi dốc đứng sẽ duyệt tất cả các hướng đi có thể và chọn đi theo trạng thái tốt nhất trong số các trạng thái kế tiếp có thể có. Trong khi đó, leo núi đơn giản chỉ chọn đi theo trạng thái kế tiếp đầu tiên tốt hơn trạng thái hiện tại mà nó tìm thấy. ý tưởng của thuật toán leo núi dốc đứng. 1-Nếu trạng thái ban đầu là trạng thái đích thì thoát và thông báo đã tìm được lời giải. Ngược lại, đặt trạng thái hiện tại (T0) là trạng thái khởi đầu (T0) 2-Lặp lại cho đến khi đạt đến trạng thái kết thúc hoặc đến khi Ti không tồn tại một trạng thái kế tiếp (Tk) nào tốt hơn trạng thái hiện tại Ti a-Đặt S là tập tất cả trạng thái kế tiếp có thể có của Ti và tốt hơn Ti b-Xác định Tkmax là trạng thái tốt nhất trong tập S c-Đặt Ti= Tkmax Đoạn mã tựa Pascal diễn đạt ý tưởng thuật giải: Procedure LNDD; Begin Ti:=T0; Stop:=False; While Stop=False do Begin If Ti=TG then Begin Thông báo kết quả; Stop:=True; End Else Begin Best:=h’(Ti); Tmax:= Ti; While do Begin Tk:=; If then Begin Best:=h’(Tk); Tmax:= Tk; End; End; If (Best>Ti) then Ti:=Tmax Else Begin Thông báo không tìm được kết quả; Stop:=True; End; End; End; End; 2.3/ Đánh giá hai thuật giải leo núi So với leo núi đơn giản, leo núi dốc đứng có ưu điểm là luôn luôn chọn hướng có triển vọng nhất để đi. Tuy nhiên, điều này chưa chắc nó tốt hơn leo núi đơn giản. Để chọn được hướng đi tốt nhất, leo núi dốc đứng phải duyệt qua tất cả các hướng đi có thể có tại trạng thái hiện tại. Trong khi đó, leo núi đơn giản chỉ chọn đi theo hướng tốt hơn đầu tiên mà nó tìm ra được. Do đó thời gian cần thiết để leo núi dốc đứng chọn được một hướng đi sẽ lớn hơn so với leo núi đơn giản. Tuy vậy, do lúc nào cũng chọn hướng đi tốt nhất nên leo núi dốc đứng thường tìm đến lời giải sau một số bước ít hơn so với leo núi đơn giản. Tóm lại, leo núi dốc đứng sẽ tốn nhiều thời gian hơn cho mỗi bước nhưng lại đi ít hơn, còn leo núi đơn giản tốn ít thời gian hơn cho mỗi bước nhưng lại phải đi nhiều bước hơn. Đây chính là ưu điểm và khuyết điểm của hai thuật giải nên ta phải cân nhắc kỹ lưỡng khi lựa chọn thuật giải. Cả hai phương pháp leo núi dốc đứng và leo núi đơn giản đều có thể thất bại trong việc tìm lời giải của bài toán mặc dù lời giải đó thực sự tồn tại. Cả hai giải thuật đều có thể kết thúc khi đạt được một trạng thái mà không còn trạng thái nào tốt hơn nữa để phát sinh nhưng trạng thái này không phải là trạng thái đích. Điều này sẽ xảy ra nếu chương trình đạt đến một điểm cực trị địa phương, một đoạn đơn điệu ngang. Có hai biện pháp cơ bản để khắc phục vấn đề này. Phương án thứ nhất là kết hợp leo núi với quay lui. Ta sẽ quay lui tại các trạng thái trước đó và thử đi theo hướng khác. Thao tác này hợp lý nếu tại các trạng thái trước đó nếu có một hướng đi tốt mà ta đã bỏ qua từ trước. Đây là một cách khá hay để đối phó với các điểm cực trị địa phương. Tuy nhiên, do đặc điểm của leo núi là “bước sau cao hơn bước trước” nên phương án này sẽ thất bại khi ta xuất phát từ một điểm quá cao hoặc từ một đỉnh núi mà để đến được lời giải cần phải đi qua một “thung lũng” rất sâu như trong hình sau Vị trí và hướng đi hiện tại Không thể quay lui xuống thấp hơn ngưỡng này được Lời giải Vị trí xuất phát Một trường hợp thất bại của leo núi kết hợp với quay lui Cách thứ hai là thực hiện một bước nhảy vọt theo hướng nào đó để thử đến một vùng mới của không gian tìm kiếm. Tiếp cận này hiệu quả khi ta gặp phải một đoạn đơn điệu ngang. Tuy nhiên nhảy vọt cũng có nghĩa là bỏ qua cơ hội để tiến đến lời giải thực sự. Trong trường hợp chúng ta đang đứng khá gần với lời giải, việc nhảy vọt sẽ chuyển sang một vị trí hoàn toàn xa lạ. Hơn nữa, số bước nhảy là bao nhiêu và nhảy theo hướng nào là một vấn đề phụ thuộc nhiều vào đặc điểm không gian tìm kiếm của bài toán Lời giải Đọan đơn điệu ngang Vị trí hiện tại Vị trí sau khi nhảy Một trường hợp thất bại cho phương án “nhảy vọt” Leo núi là một phương pháp mà việc quyết định sẽ làm gì tiếp theo dựa vào một đánh giá về trạng thái hiện tại và các trạng thái kế tiếp có thể có mà không xem xét một cách toàn diện trên tất cả các trạng thái đã đi qua. Thuận lợi của leo núi là ít gặp sự bùng nổ tổ hợp. Nhưng lại không không chắc chắn tìm ra lời giải. III/ Tìm kiếm ưu tiên tốt nhất (BFS) và thuật giải A* Nguyên lý chung: Chọn hướng đi triển vọng nhất trong số những hướng đi đã biết. 3.1/ Tìm kiếm ưu tiên tốt nhất (BFS: Best-First Search) Ư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 theo chiều rộng là không bị sa vào các đường dẫn bế tắc. Tìm kiếm BFS kết hợp cả hai 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 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. 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 đó. Với tiếp cận này, ta sẽ đi sâu vào những nhánh tìm kiếm có khả năng nhất nhưng không bị luẩ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 xấu thì 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ưởng chủ đạo của tìm kiếm BFS. Để minh họa ý tưởng này ta có ví dụ sau: Bước 1 A B 3 C 1 D 5 Bước 2 A B 3 C 1 D 5 E 4 F 6 Các con số dưới nút là giá trị hàm Heuristic ứng với nút đó. Nút có giá trị càng nhỏ thì càng gần với nút đích. Khởi đầu, chỉ có một nút A nên nó sẽ được mở rộng tạo ra ba nút mới B, C và D. Do C là nút có khả năng nhất nên nó sẽ được mở rộng và sinh ra hai nút kế tiếp là E và F. Đến đây, ta lại thấy nút B có khả năng nhất, nên ta chọn mở rộng nút B và tạo được hai nút G và H. Bước 4 A B 3 C 1 D5 E 4 F 6 G 6 H 5 Bước 3 A B 3 C 1 D5 E 4 F 6 G 6 H 5 J 1 I 2 Minh họa thuật giải BFS Ta lại thấy nút E có khả năng nhất, vì thế nút E được mở rộng sinh ra nút I và J. ở bước tiếp theo, J sẽ được mở rộng vì nó có khả năng nhất. Quá trình này tiếp tục cho đến khi tìm thấy một lời giải. Thuật giải tìm kiếm BFS có hai đặc điểm khác với thuật giải tìm kiếm leo núi dốc đứng. Thứ nhất, trong thuật giải tìm kiếm leo núi, một trạng thái được chọn và tất cả các trạng thái khác bị loại bỏ, không bao giờ chúng được xem xét lại. Trong thuật giải tìm kiếm BFS, tại mỗi bước cũng có một trạng thái được chọn nhưng những trạng thái khác vẫn được giữ lại, để ta có thể trở lại xét sau đó khi mà trạng thái hiện tại trở nên kém khả năng hơn những trạng thái đã được lưu trữ. Thứ hai, trong thuật giải BFS, ta chọn trạng thái tốt nhất mà không quan tâm đến nó có tốt hơn các trạng thái trước đó hay không. Trong khi đó leo núi sẽ dừng nếu không có trạng thái tiếp theo nào tốt hơn trạng thái hiện tại. Để cài đặt tìm kiếm BFS, ta dùng hai tập hợp MO và DONG. MO là tập chứa các trạng thái đã được sinh ra nhưng chưa được xét đến. MO được tổ chức như một hàng đợi ưu tiên mà trong đó phần tử có độ ưu tiên cao nhất là phần tử tốt nhất. DONG là 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ỗi trạng thái mới được tạo ra lại trùng với trạng thái đã xét đến trước đó. Trong BFS, độ tốt của mỗi trạng thái là tổng của hai giá trị g và h’. Trong đó h’ là ước lượng chi phí từ trạng thái hiện tại cho dến trạng thái đích. Còn g là chi phí thực sự từ trạng thái ban đầu đến trạng thái hiện tại. Hình dưới đây minh họa cho điều này. 4 3 T0 T1 T3 T2 g(Ti)=4+3=7 g là chi phí thực sự để đi từ trạng thái khởi đầu đến trạng thái hiện tại TG h’(Ti)=5 h’ là ước lượng chi phí để đi từ trạng thái hiện tại đến đích TG là trạng thái đích Đặt f’=g+h’ để thể hiện một ước lượng về “tổng chi phí” cho con đường từ trạng thái ban đầu cho đến trạng thái kết thúc dọc theo con đường đi qua trạng thái hiện tại. Nếu có nhiều hơn một con đường đi qua trạng thái hiện tại thì giải thuật chỉ ghi nhận con đường tốt nhất. Để thuận tiện, ta quy ước là g và h’ là không âm và càng nhỏ nghĩa là càng tối ưu. Thuật giải BFS-Best First Search 1-Đặt MO 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 MO, thực hiện a/ Chọn trạng thái tốt nhất (Tmax) trong MO b/ Nếu Tmax là trạng thái kết thúc thì thoát. c/ Ngược lại tạo ra các trạng thái kế tiếp có thể có từ trạng thái Tmax d/ Đối với mỗi trạng thái kế tiếp Tk thực hiện i/ Nếu Tk chưa có trong MO thì tiến hành đánh giá Tk, thêm Tk vào MO và ghi nhận Tmax là trạng thái cha của nó. ii/ Nếu Tk đã có trong MO, thì cập nhật lại trạng thái cha của Tk là Tmax nếu đường dẫn qua Tmax đến Tk tốt hơn đường dẫn hiện đang lưu trữ trong Tk. Sau đó, cập nhật lại giá trị ước lượng g của tất cả các trạng thái con xuất phát từ Tk. Thực tế, hiếm có một bài toán nào có thể giải thuần túy bằng BFS. Ta thường vận dụng một phiên bản đặc biệt của BFS là thuật giải A*. 3.2/ Thuật giải A* Thuật giải A* cũng sử dụng tập MO và DONG. Khi xét đến trạng thái Ti, bên cạnh lưu trữ ba giá trị g, h’, f’ để phản ánh độ tốt của trạng thái đó, ta còn phải lưu ý lưu trữ thêm hai thông số sau: -Trạng thái cha của trạng thái Ti (cha(Ti)): đó là 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. -Danh sách các trạng thái kế tiếp của Ti: 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 ra danh sách này có thể được tính được từ Cha của các trạng thái được lưu trữ. Tuy nhiên, việc tính này có thể mất nhiều thời gian nên người ta thường lưu trữ ra một danh sách riêng. 1/ Đặt MO chỉ chứa T0. Đặt g(T0)=0, tính h’(T0) và f’(T0)=h’(T0). Đặt DONG là tập rỗng. 2/ Lặp lại các bước sau cho đến khi gặp điều kiện dừng. a/ Nếu MO là rỗng: bài toán vô nghiệm, thoát. b/ Ngược lại, chọn Tmax trong MO sao cho f’(Tmax) là nhỏ nhất. i/ Lấy Tmax ra khỏi MO và đưa vào DONG ii/ Nếu Tmax chính là TG thì thoát và thông báo lời giải là Tmax iii/ Nếu Tmax không phải là TG thì tạo 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: 1/ Tính g(Tk)=g(Tmax) + cost(Tmax,Tk) 2/ Nếu tồn tại Tk’ trong MO 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 3/ Nếu tồn tại Tk’ trong DONG 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ữ. 4/ Nếu Tk chưa xuất hiện trong tất cả MO lẫn DONG thì Thêm Tk vào MO Tính f’(Tk)=g(Tk)+h’(Tk). Sau khi tìm được trạng thái đích TG, để tìm con đường từ T0 đến TG 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ữ cho đến khi đạt đến T0. Đó chính là đường đi tối ưu từ T0 đến TG Các thao tác cập nhật g(Tk’), f’(Tk’) và Cha(Tk’) trong bước 2/b/iii/2 và 2/b/iii/3 thể hiện tư tưởng luôn chọn đường đi tối ưu nhấ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 đường đi khác thông qua Tk mà tốt hơn con đường hiện tại được lưu trữ thì ta chọn con đường mới này. Trường hợp 2/b/iii/3 phức tạp hơn. Vì từ Tk’ nằm trong tập DONG 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 trạng thái con tiếp theo của chúng và cứ như vậy cho đến khi mỗi nhánh kết thúc với một trạng thái trong MO, 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 thực hiện quá trình duyệt theo kiểu quay lui 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. Ta sẽ dừng việc duyệt đến khi trạng thái hiện tại nằm trong MO hoặc đến một trạng thái T mà giá trị g(T) hiện tại của nó tốt hơn hoặc bằng g(Cha(T))+cost(cha(T),T). 3.3/ Đánh giá thuật giải A* Thứ nhất, g cho biết độ tốt của con đường từ trạng thái khởi đầu đến trạng thái hiện tại. Vì vậy nó giúp ta lựa chọn trạng thái nào để mở rộng tiếp theo mà không chỉ dựa trên trạng thái đó tốt như thế nào. Điều này cũng rất hữu ích nếu ta không chỉ quan tâm việc tìm ra lời giải mà còn quan tâm đến con đường dẫn đến lời giải. Tuy nhiên, nếu chỉ quan tâm đến việc tìm được lời giải mà không quan tâm đến con đường đến lời giải, có thể đặt g=0 ở mọi trạng thái. Điều này sẽ giúp ta luôn chọn đi theo trạng thái có vẻ gần nhất với trạng thái kết thúc, vì lúc này f’ chỉ phụ thuộc vào h’ là hàm ước lượng chi phí ít nhất để tới đích. Khi đó thuật giải có dáng dấp của tìm kiếm chiều sâu theo nguyên lý hướng đích kết hợp với lần ngược. Nếu muốn tìm ra kết quả với số bước đi ít nhất, thì ta đặt giá trị để đi từ trạng thái đến trạng thái con kế tiếp của nó luôn là 1 và vẫn dùng hàm ước lượng h’. Còn ngược lại, nếu muốn tìm chi phí ít nhất thì ta phải đặt giá trị hàm cost phản ánh đúng chi phí thực sự. Ta thấy rằng thuật giải A* không hoàn toàn là một giải thuật tối ưu tuyệt đối mà chỉ là thuật giải linh động và cho khá nhiều phương án để lựa chọn. Tùy theo bài toán mà ta có một bộ thông số thích hợp cho A* để thuật giải hoạt động hiệu quả nhất. Thứ hai là giá trị h’ là ước lượng chi phí từ một trạng thái đến đạng thái đích. Nếu h’ chính là h thì A* sẽ đi một mạch từ trạng thái đầu đến trạng thái kết thúc mà không cần phải thực hiện bất kỳ một thao tác đổi hướng nào. Thực tế, không thể có một đánh giá tuyệt đối chính xác. Điều đáng quan tâm ở đây là h’ được ước lượng sao cho càng gần với h càng tốt. Khi đó quá trình tìm kiếm càng nhanh chóng tìm thấy lời giải. Nếu h’ luôn bằng 0 ở mọi trạng thái thì quá trình tìm kiếm sẽ được điều khiển hoàn toàn bởi giá trị g. Nghĩa là thuật giải sẽ chọn đi theo những hướng mà sẽ tốn ít chi phí (hoặc ít bước đi nhất) tính từ trạng thái đầu tiên đến trạng thái hiện đang xét, bất chấp việc đi theo hướng đó có khả năng dẫn đến lời giải hay không. Đây chính phương pháp duyệt tham lam. Nếu chi phí từ trạng thái này sang trạng thái khác luôn là hằng số (h’ luôn bằng 0) thì thuật giải A* trở thành tìm kiếm theo chiều rộng. Vì tất cả những trạng thái cách trạng thái khởi đầu n bước đều có cùng giá trị g và do đó đều có cùng f’ và giá trị này sẽ nhỏ hơn tất cả các trạng thái cách trạng thái khởi đầu n+1 bước. Và nếu g luôn bằng 0 và h’ cũng luôn bằng 0, mọi trạng thái đang xét đều tương đương nhau. ta chỉ có thể chọn giá trị kế tiếp một cách ngẫu nhiên. Còn nếu như h’ không đúng bằng h và cũng không luôn bằng 0. Nếu như bằng một cách nào đó, ta có thể chắc chắn rằng h’ luôn nhỏ hơn h đối với mọi trạng thái thì ta nói h’ đánh giá thấp h, khi đó thuật giải A* sẽ luôn tìm ra con đường tối ưu để đi đến đích, nếu đường dẫn đó tồn tại. Còn nếu h’ cao hơn h thì thuật giải sẽ bị rơi vào những hướng tìm kiếm vô ích. Vậy ta có thể nói A* là một thuật giải linh động và tổng quát trong đó bao hàm cả tìm kiếm chiều sâu, cả tìm kiếm theo chiều rộng và những nguyên lý Heuristic khác. Vì thế người ta thường nói, A* chính là thuật giải tiêu biểu cho Heuristic. Bên cạnh những ưu điểm, A* vẫn tồn tại một số khuyết điểm cơ bản đó là tốn khá nhiều bộ nhớ để lưu lại trạng thái đã đi qua-nếu chúng ta muốn nó chắc chắn tìm thấy lời giải tối ưu. Với những bài toán có không gian tìm kiếm nhỏ thì đây không phải là một điểm đáng quan tâm. Tuy nhiên, với những bài toán có không gian tìm kiếm khá lớn thì không gian lưu trữ là một vấn đề phức tạp. IV/ Các chiến lược phối hợp Chúng ta đã biết ba phương pháp tìm kiếm: Tìm kiếm leo núi, tìm kiếm kiểu thử-sai quay lui và tìm kiếm BFS. Nếu xét về khả năng quay lui thì leo núi là không thể có, trong khi đó tìm kiếm quay lui và BFS cho phép quay lại tất cả những hướng đi chưa xét đến. Nếu xét về số lượng trạng thái trong mỗi quyết định thì tìm kiếm leo núi và quay lui chỉ chỉ tập trung vào một phạm vi hẹp trên tập các trạng thái mới tạo ra từ trạng thái hiện tại, trong khi đó BFS xem xét toàn bộ tập các con đường đã có, bao gồm cả những con đường mới được tạo ra cũng như tất cả những con đường không được xét tới trước đây trước mỗi quyết định. Nếu không đủ bộ nhớ để áp dụng thuật toán BFS, ta có thể kết hợp BFS với tìm kiếm quay lui khi đó số lượng các trạng thái được xét đến tại mỗi bước sẽ nhỏ đi. Một cách phối hợp là áp dụng thuật giải tìm kiếm BFS tại đỉnh của không gian tìm kiếm và tìm kiếm quay lui được áp dụng tại đáy. Đầu tiên ta áp dụng BFS vào trạng thái khởi đầu T0. BFS sẽ thực hiện cho đến khi số lượng trạng thái được lưu trữ trong MO chiếm dụng một không gian bộ nhớ vượt quá M0. Sau đó, ta áp dụng tìm kiếm quay lui xuất phát từ trạng thái tốt nhất Tmax trong MO cho đến khi toàn bộ không gian con phía dưới trạng thái đó được duyệt hết. Nếu không tìm thấy kết quả, trạng thái Tmax này được ghi nhận là không dẫn đến kết quả và ta lại chọn ra trạng thái tốt thứ hai trong MO và lại áp dụng tìm kiếm quay lui cho phần không gian phía dưới trạng thái này... Một cách phối hợp khác là tìm kiếm quay lui tại đỉnh không gian tìm kiếm và áp dụng tìm kiếm BFS tại đáy. Ta áp dụng tìm kiếm quay lui cho tới khi gặp một trạng thái Tk mà số trạng thái trung gian của nó vượt quá một ngưỡng d0 nào đó. Tại điểm này, thay vì lần ngược trở lại, ta áp dụng tìm kiếm BFS cho phần không gian phía dưới bắt đầu từ Tk cho tới khi nó trả về một kết quả hoặc không tìm thấy. Nếu nó không tìm thấy kết quả, chúng ta lần ngược trở lại và lại dùng BFS khi đạt độ sâu d0. Thực tế, rất khó xác định được d0 vì rất khó đánh giá được không gian bài toán. Kiểu kết hợp này có một ưu điểm đó là càng tiến về đáy của không gian tìm kiếm ước lượng h’ càng trở nên chính xác hơn và dó đó càng dễ dẫn đến kết quả hơn. Một kiểu phối hợp phức tạp hơn nữa. Trong đó, tìm kiếm BFS được thực hiện cục bộ và tìm kiếm quay lui được thực hiện toàn cục. Ta bắt đầu tìm kiếm BFS cho tới khi một lượng M0 bộ nhớ được dùng. Tại điểm này, ta xem tất cả các trạng thái trong MO như những trạng thái con trực tiếp của trạng thái ban đầu và chuyển chúng cho tìm kiếm quay lui. Tìm kiếm quay lui sẽ chọn trạng thái tốt nhất trong những trạng thái con này và chuyển trạng thái đã chọn cho tìm kiếm BFS cục bộ cho đến khi một lượng bộ nhớ M0 lại được dùng hết và trạng thái con mới trong MO lại tiếp tục được xem như nút con của nút mở rộng... Nếu việc mở rộng bằng BFS thất bại thì quay lui lại và chọn nút con tốt thứ hai của tập MO trước đó, rồi lại tiếp tục mở rộng bằng BFS... Một cách phối hợp tìm kiếm khác được gọi là tìm kiếm theo giai đoạn. Ta không lưu trữ trong bộ nhớ toàn bộ cây tìm kiếm được sinh ra bởi BFS mà chỉ giữ lại cây có triển vọng nhất. Khi một lượng bộ nhớ M0 được dùng hết, ta sẽ đánh dấu một tập con các trạng thái tốt ở trong MO để giữ lại. Những đường đi tốt nhất qua những trạng thái này cũng sẽ được lưu lại và tất cả các phần còn lại của cây bị loại bỏ. Quá trình tìm kiếm sau đó sẽ tiếp tục theo BFS cho tới khi một lượng bộ nhớ M0 lại được dùng hết và cứ thế. Chiến lược này có thể được xem như là một sự lai ghép giữa BFS và leo núi. Trong đó leo núi loại bỏ tất cả các phương án và chỉ giữ lại phương án tốt nhất còn tìm kiếm theo giai đoạn loại bỏ tất cả các phương án và giữ lại tập các phương án tốt nhất. B-Sử dụng heuristic trong trò chơi I/ Thuật toán Minimax. Đối với các trò chơi có không gian trạng thái có thể mô tả được đến cùng, chỉ có một khó khăn là phải tính toán các phản ứng của các đối thủ. Một cách xử lý là giả sử đối thủ cũng sử dụng những kiến thức về không gian trạng thái giống như ta, và áp dụng kiến thức đó một cách kiên định để thắng cuộc. Minimax sẽ tìm kiếm không gian trò chơi này theo giả thiết đó. Hai đối thủ trong một trò chơi được gọi là MIN và MAX. MAX đại diện cho đối thủ quyết dành thắng lợi bằng cách tối đa hóa ưu thế của mình. MIN là đối thủ cố tối thiểu hóa điểm số của MAX. Giả thiết MIN cũng dùng cùng những thông tin như MAX và luôn luôn di chuyển vào trạng thái xấu nhất đối với MAX. Để thực hiện minimax, ta đánh dấu từng mức trong không gian tìm kiếm phù hợp với từng người, MIN hoặc MAX có nước đi ở đó. Giả sử MIN được quyền đi trước. Mỗi nút được gán giá trị 1 ứng với MAX thắng cuộc và được gán giá trị 0 ứng với MIN thắng cuộc. Sau đó, minimax sẽ lan truyền ngược các giá trị này lên cao dần trên đồ thị, qua hết các nút mẹ kế tiếp nhau theo luật sau: +Nếu trạng thái mẹ là nút MAX, gán cho nó giá trị lớn nhất của tất cả các nút con cháu của nó. +Nếu trạng thái mẹ là nút MIN, gán cho nó giá trị nhỏ nhất của tất cả các nút con cháu của nó. Đối với các trò chơi phức tạp, ít khi có khả năng mở rộng đồ thị không gian trạng thái đến các nút lá. Thay vào đó, không gian trạng thái này được tìm kiếm đến một mức được xác định trước. Chiến lược này được gọi là tính trước n nước đi, trong đo n là số mức được phát hiện. Vì những nút cuối cùng của đồ thị con này không phải là các trạng thái kết thúc của trò chơi, nên không thể gán cho chúng các giá trị phản ánh thắng cuộc hay thua cuộc. Thay vào đó mỗi nút được gán một giá trị phù hợp với một hàm đánh giá heuristic. Giá trị này được truyền ngược về nút gốc không cho biết được một thắng cuộc hay không mà chỉ là giá trị ước lượng tốt nhất của trạng thái sau n nước đi kể từ nút xuất phát. Các đồ thị trò chơi được tìm kiếm bằng mức. MAX và MIN luân phiên nhau chọn các nước đi. Mỗi nước đi của đối thủ sẽ xác định một lớp mới trên đồ thị. Nói chung, các chương trình trò chơi đều dự tính trước một độ sâu lớp cố định, thường được xác định bằng các giới hạn về không gian hoặc thời gian của máy tính. Các trạng thái trên lớp được đánh giá theo heuristic và được truyền ngược lên bằng minimax. Sau đó, thuật toán tìm kiếm sẽ dùng các giá trị vừa nhận được để chọn lựa một nước trong số các nước đi kế tiếp. Sau khi đã gán giá trị cho từng trạng thái trong lớp được chọn, chương trình sẽ lan truyền giá trị ngược lên cho từng trạng thái mẹ. Nếu trạng thái mẹ nằm trong mức MIN, minimax sẽ gán giá trị nhỏ nhất của các trạng thái con. Nếu mẹ là một nút MAX, thuật toán sẽ gán cho nó giá trị lớn nhất của các con. Bằng cách tối đa hóa cho các cha mẹ MAX và tối thiểu hóa cho MIN, các giá trị này đi lùi theo đồ thị đến con của trạng thái hiện tại. Các giá trị này sẽ được trạng thái hiện tại dùng để tiến hành chọn lựa trong các con của nó 3 MAX 3 1 2 MIN 3 9 1 7 2 6 MAX MIN 2 3 5 9 0 1 7 4 2 1 5 6 Thực hiện Minimax đối với một không gian trạng thái giả định II/ Thuật toán alpha-beta Thuật toán minimax trực tiếp yêu cầu phải có sự phân tích hai bước đối với không gian tìm kiếm. Bước đầu tiên để truyền xuống đến độ sâu của lớp áp dụng heuristic và bước thứ hai để suy biến ngược các giá trị trên cây. Muốn vậy, minimax phải đi theo tất cả các nhánh trong không gian tìm kiếm. Để nâng cao hiệu quả tìm kiếm trong các trò chơi hai người, một kỹ thuật cải tiến được gọi là phương pháp alpha-beta. ý tưởng của phương pháp này rất đơn giản: thay vì tìm kiếm toàn bộ không gian đến độ sâu của lớp dự tính trước, tìm kiếm alpha-beta thực hiện theo kiểu tìm kiếm sâu. Có hai giá trị, gọi là alpha và beta, được tạo ra trong quá trình tìm kiếm. Giá trị alpha liên quan với các nút MAX và không bao giờ giảm, giá trị beta liên quan với nút MIN và không bao giờ tăng. Giả sử có giá trị alpha của nút MAX là 6. Do đó MAX không cần xem xét bất kỳ giá trị suy biến ngược nào bé hơn hoặc bằng 6 có liên quan với một nút MIN ở bên dưới. Alpha là giá trị tồi nhất mà MAX có thể nhận được sau khi cho rằng MIN cũng sẽ nhận giá trị tốt nhất của nó. Tương tự, nếu MIN có giá trị beta là 6, thì nó không cần xem xét các nút nằm dưới nó có giá trị lớn hơn hoặc bằng 6. Để bắt đầu tìm kiếm, alpha-beta đi xuống hết độ sâu lớp theo kiểu tìm kiếm sâu, đồng thời áp dụng sự đánh giá heuristic cho một trạng thái và tất cả anh em của nó. Giả thiết, tất cả là các nút MIN. Giá trị tối đa của các nút MIN này sẽ suy ngược lên cho nút mẹ. Sau đó, giá trị này được gán cho ông bà của các nút MIN như một giá trị beta cuối cùng. Tiếp theo, thuật toán này sẽ đi xuống các cháu khác và kết thúc việc khám phá đối với mẹ của chúng nếu gặp bất kỳ một giá trị nào lớn hơn hoặc bằng giá trị beta này. Tương tự cho việc tỉa bớt alpha đối với các cháu của một nút MAX. Hai luật kết thúc tìm kiếm dựa trên các giá trị alpha và beta là: +Cuộc tìm kiếm có thể kết thúc bên dưới một nút MIN nào có giá trị beta bé hơn hoặc bằng giá trị alpha của một nút cha MAX bất kỳ nào đó của nó. + Cuộc tìm kiếm có thể kết thúc bên dưới một nút MAX nào có giá trị alpha lớn hơn hoặc bằng giá trị beta của một nút cha MIN bất kỳ nào đó của nó. 3 MAX 3 1 2 MIN 3 9 1 7 2 6 MAX MIN 2 3 5 9 0 1 7 4 2 1 5 6 Phương pháp rút gọn Alpha-beta áp dụng cho không gian trạng thái giả định. Các trạng thái bị cắt sẽ không được đánh giá Việc tỉa bớt Alpha-beta như vậy biểu hiện một quan hệ giữa các nút ở lớp n và các nút ở lớp n+1, và do đó toàn bộ các cây con bắt nguồn ở mức n+1 đều có thể loại khỏi việc xem xét. C- Lập trình minh họa. I/ Một số định nghĩa. 1.1/ Định nghĩa trò chơi cờ. Các trò chơi cờ vua, cờ tướng, cờ caro... thường có đặc điểm: +Có hai người chơi, mỗi người đi một nước khi tới lượt. +Các đấu thủ đều biết mọi thông tin về tình trạng trận đấu. +Trận đấu không kéo dài vô tận. Phải có một đấu thủ thắng hoặc thua hoặc hòa. 1.2/ Cây trò chơi. Để đi được một nước cờ ta thường suy nghĩ đánh nước nào để được có một thế cao. Ngược lại đối phương cũng chống lại bằng một nước đi khác có lợi nhất cho họ. Khi một nước bất kỳ được tạo ra trên bàn cờ gọi là một thế cờ. Tại mỗi bước đi của mỗi đấu thủ, có nhiều cách lựa chọn nước đi. Mỗi cách lựa chọn như vậy được gọi là một trạng thái. Các trạng thái này trong quá trình chơi có thể biểu diễn thành một không gian tìm kiếm hay cây trò chơi. Vì tại mỗi trạng thái có khá nhiều trạng thái tiếp theo, do đó số nút sẽ tăng rất nhanh theo độ sâu. Vì vậy ta không thể xây dựng và tìm kiếm đến đáy thực sự của cây mà chỉ đến một độ sâu giới hạn nào đó. Việc này được gọi là nghĩ trước một số nước đi. Thông thường cả người và máy chỉ nghĩ được một số nước. II/ Thuật toán alpha-beta. Để thấy được vai trò của Heuristic trong một số ứng dụng, tiểu luận xin trình bày áp dụng thuật giải alpha-beta trong lập trình trò chơi Caro. 1-Nếu mức đang xét là gốc cây: đặt alpha là - và beta là + 2-Nếu đạt đến giới hạn tìm kiếm, lượng tính giá trị của thế cờ hiện tại ứng với người chơi đó. 3-Nếu mức đang xét là MIN (người chơi cực tiểu) a-Thực hiện công việc sau cho đến khi tất cả các con của nó đã được xét với thủ tục alpha-beta hoặc cho đến khi alpha lớn hơn hoặc bằng beta +áp dụng thủ tục alpha-beta với alpha và beta hiện tại cho một con. Ghi nhớ nhớ lại kết quả +So sánh giá trị ghi nhớ với giá trị beta, nếu nhỏ hơn thì đặt beta bằng giá trị mới này b-Ghi nhớ lại beta. 4-Nếu mức đang xét là MAX (của người chơi cực đại) a-Thực hiện công việc sau cho đến khi tất cả các con của nó đã được xét với thủ tục alpha-beta hoặc cho đến khi alpha bé hơn hoặc bằng beta +áp dụng thủ tục alpha-beta với alpha và beta hiện tại cho một con. Ghi nhớ nhớ lại kết quả +So sánh giá trị ghi nhớ với giá trị alpha, nếu lớn hơn thì đặt alpha bằng giá trị mới này b-Ghi nhớ lại alpha. Có thể diễn đạt thuật toán trên bằng ngôn ngữ tựa pascal như sau: Function alphabeta(alpha,beta,depth:integer):integer; Var a, b, g: integer; Begin If depth = maxdepth then alphabeta := luongtinh; Else Begin Sinhnuocdi(depth); If depth mod 2 = 1 then Begin g := -infinity; a := alpha; While (g ) do Begin Dithu(depth mod 2, i); If kiemtrathang = may then g := infinity - depth Else g := getmax(g, alphabeta(a, beta, depth+1) ); Undodithu(i); a := getmax(a, g); if depth = 1 then If maxvalue < g then maxvalue := g; end; end Else {depth mod 2=0} Begin g := +infinity; b := beta; While (g > alpha) and () do Begin Dithu(depth mod 2, i); If kiemtrathang = nguoi then g := -infinity + depth Else g := getmin(g,alphabeta(alpha,b,depth+1) ); Undodithu(i); b := getmin(b, g); end; end; alphabeta := g; end; end; Trong đó: -Hàm alphabeta là một hàm đệ quy. -Hàm luongtinh là một hàm lượng giá thế cờ của hai bên: h=h1-h2. Trong đó: h1 thế của máy đánh và h2 là thế của người đánh. h1 được tính: h1=với a là số lượng lớn nhất ký hiệu “0’ của máy đứng liền nhau theo một hướng. h2 cũng được tính tương tự như vậy. -Thủ tục sinhnuocdi: nhằm tạo ra các trạng thái kế tiếp của trạng thái hiện tại. Các trạng thái này được ghép với những trạng thái chưa được xét ở trước. -Thủ tục dithu: nhằm chọn thử một trạng thái để lượng giá. -Thủ tục Undodithu: nhằm gỡ trạng thái thử để quay lui với trạng thái khác. -Hàm kiemtrathang: cho giá trị 1 nếu máy thắng, cho giá trị 2 nếu người thắng. Hàm này đếm số lượng các dấu “X” hoặc “O” đứng liền nhau. Thuật toán alpha-beta là một thuật toán cổ điển, do đó còn có nhiều hạn chế về thời gian để thực hiện một nước đi cũng như hiệu quả của nước đi đó. Chương trình trò chơi Caro được viết trên ngôn ngữ lập trình Pascal, do được viết sát với quan điểm của thuật giải alpha-beta nên thời gian để máy thực hiện một nước đi khá lớn. Để cải tiến về mặt tốc độ của chương trình, tác giả xin trình bày thêm một chương trình thứ hai, trong đó đã có sự cải tiến nhiều về thuật giải. Nội dung chương trình trò chơi Caro được lưu trên đĩa CD kèm theo với tiểu luận. Phần III. Kết luận Tiểu luận này đã trình bày các phương án tìm kiếm lời giải dựa theo nguyên lý Heuristic. Hai phương pháp cơ bản của tìm kiếm lời giải là tìm kiếm theo chiều sâu và tìm kiếm theo chiều rộng. Tìm kiếm theo chiều sâu chỉ quan tâm mở rộng trạng thái mà nó chọn và bỏ qua toàn bộ những trạng thái không được chọn. Phương pháp này không tốn không gian lưu trữ các trạng thái, nhưng nó có thể đi lạc hoặc luẩn quẩn trong một nhánh nào đó rất xa với lời giải. Tìm kiếm chiều rộng lại tiến hành mở rộng các trạng thái có thể có ở từng bước. Phương pháp này xét hết toàn bộ các khả năng có thể xảy ra một cách cẩn thận trong từng bước do đó tốn rất nhiều thời gian để lưu trữ các trạng thái này. Một cải tiến của tìm kiếm chiều sâu là tìm kiếm leo núi theo nguyên lý “bước sau phải cao hơn bước trước”. Có hai kiểu leo núi cơ bản là leo núi đơn giản và leo núi dốc đứng. Leo núi đơn giản chọn đi theo trạng thái đầu tiên mà nó cho là thuận lợi hơn trạng thái hiện tại. Leo núi dốc đứng chọn đi theo trạng thái tốt nhất trong số trạng thái thuận lợi hơn trạng thái hiện tại. Nhược điểm chính của leo núi là khả năng quay lui rất hạn chế khi gặp phải những trường hợp đặc biệt của không gian tìm kiếm như cực trị địa phương hoặc miền đơn điệu ngang. Một cải tiến hiệu quả và linh động đó là tìm kiếm ưu tiên tốt nhất (BFS) bằng cách phối hợp được sức mạnh của tìm kiếm chiều sâu và chiều rộng. Tìm kiếm BFS giống tìm kiếm leo núi dốc đứng, nghĩa là chọn đi theo hướng có triển vọng nhất nhưng không phải chỉ hạn hẹp trong tập trạng thái kế tiếp có thể mở rộng từ trạng thái hiện tại, mà trong tập tất cả trạng thái mà nó đã tới nhưng chưa kịp xét đến. Một phiên bản đặc biệt của BFS là A*. Thuật giải A* đánh giá tính tốt của một trạng thái dựa trên tổng của hai giá trị: khả năng đến lời giải h’ và chi phí tối ưu thực sự g để đi từ trạng thái bắt đầu đến trạng thái đang xét. Điều chỉnh hai giá trị g và h’ thích hợp, chúng ta lại có các thuật giải: tìm kiếm theo chiều sâu, tìm kiếm theo chiều rộng, tham lam,... A* là thuật giải kinh điển của Heuristic. Tuy linh động và hiệu quả nhưng A* và BFS có một khuyết điểm lớn đó là tốn quá nhiều bộ nhớ để lưu trữ các trạng thái. Để giải quyết điều này, người ta đã đưa ra một số giải pháp phối hợp giữa BFS và tìm kiếm quay lui. Lời kết: Để hoàn thành được đề tài này, ngoài sự nỗ lực và cố gắng của bản thân, tác giả đã nhận được sự giúp đỡ quý báu của Quý Thầy, GS.TS.Nguyễn Thanh Thủy. Là một học viên chuyên ngành Tin học và dù rất tâm đắc với đề tài đang nghiên cứu nhưng với thời gian có hạn và khối lượng kiến thức của bản thân còn ít ỏi nên chắc chắn tiểu luận không tránh khỏi những hạn chế trong việc tiếp cận, nghiên cứu và trình bày. Tác giả xin kính trọng cảm ơn sự giúp đỡ quý báu của Quý Thầy và mong được đón nhận từ Quý Thầy sự góp ý để giúp bản thân tác giả có được hiểu biết đúng hơn đối với vấn đề đang nghiên cứu đồng thời mong được sự lượng thứ cho những sơ suất trong tiểu luận này. Tài liệu tham khảo 1-Nguyễn Thanh Thủy-Trí tuệ nhân tạo-NXBGD-1995 2-Hoàng Kiếm-Giải một bài toán trên máy tính như thế nào-NXBGD-2003 3-Vũ Đức Thi-Thuật toán trong tin học-NXB KH-KT-1999 4-George F.Luger and William A. Stubblefield-Bùi Xuân Toại và Trương Gia Việt dịch-Trí tuệ nhân tạo-Các cấu trúc và chiến lược giải quyết vấn đề-NXB Thống kê-2000 4-J.Perl-Heuristic, Intelligent research strategies for Computer Problem Solving-University of Califonia-1989 5-Zbigniew Michalewicz, David B.Fogel-How to solve it: modern heurisstic-Addison-Wesley-1989 Mục lục Nội dung Trang Mở đầu ......................................................................................................................................................... 1 Nội dung ........................................................................................................................................ ............ 2 A-Một số phương pháp tìm kiếm lời giải............................................................ ............ 2 I-Tìm kiếm theo chiều sâu và tìm kiếm theo chiều rộng........................ ............ 2 II-Tìm kiếm leo núi................................................................................................................ ............ 2 III-Tìm kiếm ưu tiên tốt nhất (BFS) và thuật giải A*................................ ............ 7 IV-Các chiến lược phối hợp............................................................................................ ............ 12 B-Sử dụng Heuristic trong trò chơi........................................................................... ............ 14 I-Thuật toán Minimax.......................................................................................................... ............ 14 II-Thuật toán Alpha-beta.................................................................................................... ........... 15 C-Lập trình minh họa.......................................................................................................... ............ 16 I-Một số định nghĩa.......................................................................................................... ................ 16 II-Thuật toán Alpha-beta.................................................................................................... ........... 17 Kết luận ................................................................................................................................................... 20 Tài liệu tham khảo ............................................................................................................................. 21