Giáo trình Cấu trúc dữ liệu và Giải thuật - Chương 9+10

(1959)Với đồ thị vô hướng G, với mọi đỉnh k xét theo thứ tự từ 1 đến n, với tất cả các cặp đỉnh (u,v) nếu có tồn tại cạnh nối (u,k) và cạnh nối (k,v) thì ta tự nối thêm cạnh (u,v) nếu chưa có.CHƯƠNG X: CÁC KỸ THUẬT THIẾT KẾ THUẬT TOÁN1. Phương pháp duyệt2. Phương pháp ăn tham3. Chia để trị và đệ quy4. Quy hoạch độngCHƯƠNG X: CÁC KỸ THUẬT THIẾT KẾ THUẬT TOÁN1. Phương pháp duyệta) Duyệt tuyến tính	Tư tưởng chính của duyệt tuyến tính là “vét cạn” một cách có hệ thống tất cả các khả năng có thể xẩy ra. Duyệt toàn bộPhương pháp rất cơ bản, thường dùng trong cuộc sống hàng ngày.Cho phép tìm ra một nghiệm hoặc tất cả các nghiệm ( nếu có). Ví dụ thuật toán tìm kiếm tuần tự ta đã sử dụng duyệt lần lượt từ số hạng thứ nhất cho đến số hạng sau cùng.b) Phương pháp mắt lưới Ví dụ: cho phương trình y=f(x) liên tục trong đoạn [a,b], cần tìm x trong đoan [a,b] sao cho f(x)=0. Cách giải: Chia đoạn [a,b] thành n đoạn bằng nhau có kích thước epx đủ nhỏ để f(x)=0 với mọi x mà |x-x0| cj và các ô ( i, ci) và (j,cj) không nằm trên cùng một đường chéo.Các giá trị có thể tạo thành nghiệm thành phần tạo thành tập khả năng ( ví dụ tập {1,2,..8})Tám con hậu Đây là một bài toán cổ điển có từ thế kĩ 18 mà các nhà toán học rất quan tâm cả hai khía cạnh: chỉ ra một cách xếp các con hậu và có bao nhiêu cách xếp hậu khác nhau.Tám con HậuGiả sử đã chọn được c1,c2,,ci-1Từ điều kiện của bài toán ta chọn các khả năng cho ci. Phạm vi chọn các khả năng phụ thuộc vào c1,c2,,ci-1 đã chọn trước đó.Nghiệm thành phần cần “thư-̉ sai” để mở rộng, lặp lại quá trình đó cho đến khi xây dựng xong nghiệm.Tám con hậuNếu không chọn được khả năng cho ci ( đã thử hết với tất cả các khả năng nhưng vẫn không thành công thì phải “ quay lui” xây dựng lại ci-1 bằng cách “thử-sai với các khả năng còn lại. Nếu tất cả các khả năng của ci-1 đã thử hết mà không chọn được ci thì phải xây dựng lại ci-2 ...Quá trình trên được lặp lại cho đến khi hoặc xây dựng đủ n nghiệm thành phần hoặc bài toán trên thực tế không có nghiệm.Tám con hậux x xxxxxxc1 c2 c3 c4 c5 c6 c7 c8 Nhận xét Thực chất là ta đã chia bài toán thành các bài toán thành phần và mô tả dưới dạng đệ quy.Do sự bùng nổ các phép toán (dạng cây) nên tùy điều kiện bài toán thường phải tìm cách phát hiện các điều có thể biết trước mà không cần thử sai để giảm bớt sự bùng nỗ phép toán. Nhận xétVí dụ, ở mỗi hàng có thể xem đều có 8 khả năng để đặt hậu. Tuy nhiên ở mỗi hàng, không cần thiết phải đặt hậu ở các cột mà tại đó đã có con hậu trên hàng nào đó trước đó. Do vậy, khi xét hàng i thì chỉ có (8-i+1) khả năng có thể lựa chọn để thử –sai mà thôi.Nhận xétNếu yêu cầu chỉ cần tìm ra một nghiệm của bài toán thì không nhất thiết phải “ duyệt toàn bộ” các khả năng. Việc làm đó chỉ xẩy ra khi đòi hỏi phải đưa ra tất cả các nghiệm hoặc khi để khẳng định bài toán không có nghiệmCHƯƠNG X: CÁC KỸ THUẬT THIẾT KẾ THUẬT TOÁN2. Phương pháp tham ănThường dùng để giải các bài toán tối ưu theo nghĩa tốt nhất có thể được mà do kích thước dữ liệu quá lớn không giải quyết bằng phương pháp duyệt toàn bộ được.Độ phức tạp của nhiều bài toán tối ưu nói chung là hàm mũ. Yêu cầu tối ưu đôi khi không phải là ưu tiên bắt buộc mà yêu cầu chỉ cần có nghiệm gần tối ưu chấp nhận được.Ăn thamVí dụ, cần chọn B tập con của tập A mà các phần tử tập B thỏa mãn một số tính chất nào đó. Tập con B như vậy được gọi là nghiệm chấp nhận được. Gắn với các nghiệm chấp nhận là một hàm mục tiêu. Nghiệm tối ưu là nghiệm chấp nhận có giá trị hàm mục tiêu tốt nhất. Ăn thamXây dựng tập B bằng kiến thiết, khởi tạo B là một tập rỗng. Tại mỗi bước, chọn một phần tử “hợp lí nhất” của tập A để kết nạp vào tập B và loại phần tử đó ra khỏi tập A. Lựa chọn dựa trên tiêu chí cho trước. Việc mở rộng B sẽ kết thúc khi thêm một phần tử mới vào B thì nó không còn thỏa mãn tiêu chí nữa.Ăn thamCó hai vấn đề giải quyết:Xây dựng cách chọn theo kiễu ăn tham.Xây dựng cấu trúc tối ưuCHƯƠNG X: CÁC KỸ THUẬT THIẾT KẾ THUẬT TOÁN2. Phương pháp tham ănBài toán xử lí công việcCho CV={1,2,N}. là tập N công việc cần sử dụng tài nguyên, mà tại mỗi thời điểm chỉ phục vụ cho một công việc. Giả thiết, công việc i có thời gian bắt đầu si và kết thúc là fi và thỏa mãn si fj hoặc sj>=fj.Yêu cầu là chọn công việc đưa vào sử dụng sao cho càng nhiều công việc càng tốt. Không mất tính tổng quát ta giả thiết f1 N đưa ra CV và kết thúc;Bước 4. i:=i+1;Bước 5. Nếu si >= fj thì { CV:= CV+[i]; j:=i}Bước 6. Quay lại bước 3.CHƯƠNG X: CÁC KỸ THUẬT THIẾT KẾ THUẬT TOÁN2. Phương pháp tham ănBài toán xử lí công việcisifi012345678910111213141*14 xxx           235               306               4*57     xx        538               659               7610               8*811        xxx    9812               10212               11*1214             xx2. Phương pháp tham ănNhận xétNghiệm của bài toán nói chung không cho nghiệm tối ưu toàn cục. Tuy nhiên cũng không ít trường hợp nó cho nghiệm tối ưu.Một số trường hợp người ta tìm cách xây dựng lựa chọn ăn tham khác nhau. Với mỗi cách cho một nghiệm tối ưu gần đúng. Trong số các nghiệm tìm được đó chọn nghiệm tốt nhất.3. Chia để trị và đệ quyGiới thiệu	Có thể hiểu chiến lược Chia-Để- Trị một cách đại thể như sau: Chia: Chia bài toán xuất phát, phức tạp, có kích thước Input lớn thành các bài toán con tương tự nhưng có kích thước Input nhỏ hơn. Chia-Để- TrịTrị: Giải các bài toán con bằng đệ quy. Các bước Chia- Trị được lặp lại cho đến khi bài toán con hoặc là có lời giải hiển nhiên hoặc dẽ dàng nhận đươc lời giải.Kết hợp nghiệm (combaine): Nghiệm các bài toán con được kết hợp để cho nghiệm bài toán con lớn hơn và cuối cùng cho nghiệm của bài toán xuất phát. 3. Chia để trị và đệ quyNhận xétSử dụng công cụ đệ quy:rất chặt chẽ, dễ cài đặtThường đòi hỏi khối lượng tính toán rất lớn. Quá trình thực hiện Chia- Để trị diễn ra theo hai bước:Chia-Để- TrịBước chia để trị là đi “ từ trên xuống”( Top-Down) để xác định lời gọi đệ quy.Bước kết hợp nghiệm thì đi từ dưới lên ( Bottom-up), tại bước này thực hiện các tính toán và kết hợp nghiệm cho bài toán lớn hơn. Do nghiệm các bài toán con không được lưu trữ nên các bước sau, khi cần sử dụng thì phải tính lại. CHƯƠNG X: CÁC KỸ THUẬT THIẾT KẾ THUẬT TOÁN4. Quy hoạch độnga) Định nghĩaPhương pháp quy hoạch động thường dùng để giải các bài toán tối ưu có bản chất đệ quyTrong QHĐ khi không biết phải giải bài toán con nào ta sẽ giải tất cả các bài toán con và lưu trữ lại tất cả các nghiệm của các bài toán con này và khi gặp lại thì không cần phải giải lại mà chỉ cần sử dụng các nghiệm đã được lưu trữ. Quy hoạch độngBài toán có thõa mãn các yêu cầu:Bài toán phải phân rã thành nhiều bài toán con mà sự kết hợp lời giải các bài toán con đó phải cho lời giải của bài toán lớn.QHĐ cần có bộ nhớ để lưu trữ nên phải xem ta có đủ tài nguyên hay không.Quá trình từ bài toán cơ sở tìm ra lời giải bài toán xuất phát phải qua hữu hạn bước. 4. Quy hoạch độngb) Thuật ngữCông thức kết hợp nghiệm các bài toán con để có nghiệm của bài toán lớn hơn gọi là công thức truy hồi của QHĐ.Tập các bài toán nhỏ nhất có lời giải hiển nhiên để từ đó giải các bài toán lớn hơn gọi là cơ sở của QHĐ.Không gian dùng để lưu trữ nghiệm các bài toán con dùng đề tính nghiệm bài toán lớn hơn gọi là bảng phương án của QHĐ.4. Quy hoạch độngc) Thuật toán QHĐ Bước 1: Lưu nghiệm của các bài toán cơ sở vào các vị trí tương ứng trong bảng phương án.Bước 2: Dùng công thức truy hồi, dựa vào nghiệm các bài toán con đã lưu trong bảng phương án để tính nghiệm bài toán lớn hơn và lưu kết quả vào vị trí tương ứng trong bảng phương án. Tiếp tục quá trình đó cho đến khi bảng phương án được tính xong hoàn toàn.Bước 3: Dựa vào bảng phương án, truy vết để tìm ra nghiệm tối ưu.Ví dụd) Một số ví dụDãy con đơn điệu tăng dài nhấtCho A là dãy số nguyên a1,a2,.an. Một dãy con của A là một cách chọn trong A một số phần tử giữ nguyên thứ tự.Nhận xét . Số lượng dãy con là 2n.Yêu cầu. Tìm dãy con đơn điệu tăng của A có độ dài lớn nhất.Kết luận: Độ dài xâu con dài nhất là 7 và bao gồm các phần tử thứ 2,3,4,7,8,9,10 nghĩa là dãy con 2,3,4,5,6,7,8Ví dụTa sẽ giải bài toán này bằng QHĐ.- Bổ sung vào dãy 02 phần tử là a[0]= -∞ và a[n+1]=+ ∞- Khi đó dãy con dài nhất chắc chắn bắt đầu từ a[0] và kết thúc tại a[n+1]- Với mọi I 0a[i] và phải chọn dãy con dài nhất.L[i] được tính: Xét tất cả chỉ số j trong khoảng từ i+1 đến n+1 mà a[j] >a[i] , chọn ra chỉ số jmax có L[jmax] dài nhất Đặt L[i] = L[jmax] +1QHĐ(iV) Truy vết -Mỗi lần khi gán L[i] = L[jmax] +1ta đặt T[i] =jmax để chỉ rằng dãy con dài nhất bắt đầu từ a[i] có phần tử thứ 2 là a[jmax].- Sau khi tính xong bảng phương án L và bảng ghi vết T, dãy sẽ bắt đầu từ T[0] – là phần tử đầu tiên được chọn.T[T[0]] là phần tử thứ 2,.Ví dụI01234567891011A[i]- ∞52349105678+∞L[i]958763254321T[i]283*4*7*6118*9*10*11