Thiết lập một số thuật giải tìm kiếm

53 Chương 4 Thiết lập một số thuật giải tìm kiếm Chương 4 của luận văn trình bày về việc tổng quát hóa một số thuật giải tìm kiếm. Việc tổng quát hóa xuất phát bằng cách xây dựng thuật giải tìm kiếm tổng quát và mở rộng dần sang các thuật giải đặc thù khác như tìm kiếm theo chiều sâu, tìm kiếm theo chiều rộng … đến các thuật giải heuristics, thuật giải leo đồi, thuật giải A* … Phần còn lại của chương 4 là một số ví dụ việc áp dụng khung thuật giải tìm kiếm này cho từng thuật toán tìm kiếm cụ thể. 4.1 Họ thuật giải tìm kiếm Bài toán tìm kiếm là một trong những bài toán cơ bản nhưng quan trọng bật nhất của khoa học máy tính. Yêu cầu đặt ra của bài toán chỉ đơn giản là tìm một lời giải thỏa mãn bài toán bằng cách duyệt qua một số ứng viên trong không gian tìm kiếm. Mỗi thứ tự chờ duyệt của các ứng viên trong không gian tìm kiếm này lại trở thành mỗi thuật giải khác nhau. Ví dụ thứ tự chờ duyệt phần tử của thuật giải tìm kiếm theo chiều sâu theo cơ chế “vào sau ra trước” rõ ràng khác hẳn với thứ tự chờ duyệt “vào trước ra trước” của thuật giải tìm kiếm theo chiều rộng. 54 Các bài toán tìm kiếm được phân loại như sau: - Tìm kiếm không có thông tin: Một thuật giải tìm kiếm không có thông tin là thuật giải không tính đến bản chất cụ thể của bài toán. Khi đó, các thuật giải dạng này có thể được cài đặt tổng quát, và cùng một cài đặt có thể được sử dụng trong một diện rộng các bài toán (do sử dụng trừu tượng hóa). Nhược điểm của các thuật giải này là phần lớn các không gian tìm kiếm có kích thước cực kì lớn. Thuật giải tìm kiếm không có thông tin được phân loại như sau: o Tìm kiếm trên danh sách: Có lẽ các thuật giải tìm kiếm trên danh sách là loại thuật giải tìm kiếm cơ bản nhất. Mục đích là tìm trong một tập hợp một phần tử chứa một khóa có giá trị cho trước. Do đây là một bài toán thường gặp trong khoa học máy tính, nên độ phức tạp tính toán của các thuật giải này đã được nghiên cứu kỹ càng. Thuật giải đơn giản nhất là tìm kiếm tuyến tính. Thuật giải này kiểm tra từng phần tử trong danh sách theo thứ tự của danh sách đó. Nó có thời gian chạy khá lớn: ( ), trong đó n là số phần tử trong danh sách, nhưng có thể sử dụng thẳng cho một danh sách bất kỳ mà không cần tiền xử lý. Tìm kiếm nhị phân là một thuật giải cao cấp hơn với thời gian chạy là ( ). Đối với các danh sách lớn, thuật giải này tốt hơn hẳn tìm kiếm tuyến tính, nhưng nó đòi hỏi danh sách phải được sắp xếp từ và có khả năng truy xuất ngẫu nhiên. Tìm kiếm nội suy tốt hơn tìm kiếm nhị phân đối với các danh sách rất lớn với phân bố gần đều. o Tìm kiếm trên cây: Tìm kiếm trên cây là trung tâm của các kỹ thuật tìm kiếm. Các thuật giải này tìm kiếm trên các cây gồm các nút, cây này có thể là cây tường minh hoặc được xây dựng dần trong quá trình tìm kiếm. Nguyên lý cơ bản là: một nút được lấy ra từ một cấu trúc dữ liệu, các nút con của nó được xem xét và bổ sung vào cấu trúc dữ liệu đó. Bằng cách thao tác trên cấu trúc dữ liệu này, cây tìm kiếm được duyệt theo các thứ tự khác nhau, chẳng hạn theo từng mức (tìm kiếm 55 theo chiều rộng) hoặc đi tới một nút lá trước rồi quay lui (tìm kiếm theo chiều sâu). Các ví dụ khác về tìm kiếm trên cây bao gồm: tìm kiếm lặp sâu dần, tìm kiếm chiều sâu giới hạn, tìm kiếm hai chiều và tìm kiếm chi phí đều. o Tìm kiếm trên đồ thị: Nhiều bài toán về lý thuyết đồ thị có thể được giải quyết bằng các thuật giải tìm kiếm, chẳng hạn thuật giải Dijkstra, thuật giải Kruskal, thuật giải láng giềng gần nhất và thuật giải Prim. Các thuật giải này có thể được coi là các mở rộng của các thuật giải tìm kiếm trên cây. - Tìm kiếm có thông tin: Trong tìm kiếm có thông tin, người ta sử dụng một đánh giá heuristic đặc thù cho bài toán cần giải quyết với vai trò hướng dẫn cho quá trình tìm kiếm. Một cách đánh giá heuristic tốt sẽ làm cho quá trình tìm kiếm có thông tin hoạt động hiệu quả hơn hẳn một phương pháp tìm kiếm không có thông tin bất kỳ. Có một vài thuật giải tìm kiếm có thông tin nổi trội dành cho danh sách. Một trong số đó là một bảng băm với một hàm băm là một heuristic đựa trên bài toán đang được giải. Đa số các thuật giải tìm kiếm có thông tin đều là tìm kiếm trên cây. Trong đó có tìm kiếm theo lựa chọn tốt nhất và A*. Cũng như các thuật giải không có thông tin, các thuật giải này có thể được mở rộng để làm việc trên cả các đồ thị. - Tìm kiếm đối kháng: Trong các trò chơi như cờ vua hay cờ tướng, có một cây trò chơi bao gồm tất cả các nước đi có thể của cả hai đấu thủ và các cấu hình bàn cờ là kết quả của các nước đi đó. Ta có thể tìm kiếm trên cây này để có được một chiến lược chơi hiệu quả. Dạng bài toán này có đặc điểm độc nhất vô nhị là ta phải tính đến mọi nước đi mà đối thủ của ta có thể sử dụng. Để làm điều này, các chương trình máy tính chơi cờ, cũng như các dạng khác của trí tuệ nhân tạo như lập kế hoạch tự động (machine planning), thường sử dụng các thuật giải tìm kiếm như thuật giải minimax, tỉa cây tìm kiếm, và tỉa cây alpha-beta (alpha-beta pruning). 56 - Tìm kiếm thỏa mãn ràng buộc: Đây là một loại tìm kiếm để giải quyết các bài toán thỏa mãn ràng buộc mà trong đó, thay vì tìm một đường đi, lời giải chỉ đơn giản là một tập các giá trị được gán cho một tập các biến. Do các biến có thể được xử lý theo thứ tự tùy ý, các thuật giải thông thường dành cho tìm kiếm trên cây rất không hiệu quả. Các phương pháp giải các bài toán ràng buộc bao gồm tìm kiếm tổ hợp và quay lui, cả hai đều tận dụng các đặc điểm tự do có liên quan đến các bài toán ràng buộc. - Và một số loại khác: các thuật giải tìm xâu kí tự con, thuật giải tabu, thuật giải di truyền, thuật giải mô phỏng tôi luyện … cũng thuộc họ giải thuật tìm kiếm này. Trong khuôn khổ của luận văn, chúng tôi chỉ đề cập đến một số các thuật giải tìm kiếm thông dụng như tìm kiếm theo chiều sâu, tìm kiếm theo chiều rộng, thuật giải A* hay thuật giải leo đồi … 4.2 Xây dựng thuật giải tìm kiếm tổng quát Để xây dựng thuật giải tìm kiếm tổng quát, ta xét điểm tương đồng về bản chất của các thuật giải tìm kiếm. Về cơ bản, hầu hết các thuật giải tìm kiếm đều lần lượt tìm kiếm ứng viên lời giải trong không gian tìm kiếm và kiểm tra đây có phải lời giải của bài toán hay không? Thuật giải sẽ dừng khi tìm được lời giải hoặc đã duyệt hết không gian tìm kiếm. Mã giả thuật giải tìm kiếm tổng quát được mô tả trong bảng 4-1. Bảng 4-1 Mã giải thuật giải tìm kiếm Thủ tục: tìm kiếm 1. Bắt đầu với x là một lời giải bất kì của không gian tìm kiếm 2. Nếu x là lời giải cần tìm. Dừng thuật giải à Thành công. 3. Nếu x không là lời giải cần tìm. Thực hiện tiếp tục bước 2 với x là phần tử kế tiếp trong danh sách chờ duyệt. Nếu không còn phần tử nào chưa tìm thì dừng thuật giải à Thất bại. 57 Từ mã giả trên, ta xây dựng khung giải thuật tìm kiếm kế thừa từ khung giải thuật tổng quát đã trình bày ở chương 2 như sau. Lớp ℎ kế thừa và cái đặt thuật giải tìm kiếm tổng quát () kế thừa từ lớp giải quyết bài toán tổng quát . Hàm ℎ() được gọi từ hàm () sẽ thực hiện một số lời gọi đến các hook của lớp thuật giải tìm kiếm tổng quát ℎ , cụ thể là hàm tạo danh sách chờ duyệt của các ứng viên () . Hàm () này sẽ trả về một đối tượng biểu diễn danh sách các ứng viên sẽ được duyệt. Thao tác trên lớp này sẽ được thực thi tại các lớp duyệt danh sách ứng viên của thuật giải tìm kiếm cụ thể thông qua các hàm hook: (), (), () … Bảng 4-2 Thuật giải tìm kiếm tổng quát class SearchSolver implements Solver { public SearchSolution solveBySearch(SearchProblem problem) { // khởi tạo iterator danh sách chờ duyệt ứng viên SearchStrategy.Iterator iterator = strategy.createExploringList(problem); // lặp khi còn phần tử trong danh sách chờ duyệt while (!iterator.isEmpty()) { // lấy một ứng viên trong danh sách chờ duyệt Object candidate = iterator.select(); // nếu ứng viên này là lời giải, chọn ứng viên làm lời giải // và dừng việc lặp if (problem.isSolution(candidate) { return SearchSolution.makeSolution(candidate); } // mở rộng danh sách ứng viên chờ duyệt iterator.explore(problem, candidate); } return SearchSolution.makeSolution(null); } } interface SearchProblem extends Problem { 58 boolean isSolution(Object choices); Object getInitState(); Iterator explore(Object candidate); }; interface SearchSolution extends Solution {} abstract class SearchStrategy implements Strategy { static abstract class Iterator { public abstract boolean isNotEmpty (); public abstract Object select (); public abstract void explore (SearchProblem p, Object c); public abstract void add(Object c); } // tạo danh sách chờ duyệt các ứng viên protected abtract Iterator createExploringList(SearchProblem p); } Với cách triển khai như trên, ta có thể mô hình hóa lại khung giải thuật tìm kiếm tương tự cách mô hình hóa các thuật giải ở chương 3 như Hình 5-1. Hình 4-1 Thuật giải tìm kiếm tổng quát 59 4.3 Các thuật giải tìm kiếm cụ thể Sau khi xây dựng xong giải thuật tìm kiếm tổng quát, ta lần lượt bổ sung vào khung giải thuật tìm kiếm các giải thuật tìm kiếm cụ thể. Các giải thuật tìm kiếm này sẽ lần lượt kế thừa thuật giải tìm kiếm tổng quát và kế thừa các hàm hook liên quan đến thứ tự chờ duyệt của không gian tìm kiếm. 4.3.1 Thuật giải tìm kiếm ưu tiên chiều sâu Thuật giải tìm kiếm ưu tiên chiều sâu (depth-first-search) là một dạng thuật giải tìm kiếm thông tin không đầy đủ. Quá trình tìm kiếm bắt đầu từ một phần tử trong không gian tìm kiếm rồi duyệt tiếp phần tử kế tiếp chưa được duyệt của phần tử này. Bước lặp trên được thực hiện liên tục đến khi phần tử vừa duyệt là không còn phần tử nào kế tiếp, thuật giải sẽ quay lui lại phần tử mới vừa duyệt ở bước kế trước. Khi thực thi thuật giải dưới dạng không đệ quy, thứ tự các phần tử chờ duyệt sẽ được lần lượt bổ sung vào một ngăn xếp. Với bản chất thuật giải như vậy, ta nhận thấy thuật giải tìm kiếm ưu tiên chiều sâu sẽ kế thừa thuật giải tìm kiếm tổng quát với thứ tự của danh sách chờ duyệt là “vào sau ra trước”. Ta xây dựng lớp thuật giải tìm kiếm ưu tiên chiều sâu ℎ ℎ kế thừa từ ℎ trong đó hàm hook () sẽ tạo ra một đối tượng ℎ kế thừa từ ℎ . . ℎ sẽ hoạt động theo cơ chế “vào sau ra trước”. Khi cài đặt bằng ngôn ngữ lập trình Java, ta có thể sử dụng một hoặc một với thao tác thêm phần tử vào đầu danh sách và lấy phần tử ở cuối danh sách. Mã giã thuật giải tìm kiếm ưu tiên chiều sâu cài đặt kế thừa từ thuật giải tìm kiếm tổng quát được mô tả trong Bảng 4-3. 60 Bảng 4-3 Thuật giải tìm kiếm ưu tiên chiều sâu class DepthFirstSearch extends SearchStrategy { class DepthFirstIterator extends SearchStrategy.Iterator { // cài đặt lớp duyệt ứng viên theo cơ chế vào sau ra trước // với phần tử ban đầu bất kì theo yêu cầu của bài toán } protected Iterator createExploringList (SearchProblem p) { return new DepthFirstIterator (p); } } 4.3.2 Thuật giải tìm kiếm ưu tiên chiều rộng Thuật giải tìm kiếm ưu tiên chiều rộng (breadth-first-search) là một dạng thuật giải tìm kiếm thông tin không đầy đủ. Quá trình tìm kiếm bắt đầu từ một phần tử trong không gian tìm kiếm rồi duyệt qua tất cả phần tử kế tiếp chưa được duyệt của phần tử này. Sau đó, ứng với mỗi phần tử kế đó, thuật giải lại duyệt hết các phần tử kế của nó. Và liên tục lặp như vậy đến khi tìm ra lời giải hoặc thuật giải đã duyệt qua tất cả phần tử của không gian tìm kiếm. Khi thực thi thuật giải dưới dạng không đệ quy, thứ tự các phần tử chờ duyệt sẽ được lần lượt bổ sung vào một hàng đợi. Với bản chất thuật giải như vậy, ta nhận thấy thuật giải tìm kiếm ưu tiên chiều rộng sẽ kế thừa thuật giải tìm kiếm tổng quát với thứ tự của danh sách chờ duyệt là “vào trước ra trước”. Tương tự như ℎ ℎ, ta xây dựng lớp thuật giải tìm kiếm ưu tiên chiều rộng ℎ ℎ kế thừa từ ℎ trong đó hàm hook () sẽ tạo ra một đối tượng ℎ hoạt động theo cơ chế “vào trước ra trước”. Khi cài đặt bằng ngôn ngữ lập trình Java, ta có thể sử dụng một hoặc một với thao tác thêm phần tử vào cuối danh sách và lấy phần tử ở cuối danh sách. 61 Mã giã thuật giải tìm kiếm ưu tiên chiều rộng cài đặt dựa trên khung thuật giải tìm kiếm được mô tả trong Bảng 4-4. Bảng 4-4 Thuật giải tìm kiếm ưu tiên chiều rộng class BreadthFirstSearch extends SearchStrategy { class BreadthFirstIterator extends SearchStrategy.Iterator { // cài đặt lớp duyệt ứng viên theo cơ chế vào trước ra trước // với phần tử đầu tiên bất kì theo yêu cầu của bài toán } protected Iterator createExploringList (SearchProblem p) { return new BreadthFirstIterator (p); } } 4.3.3 Thuật giải tìm kiếm ưu tiên lựa chọn tốt nhất 4.3.3.1 Thuật giải tìm kiếm ưu tiên lựa chọn tốt nhất tổng quát Thuật giải tìm kiếm ưu tiên lựa chọn tốt nhất (best-first-search) là một dạng của tìm kiếm có thông tin. Nó duyệt qua không gian tìm kiếm theo thứ tự ưu tiên của các phần tử theo một quy tắc đặt trước. Judea Pearl mô tả thuật giải tìm kiếm ưu tiên lựa chọn tốt nhất được thực hiện bởi việc ước lượng giá trị thỏa mãn lời giải của phần tử n bởi một hàm lượng giá heuristic. Hàm lượng giá này sẽ phụ thuộc vào giá trị của phần tử n, yêu cầu của lời giải, và những thông tin thu thập trong quá trình duyệt trước đó và quan trọng nhất là phụ thuộc vào mọi tri thức bổ sung về miền xác định của bài toán. Các thuật giải tìm kiếm theo lựa chọn tốt nhất thường được sử dụng để tìm đường trong quá trình tìm kiếm tổ hợp, ví dụ như thuật giải và thuật giải tìm kiếm ∗… Rõ ràng về mặt bản chất, thuật giải tìm kiếm ưu tiên lựa chọn tốt nhất hoàn toàn tương thích với thuật giải tìm kiếm tổng quát đã trình bày ở Mục 5-2, chỉ khác ở 62 danh sách thứ tự chờ duyệt của các ứng viên. Để tăng hiệu quả cho việc thực thi, danh sách chờ duyệt này sẽ được cài đặt bằng một hàng đợi ưu tiên. Từ đó, ta có thể xây dựng lớp thuật giải tìm kiếm ưu tiên lựa chọn tốt nhất ℎ kế thừa từ ℎ trong đó hàm hook () sẽ tạo ra một đối tượng hoạt động theo cơ chế chọn phần tử có giá trị hàm lượng giá tốt nhất. Khi cài đặt bằng ngôn ngữ lập trình Java, ta thể sử dụng kết hợp với một lớp Comparator để so sánh hàm lượng giá . Comparator là lớp tổng quát biểu diễn hàm so sánh và biểu diễn hàm lượng giá bất kì. Hai lớp này có sẵn trong STL của C++ ( và ), khi sử dụng ta phải cài đặt lại theo cơ chế tương tự. Bảng 4-5 Thuật giải tìm kiếm ưu tiên lựa chọn tốt nhất class BestFirstSearch extends SearchStrategy { class BestFirstIterator extends SearchStrategy.Iterator { public BestFirstIterator(SearchProblem p, Function f) { // tạo mới hàng đợi ưu tiên với comparator theo f } public Object select () { // hàm này trả về vị trí đầu tiên của hàng đợi ưu tiên } public void explore () { // thêm phần tử mới vào hàng đợi và cập nhật lại thứ tự } } protected Iterator createExploringList (SearchProblem p) { return new BestFirstIterator (p, getEvalFunc() ); } } 63 4.3.3.2 Thuật giải A* Thuật giải A* là một thuật giải tìm kiếm có thông tin được sử dụng để tìm một đường đi từ một phần tử khởi đầu tới một phần tử đích cho trước (hoặc tới một phần tử thỏa mãn một điều kiện đích). Thuật giải này sử dụng một hàm lượng giá heuristic để xếp loại từng phần tử theo ước lượng về tuyến đường tốt nhất đi qua phần tử đó và duyệt các phần tử theo thứ tự của đánh giá heuristic này. Do đó, thuật toán ∗ là một trường hợp của tìm kiếm ưu tiên lựa chọn tốt nhất (best-first search). Do xác định thuật giải ∗ chính là một trường hợp của thuật giải ưu tiên lựa chọn tốt nhất nên ta dễ dàng xây dựng lớp AStar biểu diễn thuật giải ∗ kế thừa trực tiếp từ thuật giải best-first search. Bảng 4-6 Thuật giải A* class AStar extends BestFirstSearchStrategy { protected Function getEvalFunc() { // trả về hàm lượng giá heuristic } } 4.3.4 Thuật giải tìm kiếm cục bộ 4.3.4.1 Thuật giải tìm kiếm cục bộ tổng quát Thuật giải tìm kiếm cục bộ (hoặc thuật giải tìm kiếm địa phương) là giải pháp metaheuristic cho việc giải các bài toán tính toán tối ưu khó trong máy tính. Thuật giải này có thể được áp dụng cho các bài toán tìm kiếm lời giải gần đúng tối ưu trong một loạt các lời giải ứng viên. Phương pháp tìm kiếm sẽ duyệt qua các lời giải trong không gian tìm kiếm cho đến khi lời tìm ra lời giải được cho là tối ưu hoặc vượt quá thời gian tìm kiếm cho phép. Một số bài toán kinh điển có thể áp dụng 64 thuật giải tìm kiếm cục bộ như: bài toán người du lịch, bài toán xếp lịch trực y tá, bài toán tìm tập phủ đỉnh của đồ thị … Thuật giải tìm kiếm cục bộ sẽ bắt đầu từ một ứng viên lời giải, kiểm tra và liên tục chọn sang ứng viên lời giải kế tiếp (hay ứng viên láng giềng) đến khi dừng thuật giải. Tuy nhiên mỗi ứng viên lời giải đều có thể có hơn một lời giải láng giềng, cho nên mỗi cách lựa chọn lời giải láng giềng trong danh sách láng giềng để thành bước duyệt kế tiếp có thể trở thành một thuật giải khác. Bảng 4-7 Thuật giải tìm kiếm cục bộ abtract class LocalSearch extends SearchStrategy { abtract class LocalSearchIterator extends SearchStrategy.Iterator { public Object select () { // trả về phần tử đang chờ duyệt hoặc null } public void explore () { // chọn chỉ một phần tử láng giềng làm phần tử chờ duyệt // kế tiếp } } protected Iterator createExploringList (SearchProblem p) { return new LocalSearchIterator (p); } } 4.3.4.2 Thuật giải leo đồi Thuật giải leo đồi là kỹ thuật giải bài toán theo phương pháp toán tối ưu, thuộc họ thuật giải tìm kiếm cục bộ. Ở mỗi bước chọn phần tử kế tiếp trong thuật giải tìm kiếm cục bộ, thuật giải leo đồi chọn phần tử có giá trị tương thích cao nhất theo một hàm lượng giá có sẵn. Mã giả thuật giải leo đồi được thể hiện trong Bảng 4-8 65 Bảng 4-8 Mã giả thuật giải leo đồi Hill Climbing Algorithm currentNode = startNode; loop do L = NEIGHBORS(currentNode); nextEval = -INF; = NULL; for all x in L if (EVAL(x) > nextEval) nextNode = x; = EVAL(x); if nextEval <= EVAL(currentNode) return currentNode; currentNode = nextNode; Tuy nhiên, khi cài đặt thuật giải leo đồi trong khung thuật giải tìm kiếm. Ta nhận xét rằng thuật giải leo đồi là một trường hợp của thuật giải tìm kiếm cục bộ. Do vậy ta có thể cài đặt thuật giải leo đồi kế thừa từ thuật giải tìm kiếm cục bộ như sau: Bảng 4-9 Thuật giải leo đồi kế thừa từ thuật giải tìm kiếm cục bộ class HillClimbing extends LocalSearch { abtract class HillClimbingIterator extends SearchStrategy.Iterator { public Object select () { // trả về phần tử đang chờ duyệt hoặc null } public void explore () { // chọn chỉ một phần tử láng giềng có giá trị tương thích // cao nhất làm phần tử kế tiếp } } protected Iterator createExploringList (SearchProblem p) { return new HillClimbingIterator (p, getEvalFunc() ); } } 66 4.4 Tổng kết Như vậy qua quá trình xây dựng thuật giải tìm kiếm tổng quát và các thuật giải tìm kiếm cụ thể giải thuật kế thừa từ lớp thuật giải tìm kiếm ℎ , ta đã hình thành một khung thuật giải gọi là khung thuật giải dành cho các thuật giải tìm kiếm. Mỗi thuật giải tìm kiếm cụ thể sẽ cài đặt hàm nhượng quyền lại một số hàm của lớp thuật giải tổng quát, và quan trọng nhất là hàm select() để chọn một phần tử và hàm explore() để cập nhật danh sách ứng viên chờ duyệt. Thuật giải Cài đặt hàm nhượng quyền Ghi chú Depth-First- Search select(): Chọn ứng viên mới đưa vào, xóa khỏi danh sách explore(c): Đưa vào danh sách các phần tử kề của c Stack Breadth- First-Search select(): Chọn ứng viên sớm nhất trong danh sách, xóa khỏi danh sách explore(c): Đưa vào danh sách các phần tử kề của c Queue Best-First- Search select(): Chọn ứng viên có giá trị lượng giá cao nhất trong danh sách, xóa khỏi danh sách explore(c): Đưa vào danh sách các phần tử