intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Thuật toán: Chương 3 - GV. Nguyễn Thanh Cẩm

Chia sẻ: Nguyễn Hà | Ngày: | Loại File: PDF | Số trang:67

Thêm vào BST
Báo xấu
165
lượt xem 31
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương 3 Quy hoạch động thuộc bài giảng thuật toán, cùng nắm kiến thức trong chương này thông qua việc tìm hiểu các nội dung chính sau: thuật toán quy hoạch động tổng quát, một số thí dụ minh họa.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Thuật toán: Chương 3 - GV. Nguyễn Thanh Cẩm

  1. TRƯỜNG CAO ĐẲNG CNTT HỮU NGHỊ ViỆT - HÀN KHOA KHOA HỌC MÁY TÍNH -----------***----------- THUẬT TOÁN (Algorithms) Nguyễn Thanh Cẩm
  2. Nội Dung C1 THUẬT TOÁN VÀ ĐỘ PHỨC TẠP C2 CHIA ĐỂ TRỊ C3 QUY HOẠCH ĐỘNG C4 THUẬT TOÁN THAM LAM C5 THUẬT TOÁN QUAY LUI Nguyễn Thanh Cẩm
  3. QUY HOẠCH ĐỘNG  Chia để trị là thiết kế thuật toán theo kiểu từ trên xuống (top-down)  Quy hoạch động là quá trình tiếp cận thuật toán theo quá trình ngược lại, đó là thiết kế theo kiểu từ dưới lên (bottom-up).  Điểm khác cơ bản của quy hoạch động với phương pháp chia để trị đó là:  các bài toán con không độc lập với nhau,  nghĩa là các bài toán con cùng có chung các bài toán con nhỏ hơn.  Trong tình huống đó, phương pháp chia để trị sẽ tỏ ra không hiệu quả, khi nó phải lặp đi lặp lại việc giải các bài toán con chung đó.  Quy hoạch động sẽ giải một bài toán con một lần và lời giải của các bài toán con sẽ được ghi nhận, nhằm thoát khỏi việc giải lại các bài toán con mỗi khi ta cần lời giải của nó. Nguyễn Thanh Cẩm
  4. QUY HOẠCH ĐỘNG Trong ngành khoa học máy tính, quy hoạch động là một phương pháp giảm thời gian chạy của các thuật toán thể hiện các tính chất của các bài toán con gối nhau (overlapping subproblem) và cấu trúc con tối ưu (optimal substructure). Nhà toán học Richard Bellman đã phát minh phương pháp quy hoạch động vào năm 1953. Nguyễn Thanh Cẩm
  5. QUY HOẠCH ĐỘNG 2.1 Thuật toán quy hoạch động tổng quát 2.2 Một số thí dụ minh họa 2.2.1 Bài toán thực hiện dãy phép nhân ma trận Bài toán tìm đường đi ngắn nhất ­ 2.2.2 thuật toán Floy 2.2.3 Bài toán dãy con lớn nhất 2.2.4 Bài toán dãy con chung dài nhất Nguyễn Thanh Cẩm
  6. 3.1 Thuật toán quy hoạch động tổng quát  Để giải một bài toán bằng quy hoạch động, chúng ta cần tiến hành những công việc sau:  Tìm nghiệm của các bài toán con (các trường hợp riêng) đơn giản nhất.  Tìm ra các công thức (hoặc quy tắc) xây dựng nghiệm của bài toán con thông qua nghiệm của các bài toán con cỡ nhỏ hơn.  Tạo ra một bảng để lưu giữ các nghiệm của các bài toán con. Sau đó tính nghiệm của các bài toán con theo các công thức đã tìm ra và lưu vào bảng.  Từ bảng đã làm đầy, tìm cách xây dựng nghiệm của bài toán đã cho. Nguyễn Thanh Cẩm
  7. 3.1 Thuật toán quy hoạch động tổng quát  Việc phát triển giải thuật dựa trên quy hoạch động có thể chia làm 3 giai đoạn:  Phân rã: Chia bài toán cần giải thành những bài toán con nhỏ hơn có cùng dạng với bài toán ban đầu sao cho bài toán con kích thước nhỏ nhất có thể giải một cách trực tiếp. Bản thân bài toán xuất phát có thể coi là bài toán con có kích thước lớn nhất trong họ các bài toán con này.  Ghi nhận lời giải: Lưu trữ lời giải của các bài toán con vào một bảng. Việc làm này là cần thiết vì lời giải của các bài toán con thường được sử dụng lại rất nhiều lần, và điều đó nâng cao hiệu quả của giải thuật do không phải giải lặp lại cùng một bài toán nhiều lần.  Tổng hợp lời giải: Lần lượt từ lời giải của các bài toán con kích thước nhỏ hơn tìm cách xây dựng lời giải của bài toán kích thước lớn hơn, cho đến khi thu được lời giải của bài toán xuất phát (là bài toán con có kích thước lớn nhất). Nguyễn Thanh Cẩm
  8. 3.1 Thuật toán quy hoạch động tổng quát  Có hai tính chất quan trọng mà một bài toán tối ưu cần phải thoả mãn để có thể áp dụng quy hoạch động để giải nó là:  Cấu trúc con tối ưu: Để giải được bài toán đặt ra một cách tối ưu, mỗi bài toán con cũng phải được giải một cách tối ưu.  Số lượng các bài toán con phải không quá lớn. Rất nhiều các bài toán NP (xem [1] trang 234) – khó có thể giải được nhờ quy hoạch động, nhưng việc làm này là không hiệu quả do số lượng các bài toán con tăng theo hàm mũ. Một đòi hỏi quan trọng đối với quy hoạch động là tổng số các bài toán con cần giải là không quá lớn, cùng lắm phải bị chặn bởi một đa thức của kích thước dữ liệu vào. Nguyễn Thanh Cẩm
  9. QUY HOẠCH ĐỘNG 2.1 Thuật toán quy hoạch động tổng quát 2.2 Một số thí dụ minh họa 2.2.1 Bài toán thực hiện dãy phép nhân ma trận Bài toán tìm đường đi ngắn nhất ­ 2.2.2 thuật toán Floy 2.2.3 Bài toán dãy con lớn nhất 2.2.4 Bài toán dãy con chung dài nhất Nguyễn Thanh Cẩm
  10. 3.2 Một số thí dụ minh họa 3.2.1 Bài toán thực hiện dãy phép nhân ma trận Bài toán tìm đường đi ngắn nhất ­ 3.2.2 thuật toán Floy 3.2.3 Bài toán dãy con lớn nhất 3.2.4 Bài toán dãy con chung dài nhất Nguyễn Thanh Cẩm
  11. 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Tích của ma trận A = (aik) kích thước p x q với ma trận B = (bkj) kích thước q x r là ma trận C = (cij) kích thước p x r với các phần tử của C được tính theo công thức: q cij   aik bkj , k 1 1
  12. 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Chúng ta có thể sử dụng đoạn chương trình sau đây để tính tích của hai ma trận A, B: for (i =1; i
  13. 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Thí dụ: như ma trận ở trên thì:  Phần tử dòng 1 cột 1 của ma trận C được tính như sau:1×7 + 2×2 + 3×6 = 29 nên nó có 3 phép nhân vô hướng.  Phần tử dòng 1 cột 2 được tính: 1×8 + 2×3 + 3×7 = 35 nên cũng có 3 phép nhân vô hướng,…  Suy ra số phép nhân vô hướng (phí tổn) của 2 ma trận A và B là: 2×3×4 = 24 phép nhân. Nguyễn Thanh Cẩm
  14. 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Bây giờ ta xét tích của 4 ma trận A, B, C, D với kích trước lần lượt như sau: A × B × C × D (*) [20×2] [2×30] [30×12] [12×8]  Một điều nên lưu ý là, để thực hiện được tích của các ma trận ở trên, đòi hỏi chúng phải tương thích với nhau. Tức là số cột của A phải đúng bằng số dòng của B, số cột của B phải đúng bằng số dòng của C,… Nguyễn Thanh Cẩm
  15. 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Do phép nhân ma trận không có tính chất giao hoán, nhưng lại có tính chất kết hợp nên tích của 4 ma trận trên có thể được tính bằng nhiều cách như sau:  A(B(CD)) 30×12×8 + 2×30×8 + 20×2×8 = 3.680  (AB)(CD) 20×2×30 + 30×12×8 + 20×30×8 = 8.880  A((BC)D) 2×30×12 + 2×12×8 + 20×2×8 = 1.232  ((AB)C)D 20×2×30 + 20×30×12 + 20×12×8 = 10.320  (A(BC))D 2×30×12 + 20×2×12 + 20×12×8 = 3.120 Nguyễn Thanh Cẩm
  16. 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Từ kết quả trên ta thấy, trình tự thực hiện có ảnh hưởng lớn tới phí tổn để thực hiện dãy phép nhân của các ma trận. Bài toán đặt ra là tính số phí tổn ít nhất có thể được, khi thực hiện dãy phép nhân của n ma trận.  M = M1*M2*…Mn  Với:  M1 là ma trận có kích thước a1×a2  M2 là ma trận có kích thước a2×a3  ….  Mn là ma trận có kích thước an×an+1  Suy ra a[1..n+1] là vector kích thước của các ma trận. Nguyễn Thanh Cẩm
  17. 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Áp dụng phương pháp quy hoạch động chúng ta sẽ giải quyết bài toán theo kiểu “bottom-up”:  Gọi F[i, j] là số phép nhân tối thiểu cần thực hiện để nhân đoạn ma trận liên tiếp: Mi*Mi+1*…*Mj (1
  18. 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Cộng với chi phí thực hiện phép nhân hai ma trận cuối cùng: ma trận tạo thành từ phép nhân Mi*Mi+1*…*Mk có kích thước ai×ak+1, và ma trận tạo thành từ phép nhân Mk+1*…*Mj-1*Mj có kích thước ak+1×aj+1, vậy chi phí này là : ai×ak+1×aj+1.  Từ đó suy ra: do có nhiều cách kết hợp, mà ta cần chọn cách kết hợp để có chi phí ít nhất nên ta sẽ cực tiểu hóa F[i, j] theo công thức:  F[i, j] = min(F[i, k] + F[k+1,j] + ai*ak+1*aj+1) mọi i
  19. 3.2.1 Bài toán thực hiện dãy phép nhân ma trận Tính bảng phương án: Bảng phương án F là bảng hai chiều, nhìn vào công thức (3.1) ta thấy để tính được F[i, j] khi ta đã biết F[i, k] và F[k+1, j] tức là ban đầu ta điền cơ sở quy hoạch động vào đường chéo chính của bảng (F[i, i] = 0) từ đó tính các giá trị thuộc đường chéo nằm phía trên (tính các F[i, i+1]), rồi lại tính các giá trị nằm phía trên nữa (F[i, i+2])… dến khi tính được F[1, n] thì dừng lại. Nguyễn Thanh Cẩm
  20. 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Tìm cách kết hợp tối ưu:  Tại mỗi bước tính F[i, j], ta ghi nhận lại điểm k mà cách tính (Mi*Mi+1*…*Mk)*(Mk+1*…*Mj-1*Mj) cho số phép nhân vô hướng nhỏ nhất, chẳng hạn ta đặt F[i, j] = k. Khi đó muốn in ra phép kết hợp tối ưu để nhân đoạn Mi*Mi+1*…*Mk*Mk+1*…*Mj-1*Mj ta sẽ in ra cách kết hợp tối ưu để nhân đoạn Mi*Mi+1*…*Mk và cách kết hợp tối ưu để nhân đoạn Mk+1*…*Mj- 1*Mj (có kèm theo dấu mở ngoặc) đồng thời viết thêm dấu “*” vào giữa hai biểu thức đó. Nguyễn Thanh Cẩm
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2