Xây dựng khung thuật giải

30 Chương 2 Xây dựng khung thuật giải Chương 2 của luận văn trình bày về kiến trúc khung thuật giải và việc vận dụng các mẫu thiết kế hướng đối tượng để xây dựng nó ở mục 2.1. Từ đó sử dụng mô hình này để đặc tả lại một số nhóm thuật giải quan trọng như thuật giải chia để trị, thuật giải quay lui, thuật giải tham lam … cùng kèm theo một số ví dụ minh họa. 2.1 Xây dựng khung thuật giải tổng quát Trước khi xây dựng khung thuật giải, ta xem qua phương pháp xây dụng khung phần mềm. Ở tài liệu tham khảo [3], các tác giả đã chỉ ra hai nguyên lý xây dựng khung phần mềm: nguyên lý hợp nhất và nguyên lí phân tán. Nguyên lý hợp nhất xây dựng khung phần mềm dựa trên mẫu thiết kế ℎ . Trong đó, những điểm tương đồng sẽ được giữ trong phương thức mẫu của lớp cơ sở và những điểm khác biệt sẽ được thi công ở các hàm nhượng quyền ℎ tại các lớp con. Còn nguyên lý phân tán dựa trên mẫu thiết kế , trong đó những điểm tương đồng sẽ được giữ trong các phương thức cụ thể của client còn những điểm khác biệt sẽ được mô tả trong lớp trừu tượng và được thi công ở các lớp 31 con của nó. Trong khuôn khổ của luận văn này, nguyên lý phân tán được sử dụng để xây dựng khung thuật giải tổng quát. Bắt đầu với việc xây dựng khung thuật giải cho việc giải bài toán bằng thuật giải, ta bắt đầu với ba khái niệm cốt lõi trong việc giải bài toán là: bài toán đặt ra, phương pháp để giải bài toán và kết quả đạt được. Ví dụ ứng với bài toán sắp xếp dãy số theo thứ tự tăng dần thì kết quả cần đạt được là dãy số được sắp xếp tăng, và những phương pháp ta có thể sử dụng cho bài toán này là thuật giải sắp xếp nổi bọt, thuật giải sắp xếp chèn, thuật giải sắp xếp nhanh … Hoặc với bài toán tìm kiếm một phần tử trong mảng, ta có thể sử dụng thuật giải tìm kiếm tuần tự hoặc thuật giải tìm kiếm nhị phân để xác định kết quả của bài toán: tồn tại phần tử đó trong mảng hay không? Với những nhận xét trên, ta định nghĩa các khái niệm , và . Trong đó, biểu diễn một bài toán bất kì, biểu diễn chiến thuật hoặc phương pháp có thể áp dụng để giải bài toán và biểu diễn kết quả trả về của bài toán khi áp dụng thuật giải để giải. Theo nguyên lý phân tán ta đưa ra khung thuật giải tổng quát như hình 3-1: Hình 2-1 Khung thuật giải tổng quát 32 Trong mô hình này, giao diện biểu diễn việc giải với bất kì. Kết quả của lời giải này trả về một . Khi cụ thể hóa với họ thuật giải . Lớp sẽ kế thừa từ và triển khai cụ thể phương thức () ứng với lời giải tổng quát của mình để giải quyết bài toán và trả về kết quả trong . Trong phương thức () này sẽ gọi đến các phương thức ảo nhượng quyền (hook) của lớp biểu diễn chiến lược tổng quát . Ứng với từng thuật giải cụ thể ℎ 1, ℎ 2 … sẽ thi công những hàm ℎ này tương ứng với cách giải quyết vấn đề của mình. Để minh họa việc sử dụng khung thuật giải cho từng họ thuật giải cụ thể, mục 3.2 của luận văn sẽ trình bày cách xây dựng các họ thuật giải kinh điển như chia để trị, quay lui, tham lam … 2.2 Một số khung thuật giải cụ thể 2.2.1 Khung thuật giải chia để trị Chia để trị là một trong những kỹ thuật phổ biến được sử dụng để giải bài toán bằng cách chia bài toán gốc thành một hoặc nhiều bài toán đồng dạng có kích thước nhỏ hơn, rồi giải lần lượt từng bài toán nhỏ một cách độc lập. Lời giải của bài toán gốc chính là sự kết hợp lời giải của những bài toán con. Có rất nhiều các thuật giải kinh điển dựa trên phương pháp này như thuật giải tìm kiếm nhị phân ( ℎ), thuật giải sắp xếp nhanh ( ), thuật giải sắp xếp trộn ( )… Mã giả của thuật giải chia để trị tổng quát được minh họa trong Bảng 3-1. Bảng 2-1 Mã giả thuật giải chia để trị DIVIDE: Chia bài toán p thành các bài toán con CONQUER: Lần lượt giải các bài toán con. Trong trường hợp kích thước bài toán con đủ nhỏ, trả về lời giải trực tiếp COMBINE: Kết hợp lời giải của các bài toán con để đạt lời giải của bài toán gốc 33 Từ mã giả trên, ta nhận thấy có thể cài đặt hàm () biểu diễn một phương thức mẫu chung cho tất cả các thuật giải thuộc họ chia để trị. Bảng 2-2 Thuật giải chia để trị tổng quát DivConqSolution solveByDivConq (DivConqProblem problem) { // kiểm tra tính đơn giản của bài toán if (statregy.isSimple (problem)) // giải bài toán trực tiếp trong trường hợp đơn giản return statregy.simplySolve (problem) // chia nhỏ bài toán thành nhiều bài toán con DivConqProblem subProblems[] = statregy.divide (problem) // giải lần lượt các bài toán con DivConqSolution subSolutions[] = new DivConqSolution[subProblems.length]; for ( i = 0; i < subProblems.length; i++ ) subSolutions[i] = solveByDivConq ( subProblems[i] ) // kết quả của bài toán là sự kết hợp kết quả các bài toán con return statregy.combine ( subSolutions ) } Giải thích chức năng của các hàm nhượng quyền: isSimple(): Kiểm tra tính đơn giản của bài toán simplySolve(): Giải bài toán trong trường hợp đơn giản divide(): Chia nhỏ bài toán thành nhiều bài toán con combine(): Kết hợp lời giải bài toán con về lời giải bài toán gốc Các hàm (), (), () và () chính là các hàm ℎ và sẽ được thi công ở các lớp biểu diễn thuật giải cụ thể trong nhóm. Mỗi thuật giải khác nhau sẽ hiện thực các hàm nhượng quyền này khác nhau. Ví dụ, hàm () được thực hiện khác nhau giữa và , chỉ đơn giản là ghép hai dãy nhỏ hơn và lớn hơn giá trị cầm canh còn phải trộn hai dãy đã sắp xếp. Hoặc hàm () được thực hiện khác nhau giữa 34 ℎ và ℎ khi thu nhỏ không gian tìm kiếm với tỉ lệ [ ; ] và [1; − 1] Tiếp đến, ta xây dựng khung thuật giải chia để trị tổng quát. Theo khung thuật giải tổng quát đã trình bày ở mục 3-1, ta xây dựng lớp là lớp ngữ cảnh trong khung thuật giải chia để trị và là giao diện thể hiện cách giải quyết bài toán bằng phương pháp chia để trị. Các thuật giải cụ thể sử dụng phương pháp này như ℎ, … sẽ được kế thừa và thi công cụ thể 4 hàm ℎ đã được định nghĩa từ . «interface» Strategy +solve(in : Problem) : ISolution «interface» Solver +isSimple(in : Problem) : bool +simplySolve(in : Problem) : ISolution +divide() : IProblem[] +combine(in : Solution[]) : ISolution «interface» DivConqStrategy +isSimple() +simplySolve() +divide() +combine() QuickSort +isSimple() +simplySolve() +divide() +combine() MergeSort +isSimple() +simplySolve() +divide() +combine() BinarySearch +solve() +solveByDivConq() DivConqSolver public DivConqSolution solveByDivConq (DivConqProblem p) { if isSimple (p) return simplySolve (p); subProblems[] = divide (p); for ( i = 0; i < subProblems.length; i++ ) subSolutions[i] = solve( subProblems[i] ); return combine ( subSolutions[i] ); } «interface» Problem «interface» Solution DivConqProblem DivConqSolution Hình 2-2 Khung thuật giải chia để trị Rõ ràng khi tổng quát hóa thuật giải chia để trị theo mô hình này, bản chất và cả độ phức tạp của thuật giải vẫn không hề thay đổi. Ta có thể tính độ phức tạp của thuật giải theo tính chất 2.1 sau: Tính chất 2.1: Giả sử ( ) biểu diễn thời gian chạy của thuật giải chia để trị, và thuật giải này chia bài toán có kích thước thành bài toán con có kích thước / và chi phí chia và ghép này là ( ) thì ta có ( ) = ∗ + ( ) 35 Và ta có được có được độ phức tạp của thuật giải với các trường hợp như sau [29]: · Trường hợp 1: ∃ > 0: ( ) = ( ) ⇒ ( ) = ( ) · Trường hợp 2: ∃ ≥ 0: ( ) = ( ) ⇒ ( ) = ( ) · Trường hợp 3: ∃ ≥ 0: ( ) = Ω( ) ⇒ ( ) = ( ( )) Ví dụ 2.1: Để minh họa việc sử dụng khung thuật giải chia để trị, ta áp dụng với thuật giải ℎ cho việc tìm kiếm phần tử trong dãy như sau: · Đặc tả bài toán: Bài toán tìm kiếm gồm dữ liệu đầu vào là một mảng các phần tử, một khóa kèm theo phép toán so sánh giữa các phần tử trong danh sách. Lời giải của bài toán là phần tử có tồn tại trong mảng hay không? Để đơn giản, ta xây dựng lớp ℎ để cùng mô tả bài toán và lời giải của nó. Trong đó, cấu trúc mảng được biểu diễn bởi [] và hai chỉ số , ℎ . · Xây dựng thuật giải tìm kiếm nhị phân kế thừa từ thuật giải chia để trị tổng quát: Ta xây dựng lớp ℎ kế thừa và cài đặt 4 hàm ℎ của : o (): Bài toán tìm kiếm được gọi là đơn giản khi dãy tìm kiếm chỉ có 1 phần tử (ℎ = ) hoặc phần tử giữa dãy được chọn có giá trị bằng với khóa tìm kiếm ( [ ] = ). o (): Khi bài toán rơi vào trường hợp đơn giản, kết quả trả về chỉ đơn giản là kết quả việc so sánh phần tử giữa và khóa. o (): Khi phần tử [ ] không phải là giá trị cần tìm, ta sẽ chia nhỏ dãy tùy vào kết quả so sánh giữa nó và khóa. Nếu [ ] > : ta đưa về bài toán tìm kiếm trên dãy [ , − 1], ngược lại ta đưa về bài toán tìm kiếm trên dãy [ + 1, ℎ ]. Trong trường hợp này, bài toán được chia nhỏ thành 2 bài toán con nhưng trong đó có một bài toán con chắc chắn không có lời giải. 36 o (): Do ở bước () ta chỉ chia thành 1 bài toán con nên phương thức kết hợp này không cần thực hiện, chỉ trả về lời giải của bài toán con được chia nhỏ. · Độ phức tạp thuật toán: Dễ dàng nhận thấy, thuật giải này tương ứng với = 1 và = 2 , và ( ) = (1) theo tính chất 2.1 ta tìm được = 0 để ( ) thỏa trường hợp 2, do đó ( ) = ( ). Tương tự, ta có thể sử dụng khung thuật giải chia để trị này cho các thuật giải giải bài toán theo phương pháp chia để trị như , … 2.2.2 Khung thuật giải quay lui Thuật giải quay lui (Lehmer, 1950) là một chiến lược tìm kiếm lời giải cho các bài toán thỏa mãn ràng buộc. Về bản chất, tư tưởng chủ đạo của phương pháp quay lui là thử từng khả năng cho đến khi tìm thấy lời giải đúng. Đó là một quá trình tìm kiếm ưu tiên chiều sâu trong một tập hợp các lời giải. Trong quá trình tìm kiếm, nếu ta gặp một hướng lựa chọn không thỏa mãn ràng buộc, ta quay lui về điểm lựa chọn nơi có các hướng khác và thử hướng lựa chọn tiếp theo. Khi đã thử hết các lựa chọn xuất phát từ điểm lựa chọn đó, ta quay lại điểm lựa chọn trước đó và thử hướng lựa chọn tiếp theo tại đó. Quá trình tìm kiếm thất bại khi không còn điểm lựa chọn nào nữa. Không mất tính tổng quát, ta giả sử lời giải của bài toán được biểu diễn bởi véc-tơ (v1, v2, …, vn). Khi thực hiện, thuật giải sẽ bắt đầu bằng một véc-tơ rỗng, và tại mỗi bước ta sẽ chọn giá trị mới vào một thành phần của véc-tơ kết quả v. Tại bước chọn thành phần vi, khi không chọn được bước kế tiếp, thuật giải sẽ quay lui chọn lại bước trước đó. Mã thuật giải giải quay lui tổng quát được trình bày trong bảng 3-3. Bảng 2-3 Mã giả thuật giải quay lui ALGORITHM try(v1,...,vi) IF (v1,...,vi) is a solution THEN RETURN (v1,...,vi) FOR each v DO 37 IF (v1,...,vi,v) is acceptable vector THEN sol = try(v1,...,vi,v) IF sol != () THEN RETURN sol END END RETURN () Từ mã giả trên, ta xây dựng thuật giải quay lui tổng quát (). Bảng 2-4 Thuật giải quay lui tổng quát bool solveByBackTracking BackTrackingProblem problem, int i) { // kiểm tra đã chọn đủ số biến của lời giải hay chưa? if (i > strategy.getNumOfVariables(problem)) { // kiểm tra tập các lựa chọn solution có phải là lời giải? // nếu đúng, thêm solution vào tập các lời giải solutions if (strategy.isAcceptable(solution) { strategy.acceptSolution(solution); return true; } } // nếu chưa, chọn tiếp lựa chọn ở bước thứ i else { // duyệt tất cả các lựa chọn option ở bước thứ i foreach (option in statregy.getOptions(problem,solution,i)) { statregy.setChoice (solution, i, option); // chọn bước i + 1 tiếp theo solveByBackTracking (problem, i + 1); statregy.setChoice (solution, i, null); } } return false; } Giải thích chức năng của các hàm nhượng quyền: getNumOfVariables (): Kích thước không gian lời giải getOptions (): Trả về tất cả các lựa chọn của bài toán ở bước thứ 38 i ứng với các bước đã chọn đến i – 1. isAcceptable(): Kiểm tra các bước lựa chọn có thỏa mãn ràng buộc của bài toán hay không? acceptSolution (): Chấp nhận lời giải setChoice (): Thêm lựa chọn vào lời giải Và đồng thời xây dựng khung thuật giải quay lui tương tự cách xây dựng khung thuật giải chia để trị. T xây dựng lớp kế thừa biểu diễn khung thuật giải quay lui và kế thừa mô tả các hàm ℎ . Các thuật giải cho sử dụng phương pháp quay lui như bài toán quân hậu ( ), bài toán người du lịch ( ) hay bài toán tìm bao lồi của tập điểm ( ) sẽ kế thừa và thi công lại các hàm ℎ này. Hình 2-3 Khung thuật giải quay lui Tính chất 3.2: Độ phức tạp của thuật giải quay lui là ( ) trong trường hợp xấu nhất. Ví dụ 3.2: Để minh họa việc sử dụng khung thuật giải quay lui, ta áp dụng với bài toán 8 Hậu ( ) như sau: 39 · Đặc tả bài toán: Cho bàn cờ 8x8, bài toán đặt ra là tìm các cách đặt 8 quân hậu lên bàn cờ sao không có quân nào có thể ăn được quân nào. · Xây dựng thuật giải: Ta xây dựng lớp kế thừa và cài đặt 5 hàm ℎ của : o (): Hàm này trả về 8 vì cần đặt 8 quân hậu. o (): Hàm này trả về các TRUE vì ta đã đặt được 8 quân hậu vào bàn cờ thỏa điều kiện không quân nào ăn nhau. Trên thực tế, hàm () sẽ là TRUE khi ta đặt được quân cờ thứ 8. o (): Hàm này trả về các vị trí quân hậu mà không bị ăn bởi các quân hậu đã đặt lên trước. o ℎ () : Hàm này gán vị trí đã chọn vào lời giải . o (): Hàm này chỉ đơn giản in lời giải ra màn hình kết quả. · Độ phức tạp thuật toán: Ở cách cài đặt này, do ta đã giới hạn các lựa chọn ở bước thứ i chỉ gồm các vị trí mà không bị các quân từ đặt ở cột 1 đến cột − 1 ăn nên ở bước thứ 2 ta chỉ chọn từ (n-1) ứng viên, bước thứ 3 chọn từ (n-2) ứng viên … Do đó, độ phức tạp chỉ còn ( ) = ! 2.2.3 Khung thuật giải quy hoạch động Quy hoạch động (Richard Bellman, 1953) là phương pháp giải quyết bài toán tổng quát cho các bài toán có những bài toán con chồng nhau và cấu trúc con tối ưu. Quy hoạch động thường dùng một trong hai cách tiếp cận: · Top-down (Từ trên xuống): Bài toán được chia thành các bài toán con, các bài toán con này được giải và lời giải được ghi nhớ để phòng trường hợp cần dùng lại chúng. Đây là đệ quy và lưu trữ được kết hợp với nhau. · Bottom-up (Từ dưới lên): Tất cả các bài toán con có thể cần đến đều được giải trước, sau đó được dùng để xây dựng lời giải cho các bài toán lớn hơn. 40 Cách tiếp cận này hơi tốt hơn về không gian bộ nhớ dùng cho ngăn xếp và số lời gọi hàm. Tuy nhiên, đôi khi việc xác định tất cả các bài toán con cần thiết cho việc giải quyết bài toán cho trước không được trực giác lắm. Trong việc xây dựng khung thuật giải quy hoạch động, chúng tôi sử dụng phương pháp tiếp cận từ dưới lêng xây dựng được thuật giải quy hoạch động tổng quát minh họa trong Bảng 3-5. Bảng 2-5 Thuật giải quy hoạch động tổng quát DynProgSolution solveByDynProg (DynProgProblem p) { // khởi tạo các bài toán và lời giải bộ phận DynProgSolution partSlns[] = strategy.initPartialSolutions(p); while (!strategy.isSolution(problem, partSlns)) { // chọn các bài toán bộ phận để giải int partPbls[] = strategy.getPartialProblems(p, partSlns); // giải bài toán bộ phận DynProgSolution s = strategy.directSolve(p, partPbls, partSlns); // lưu trữ lời giải bộ phận strategy.save(partPbls, partSlns, s); } // trộn các lời giải bộ phận để được lời giải bài toán gốc return strategy.merge(partSlns); } Giải thích chức năng của các hàm hook: initPartialSolutions (): Khởi tạo danh mục bài toán bộ phận getPartialProblems (): Chọn các bài toán bộ phận để giải directSolve (): Giải bài toán bộ phận save (): Lưu trữ lời giải của bài toán bộ phận merge (): Trộn lời giải của tất cả bài toán bộ phận Để xây dựng khung giải thuật quy hoạch động, ta cũng xây dựng lớp kế thừa biểu diễn khung thuật giải quy hoạch động và 41 kế thừa mô tả các hàm ℎ . Các thuật giải cho sử dụng phương pháp quy hoạch động như bài toán nhân ma trận ( ), bài toán sẽ kế thừa và thi công lại các hàm ℎ này. 2.2.4 Khung thuật giải tham lam Thuật giải tham lam là một thuật giải giải quyết một bài toán theo kiểu “metaheuristic” để tìm kiếm lựa chọn tối ưu địa phương ở mỗi bước đi với hy vọng tìm được tối ưu toàn cục. Thuật giải tham lam có năm thành phần: · Một tập hợp các ứng viên (candidate), để từ đó tạo ra lời giải · Một hàm lựa chọn, để theo đó lựa chọn ứng viên tốt nhất để bổ sung vào lời giải · Một hàm khả thi dùng để quyết định nếu một ứng viên có thể được dùng để xây dựng lời giải · Một hàm mục tiêu, ấn định giá trị của lời giải hoặc một lời giải chưa hoàn chỉnh · Một hàm đánh giá, chỉ ra khi nào ta tìm ra một lời giải hoàn chỉnh Có hai thành phần quyết định nhất tới quyết định tham lam: · Tính chất lựa chọn tham lam: Chúng ta có thể lựa chọn giải pháp nào `được cho là tốt nhất ở thời điểm hiện tại và sau đó giải bài toán con nảy sinh từ việc thực hiện lựa chọn vừa rồi. Lựa chọn của thuật giải tham lam có thể phụ thuộc vào các lựa chọn trước đó. Nhưng nó không thể phụ thuộc vào một lựa chọn nào trong tương lai hay phụ thuộc vào lời giải của các bài toán con. Thuật giải tiến triển theo kiểu thực hiện các chọn lựa theo một vòng lặp, cùng lúc đó thu nhỏ bài toán đã cho về một bài toán con nhỏ hơn. Đấy là khác biệt giữa thuật giải này và thuật giải quy hoạch động. Thuật giải quy hoạch động duyệt hết và luôn đảm bảo tìm thấy lời giải. Tại mỗi bước của thuật toán, quy hoạch động đưa ra quyết định dựa trên các quyết định của bước trước, và có thể xét lại đường đi của bước trước hướng tới lời giải. Thuật giải tham lam quyết định sớm và thay 42 đổi đường đi thuật giải theo quyết định đó, và không bao giờ xét lại các quyết định cũ. Đối với một số bài toán, đây có thể là một thuật giải không chính xác. · Cấu trúc con tối ưu: Một bài toán được gọi là "có cấu trúc tối ưu", nếu một lời giải tối ưu của bài toán con chứa lời giải tối ưu của bài toán lớn hơn. Thuật giải tham lam tổng quát được xây dựng ở Bảng 3-6. Bảng 2-6 Thuật giải tham lam tổng quát GreedySolution solveByGreedy(GreedyProblem p) { // khởi tạo danh sách ứng viên List candidates = strategy.initCandidates(); List choices = new LinkedList(); // lặp khi danh sách ứng viên vẫn còn phần tử và các bước lựa // chọn là lời giải bộ phận while (strategy.isPartialSolution(choices) && !candidates.isEmpty()) { // chọn ứng viên theo nguyên tắc tham lam Object option = strategy.greedyChoice(candidates); candidates.remove(option); // thêm ứng viên phù hợp vào danh sách chọn if (strategy.feasible (choices, option)) solution.add(choices); } if (strategy.isSolution(choices)) return GreedySolution.makeSolution(choices); return null; } Giải thích chức năng của các hàm hook: initCandidates (): Khởi tạo danh sách ứng viên isPartialSolution (): Kiểm tra các lựa chọn là lời giải bộ phận? isSolution (): Kiểm tra các lựa chọn là lời giải toàn cục? greedyChoice (): Chọn ứng viên lời giải theo cách tham lam, thường là giá trị lớn nhất theo một phép so sánh cho trước feasible (): Kiểm tra tính phù hợp của một lựa chọn với lời giải 43 Từ thuật giải tổng quát này, tương tự thuật giải chia để trị tổng quát hay thuật giải quay lui tổng quát, ta xây dựng được khung giải thuật tham lam bằng cách thiết lập các lớp cài đặt thuật giải tổng quát và mô tả các hàm nhượng quyền.