TAILIEUCHUNG - ASP.NET 2.0 - PART 6

Đây là giáo trình kỹ thuật lập trình bằng tiếng Anh dành cho giáo viên, sinh viên chuyên ngành công nghệ thông tin tham khảo. | Chapter 11 Dynamic Programming 124 We can fully parenthesized them in two ways 1. A1 A2 A3 100 x 5 x 50 10 100 50 75000 2. A1 A2 A3 10 x 100 x 5 10 x 5 x 50 7500 10 times better See how the cost of multiplying these 3 matrices differ significantly. The cost truly depend on the choice of the fully parenthesization of the matrices. However exhaustively checking all possible parenthesizations take exponential time. Now let s see how MCM problem can be solved using DP. Step 1 characterize the optimal sub-structure of this problem. Let i j denote the result of multiplying AiAi . can be obtained by splitting it into and Ak and then multiplying the subproducts. There are j-i possible splits . k i . j-1 Within the optimal parenthesization of a the parenthesization of must be optimal b the parenthesization of Ak must be optimal Because if they are not optimal then there exist other split which is better and we should choose that split and not this split. Step 2 Recursive formulation Need to find A1 n Let m i j minimum number of scalar multiplications needed to compute Since can be obtained by breaking it into Ak we have m i j 0 if i j min i k j m i k m k 1 j pi-1pkpj if i j let s i j be the value k where the optimal split occurs. Step 3 Computing the Optimal Costs Matric-Chain-Order p n length p -1 Chapter 11 Dynamic Programming 125 for i 1 to n do m i i 0 for l 2 to n do for i 1 to n-l 1 do j i l-1 m i j infinity for k i to j-1 do q m i k m k 1 j pi-1 pk pj if q m i j then m i j q s i j k return m and s Step 4 Constructing an Optimal Solution Print-MCM s i j if i j then print Ai else print Print-MCM s 1 s i j Print-MCM s s i j 1 j Note As any other dp solution MCM also can be solved using Top Down recursive algorithm using memoization. Sometimes if you cannot visualize the Bottom Up approach just modify your original Top Down recursive solution by including memoization. You ll save a lot of time by avoiding .

TỪ KHÓA LIÊN QUAN
TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.