Đang chuẩn bị liên kết để tải về tài liệu:
Một số vấn đề về thuật toán part 7

Tham khảo tài liệu 'một số vấn đề về thuật toán part 7', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 5.2. Bài toan nhân ma trận 145 cost l 4 2 2 23 2 2 3 3 1 1 2 2 2 2 3 3 Hình 5.8 lần một sô chu trình con. Do vậy điều kiện tốt cho việc ứng dụng thiết kế theo quy hoạch đông nghĩa là ghi lại các kết quả tính toán trung gian vào một bảng. Ta ghi giá trị cost i j vào mảng m i j . Nghĩà là m í. j chứa số nhỏ nhất những phép nhân của chuỗi ma trận Mị X Mi X X Mj. Giá trị tối ưu để tính đại lượng này được mổ tả như sau Bước cơ SỎ Nếu i j thì dãy ma trận chỉ có một ma trận và vì thế không có phép nhân nào. Như vây 0. Bước thực hiện NỂĨ1 i j thì ta cổ thể tách dãy đã cho thành hai dãy tạịl với í k X Mị X X Afjt X Mu-1 X X Mj . Số những phép nhân nhồnhấttrong Mi xA í 1 X X Mk được ghi vào mịí Ả và số nhưng phép nhân nhổ nhất trong X X Mj được ghi vào m 1 j . Dễ thây rằng cờ ma trận của đoạn thứ nhất là r _i X và cỡ ma trận của đoạn thứ hai là rfXrj và khi nhân hai ma trận kết quả của phân chia tại k phải thực hiện H-í rk Tị phép nhân. Tóm lại tá có 0 m ỉ j min 1 j nếu ì ì ngược lại. Như vậy nhìn vào công thức trên để điền hết bảng ta phải biết những giá trị và n Ẳ 1 j đã được điền vào từ trước. Để tính một ô trong bảng ta tăng các th ồng số có thể nói tính m í ý là đã tính được hàng và cột này từ các ô và m j j như sơ đồ hình 5.9 146 Chương 5. Phương pháp quy hoạch động Hình 5.9 Ví dụ Như ví dụ ban đầu ta có ro 10 n 20 rz 50 r-Ị 1 r4 100. Theo thiết kế trên điền vào bảng như sau Z7ỉ l 2 min w l k m fc 1 2 ror r2 ror r2 10000 m 2 3 r r2ry 1000 m 3 4 r2 r4 5000 hình 5.10 . m l 3 min ní l m Ắ 1 3 ror hình 5.11 min m l 1 w 2 3 ror r3 m l 2 n 3 3 ror2r3 min 0 1000 200 10000 0 500 1200 zn 2 4 min m 2 Ắ m fc 1 4 nr hình 5.12 min w 2 2 n 3 4 rjr2r4 7n 2 3 n 4 4 rir3f4 min 0 5000 100000 1000 0 2000 3000 5.2. Bài toán nhân ma trận 147 tn 1.4 w Ả 1 4 ronM min 7ỉ l 1 m 2 4 r rỵrị w l 2 4- w 3 4 4- r0r2r4 zn l 3 4- m 4 4 4- r0r3r4 -min O 3OOO 20000 10000 5000 50000 1200 0 1000 - 2200 hình 5.13 Hình 5.13 Thuật toán Không khó để chuyển đổi mô tả trên thành thuật toán. Trong quá trình .