Áp dụng các mẫu thiết kế hướng đối tượng trong việc thiết lập các thuật toán tổ hợp

Trang nhan đề Lời cảm ơn Mục lục Danh mục bảng biểu Danh sách hình vẽ Chương_1: Tổng quan Chương_2: Xây dựng khung thuật giải Chương_3: Thiết lập một số thuật giải sắp xếp Chương_4: Thiết lập một số thuật giải tìm kiếm Chương_5: Thiết lập một số thuật giải tìm kiếm trên đồ thị Chương_6: Kết luận Tài liệu tham khảo Mục lục Danh mục các bảng biểu . . . 6 Danh mục các hình vẽ . . . 8 Chương 1 Tổng quan . . . 10 1.1 Giới thiệu . . . 10 1.2 Một số khái niệm và nghiên cứu liên quan . 11 1.2.1 Một số khái niệm . . 11 1.2.1.1 Lập trình tổng quát . . . 11 1.2.1.2 Mẫu thiết kế hướng đối tượng . . . 13 1.2.1.3 Khung thuật giải . . . 18 1.2.2 Một số công trình nghiên cứu liên quan . 19 1.2.2.1 Một số nghiên cứu về tổng quát hóa dữ liệu 19 1.2.2.2 Một số nghiên cứu về tổng quát hóa thuật giải 22 1.2.2.3 Một số nhận xét . . 25 1.3 Phạm vi nghiên cứu . . . 27 1.4 Ý nghĩa khoa học của luận văn . . 27 1.5 Nội dung của luận văn . . . 28 Chương 2 Xây dựng khung thuật giải . . 30 2.1 Xây dựng khung thuật giải tổng quát . . . 30 2.2 Một số khung thuật giải cụ thể . 32 2.2.1 Khung thuật giải chia để trị . . . 32 2.2.2 Khung thuật giải quay lui . . 36 2.2.3 Khung thuật giải quy hoạch động . . 39 4 2.2.4 Khung thuật giải tham lam . . 41 Chương 3 Thiết lập một số thuật giải sắp xếp . . 44 3.1 Họ thuật giải sắp xếp . . . 44 3.2 Thuật giải sắp xếp và phương pháp chia để trị . 45 3.3 Thuật giải sắp xếp tổng quát . . 47 3.3.1 Xây dựng khung thuật giải sắp xếp . . 47 3.3.2 Các thuật giải sắp xếp cụ thể . . . 49 3.4 Một khung thuật giải sắp xếp phân cấp hơn . 51 Chương 4 Thiết lập một số thuật giải tìm kiếm . . 53 4.1 Họ thuật giải tìm kiếm . . . 53 4.2 Xây dựng thuật giải tìm kiếm tổng quát . 56 4.3 Các thuật giải tìm kiếm cụ thể . . 59 4.3.1 Thuật giải tìm kiếm ưu tiên chiều sâu . . 59 4.3.2 Thuật giải tìm kiếm ưu tiên chiều rộng . . 60 4.3.3 Thuật giải tìm kiếm ưu tiên lựa chọn tốt nhất 61 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 61 4.3.3.2 Thuật giải A* . . 63 4.3.4 Thuật giải tìm kiếm cục bộ . . 63 4.3.4.1 Thuật giải tìm kiếm cục bộ tổng quát 63 4.3.4.2 Thuật giải leo đồi . . 64 4.4 Tổng kết . . . . 66 Chương 5 Thiết lập một số thuật giải tìm kiếm trên đồ thị 67 5.1 Đồ thị và bài toán tìm kiếm trên đồ thị . 67 5.2 Thuật giải tìm kiếm trên đồ thị tổng quát . 68 5 5.3 Các thuật giải tìm kiếm đồ thị cụ thể . . 71 5.3.1 Thuật giải tìm kiếm ưu tiên chiều sâu . . 71 5.3.2 Thuật giải tìm kiếm ưu tiên chiều rộng . . 72 5.3.3 Thuật giải tìm đường đi ngắn nhất Dijkstra . 72 5.3.4 Thuật giải tìm cây khung ngắn nhất Prim . . 73 5.4 Kết luận . . . . . 73 Chương 6 Kết luận . . 74 6.1 Kết quả đạt được . . 74 6.2 Hạn chế và hướng Phát triển . . 75 Tài liệu tham khảo . . . . 76

pdf9 trang | Chia sẻ: lvcdongnoi | Ngày: 20/08/2013 | Lượt xem: 1589 | Lượt tải: 1download
Bạn đang xem nội dung tài liệu Áp dụng các mẫu thiết kế hướng đối tượng trong việc thiết lập các thuật toán tổ hợp, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
44 Chương 3 Thiết lập một số thuật giải sắp xếp Chương 3 của luận văn trình bày về việc thiết lập một số thuật giải sắp xếp cơ bản. Việc thiết lập này dựa trên tư tưởng đưa các thuật giải sắp xếp về dạng chia để trị của Merritt [20] và vận dụng khung thuật giải chia để trị đã trình bày ở chương 2 để tổng quát hóa. Đồng thời mục 3.4 của luận văn cũng đề xuất một cách phân loại cải tiến, phân cấp hơn phân loại của Dzung&Wong [8]. 3.1 Họ thuật giải sắp xếp Các thuật giải sắp xếp là một trong những thuật giải cơ bản được nghiên cứu từ rất lâu đối với ngành Khoa học máy tính. Trong các giáo trình cấu trúc dữ liệu truyền thống (Knuth-1973), các thuật giải này được xếp thành 3 nhóm dựa vào quá trình thao tác trên các phần tử: đổi chổ, chọn hoặc chèn mà các thuật giải đại diện là ℎ , và . Trong đó, các thuật giải phức tạp hơn như ℎ , và được biểu diễn như là sự tối ưu hóa từ các thuật giải cơ bản trên. Riêng thì được xem như sự phân loại thứ tư. 45 Năm 1985, Merritt đã trình bày một phương pháp phân loại mới cho các thuật giải sắp xếp [20] được gọi là “phân loại nghịch”. Trong đó các thuật giải sắp xếp được chia thành hai nhóm: dễ tách / khó ghép và khó tách / dễ ghép. Đại diện chính của nhóm dễ tách / khó ghép là thuật giải sắp xếp trộn ( ), còn đại diện chính của nhóm khó tách / dễ ghép là thuật giải sắp xếp nhanh ( ). Các thuật giải , được xem như các biến thể của còn các thuật giải , sẽ thuộc nhánh (xem Hình 3-1). Sự “khó” hay “dễ” ở đây biểu thị việc hoàn thành giai đoạn sắp xếp của các thuật giải. Nhóm thuật giải “khó ghép” hoàn thành việc sắp xếp ở giai đoạn ghép còn nhóm thuật giải “khó tách” thì hoàn thành việc sắp xếp ở giai đoạn tách. Hình 3-1 Phân loại các thuật giải sắp xếp Phương pháp phân loại này hiện nay đang được chấp nhận một cách rộng rãi, nhất là khi các tác giả Dzung và Wong cài đặt chúng theo mô hình cài đặt hướng đối tượng [8]. Các mục còn lại của chương 3 cũng dựa trên phương pháp phân loại này và cung cấp một giải pháp tổng quát hóa tương đối đầy đầy đủ và phân cấp hơn. 3.2 Thuật giải sắp xếp và phương pháp chia để trị Nhắc lại, việc tổng quát hóa các thuật giải sắp xếp dựa trên nhận xét rằng chúng có thể biểu diễn dưới dạng thuật giải chia để trị như hay . Khi đó, một thuật giải sắp xếp sẽ là lặp liên tục hai thủ tục sau: “tách” danh sách thành 46 hai danh sách con và “ghép” hai danh sách con này lại. Sự khác nhau trong việc “tách” và “ghép” sẽ tạo ra được những thuật giải sắp xếp khác nhau. Hình 3-2 Minh họa sự hoạt động của MergeSort và QuickSort Ví dụ ở thuật giải , việc sắp xếp hoàn tất ở thủ tục ghép hai danh sách con đã được sắp xếp còn thủ tục tách chỉ đơn giản là chia đôi danh sách làm hai phần. Trong khi đó, ở thuật giải , việc sắp xếp hoàn tất ở thủ tục tách hai danh sách con còn thủ tục ghép chỉ đơn giản nối hai danh sách con đã sắp xếp. Minh họa việc thực hiện hai thuật giải này ở Hình 3-2. Các thuật giải sắp xếp còn lại cũng có thể được xây dựng lại dựa vào việc thay đổi hai thủ tục này: sẽ tách danh sách thành hai phần với danh sách bên trái gồm 1 phần tử và là phần tử nhỏ nhất; cũng thực hiện tương tự nhưng khác ở cách đưa phần tử nhỏ nhất vào danh sách con bên trái; là một trường hợp của với tỉ lệ chia là (1, − 1)… Nhờ những nhận xét trên, ta hoàn toàn có thể xây dựng một thuật giải sắp xếp tổng quát và hơn nữa việc này sẽ dựa trên khung thuật giải chia để trị tổng quát. Thủ tục “tách” sẽ là thủ tục () và thủ tục “ghép” sẽ là thủ tục () của khung thuật giải chia để trị. Do đó, ta có thể xây dựng lớp kế thừa từ sẽ đại diện cho tất cả các thuật giải sắp xếp. Trong đó, các hook 47 () và () đã được cài đặt sẵn còn () và () sẽ được thi công ở các lớp thuật giải con cụ thể. Hình 3-3 thể hiện sự thừa kế giữa và các lớp thuật giải sắp xếp. Việc xây dựng thuật giải tổng quát này sẽ được trình bày trong mục 3.3 tiếp theo. Hình 3-3 Thuật giải sắp xếp tổng quát 3.3 Thuật giải sắp xếp tổng quát 3.3.1 Xây dựng khung thuật giải sắp xếp Đầu tiên trong việc xây dựng khung thuật giải cho các thuật giải sắp xếp là đặc tả lại bài toán. Không mất tính tổng quát khi chúng ta chỉ xét bài toán sắp xếp trên mảng được cài đặt bởi mảng một chiều. Do đó, đầu vào của bài toán là một danh sách các phần tử có thể so sánh được bởi một toán tử so sánh. Kết quả của bài toán là danh sách đó đã được sắp xếp lại theo thứ tự. Ta nhận thấy cấu trúc dữ liệu tương tự của đầu bài và kết quả, nên có thể sử dụng chung một lớp đối tượng để cùng mô tả cả hai. Bảng 3-1 Đặc tả bài toán sắp xếp public class ArraySortDesc implements DivConqProblem, DivConqSolution { 48 public ArraySortDesc(Object[] A, int lo, int hi, Comparator comp) { this.A = A; this.lo = lo; this.hi = hi; this.comp = comp; } protected int lo, hi; protected Object[] A; protected Comparator comp; } Tiếp theo, ta xây dựng lớp biểu diễn thuật giải sắp xếp tổng quát kế thừa từ thuật giải chia để trị. Lớp sẽ thi công hai hàm hook () và (). Hai hàm hook còn lại () và () sẽ nhượng quyền cho các lớp con là các thuật giải sắp xếp cụ thể. Bảng 3-2 Thuật giải sắp xếp tổng quát public class AbtractSort implements DivConqStrategy { @Override public final boolean isSimple(Problem problem) { ArraySortDesc p = (ArraySortDesc)problem; return p.lo >= p.hi; } @Override public Solution simplySolve(Problem problem) { return (Solution)problem; } @Override public final Problem[] divide(Problem problem) { ArraySortDesc p = (ArraySortDesc)problem; int mid = divide(p); return new ArraySortDesc[] { new ArraySortDesc(p.A, p.lo, mid, p.comparator), new ArraySortDesc(p.A, mid+1, p.hi, p.comparator) }; } @Override public final Solution combine(Problem p, Solution[] ss) { return combine((ArraySortDesc)p); 49 } public abstract int divide(ArraySortDesc p); public abstract ArraySortDesc combine(ArraySortDesc p); } isSimple(): Bài toán sắp xếp được gọi là đơn giản khi dãy cần xếp chỉ có một phần tử. simplySolve(): Lời giải của bài toán trong trường hợp đơn giản chỉ gồm một phần tử cũng chính là dãy đó. Do cách tổ chức dữ liệu, ta đặt lớp ArraySortDesc mô tả cả Problem và Solution nên hàm này chỉ cần ép kiểu từ Problem sang Solution và trả về kết quả. 3.3.2 Các thuật giải sắp xếp cụ thể Từ khung thuật giải sắp xếp trên, khi cài đặt một thuật giải sắp xếp cụ thể, ta sẽ tạo một lớp kế thừa từ và thi công hai hàm () và (). Bảng 3-3 và bảng 3-4 dưới đây là minh họa thuật giải sắp xếp chèn và thuật giải sắp xếp chọn kế thừa từ thuật giải sắp xếp tổng quát. Bảng 3-3 Thuật giải sắp xếp chèn public class InsertionSort extends AbstractSort { @Override public ArraySortDesc combine(ArraySortDesc p) { int j = p.hi; Object key = p.A[p.hi]; while (p.lo < j && p.comparator.isLessThan(key, p.A[j-1])){ p.A[j] = p.A[j-1]; p.A[j-1] = key; j = j - 1; } return p; } @Override public int divide(ArraySortDesc p) { return p.hi - 1; } } 50 Bảng 3-4 Thuật giải sắp xếp chọn public class SelectionSort extends AbstractSort { @Override public ArraySortDesc combine(ArraySortDesc p) { return p; } @Override public int divide(ArraySortDesc p) { int s = p.lo; for (int i = p.lo+1; i <= p.hi; i++) { if (p.comparator.isLessThan(p.A[i], p.A[s])) s = i; } Object min = p.A[s]; p.A[s] = p.A[p.lo]; p.A[p.lo] = min; return p.lo; } } Và từ đó, các thuật giải sắp xếp còn lại hoàn toàn có thể được cấu trúc lại theo phương pháp này. Thuật giải () () Merge Sort Trả về (lo+hi)/2 Trộn 2 danh sách con Insertion Sort Trả về hi Chèn A[hi] vào đúng vị trí Quick Sort Chia hai danh sách con bên trái nhỏ hơn và bên phải lớn hơn phần tử cầm canh, trả về vị trí cầm canh Không thực hiện gì Selection Sort Đổi chổ phần tử lớn nhất và A[hi], trả về hi Không thực hiện gì Bubble Sort Nổi bọt phần tử lớn nhất về A[hi], trả về hi Không thực hiện gì Heap Sort Đổi chổ A[lo] và A[hi], trả về hi Không thực hiện gì Radix Sort Chia hai danh sách con dựa vào số bit từ trái sang, trả về vị trí chia Không thực hiện gì Distribution Sort Chia hai danh sách con dựa vào số bit từ phải sang, trả về vị trí chia Trộn hai danh sách con Hình 3-4 Các thuật giải sắp xếp cụ thể 51 3.4 Một khung thuật giải sắp xếp phân cấp hơn Mục 3.3 đã cho ta được một khung thuật giải sắp xếp tổng quát mà từ đó các thuật giải khác có thể thừa kế được chiến thuật chia để trị từ lớp cơ sở và chỉ cài đặt lại hai thủ tục “tách” và “ghép”. Tuy nhiên, sự phân cấp này tương đối phẳng, ta không thấy được sự liên hệ giữa các thuật giải sắp xếp với nhau ví dụ như và mặc dù hai thuật giải này có sự tương đồng về mặt giải pháp. Do đó, ta cần đưa ra một mô hình tổng quát hóa các thuật giải sắp xếp phân cấp hơn, trong đó những thuật giải nào có sự tương đồng về giải pháp sẽ được kế thừa từ một thuật giải tổng quát “trung gian”. Những thuật giải tổng quát “trung gian” này cũng được kế thừa từ thuật giải sắp xếp tổng quát. Trước tiên, ta có một số nhận xét như sau: · , và : là những thuật giải sắp xếp chia danh sách cần sắp thành hai danh sách con dựa vào việc so sánh giá trị các phần tử và luôn đảm bảo rành buộc: các phần tử của danh sách con bên trái luôn nhỏ hơn các phần tử của danh sách con bên phải. Cụ thể hơn, các thuật giải này sẽ lần lượt đổi chổ các phần tử làm ảnh hưởng đến ràng buột trên. dựa vào phần tử cầm canh để chia danh sách sao cho danh sách bên trái nhỏ hơn và danh sách bên phải lớn hơn phần tử cầm canh. Trong trường hợp danh sách con chỉ gồm một phần tử thì sẽ biến thể thành . Còn là một phiên bản “in-place” của . Do vậy, ta có thể gom chung 3 thuật giải này vào một nhóm gọi là nhóm thuật giải sắp xếp bằng cách chia danh sách theo giá trị. · và : dễ dàng nhận thấy điểm chung của hai thuật giải này là trộn hai danh sách con đã được sắp, sự khác nhau chủ yếu là vị trí phân chia khi tách danh sách thành hai danh sách con. chia theo tỉ lệ ( , ) còn chia theo tỉ lệ (1, − 1). Do vậy, ta 52 có thể gom chung 2 thuật giải này vào một nhóm gọi là nhóm thuật giải sắp xếp bằng cách chia sách theo vị trí. · và : về mặt bản chất rõ ràng hai thuật giải này dựa trên giá trị bộ phận của phần tử nên ta gom chung vào nhóm thuật giải sắp xếp theo giá trị bộ phận. Như vậy, các thuật giải sắp xếp sẽ được phân thành 3 nhóm: sắp xếp bằng cách chia danh sách theo vị trí, sắp xếp bằng cách chia danh sách theo giá trị và sắp xếp bằng cách chia danh sách theo giá trị bộ phận theo mô hình ở Hình 3-5. Hình 3-5 Phân loại các thuật giải sắp xếp theo logic

Các file đính kèm theo tài liệu này:

  • pdf8.pdf
  • pdf1.pdf
  • pdf10.pdf
  • pdf11.pdf
  • pdf12.pdf
  • pdf2.pdf
  • pdf3.pdf
  • pdf4.pdf
  • pdf5.pdf
  • pdf6.pdf
  • pdf7.pdf
  • pdf9.pdf
Luận văn liên quan