tailieunhanh - Introduction to Algorithms Second Edition Instructor’s Manual 2nd phần 10

Chọn bộ lớn nhất có thể không chồng lấn (đôi bên cùng có tương thích) hoạt động. Lưu ý: Có thể có những mục tiêu khác:Giả sử chúng tôi đã kiểm tra (c, e) (e, f). Sau đó sẽ tìm thấy (c, e) an toàn và sẽ bị từ chối (e, f). Phân tích khởi A: Đầu tiên cho vòng lặp: E Sắp xếp: thứ hai cho vòng lặp: | 25-10 Solutions for Chapter 25 All-Pairs Shortest Paths Find-Min-Length-Neg-Weight-Cycle W n rows W L 1 W m 1 while m n and no diagonal entries of L m are negative do L 2m Extend-Shortest-Paths L m L m m 2m if m n and no diagonal entries of L m are negative then return no negative-weight cycles elseif m 2 then return m else low m 2 high m d m 4 while d 1 do s low d L s Extend-Shortest-Paths L low L d if L s has any negative entries on the diagonal then high s else low s d d 2 return high Correctness If after the first while loop m n and no diagonal entries of L m are negative then there is no negative-weight cycle. Otherwise if m 2 then either m 1 or m 2 and L m is the first matrix with a negative entry on the diagonal. Thus the correct value to return is m . If m 2 then we maintain an interval bracketed by the values low and high such that the correct value m is in the range low m high. We use the following loop invariant Loop invariant At the start of each iteration of the while d 1 loop 1. d 2p for some integer p 1 2. d high low 2 3. low m high. Initialization Initially m is an integer power of 2 and m 2. Since d m 4 we have that d is an integer power of 2 and d 1 2 so that d 2p for some integer p 0. We also have high low 2 m m 2 2 m 4 d. Finally L m has a negative entry on the diagonal and L m 2 does not. Since low m 2 and high m we have that low m high. Maintenance We use high low and d to denote variable values in a given iteration and high low and d to denote the same variable values in the next iteration. Thus we wish to show that d 2p for some integer p 1 implies d 2p for some integer p 1 that d high low 2 implies d high low 2 and that low m high implies low m high . Solutions for Chapter 25 All-Pairs Shortest Paths 25-11 To see that d 2p note that d d 2 and so d 2p 1. The condition that d 1 implies that p 0 and so p 1. Within each iteration s is set to low d and one of the following actions occurs If L s has any negative entries on the diagonal then high

• Kỹ thuật lập trình
• thủ thuật hệ điều hành
• tìm hiểu hệ điều hành
• thủ thuật windows
• lập trình windows
• lập trình ứng dụng
• lập trình máy tính
• thủ thuật lập trình
• mẹo hay cho lập trình
• bí quyết lập trình
• thủ thuật máy tính
• phần mềm máy tính
• quản trị hệ thống
• hệ điều hành linux
• hệ điều hành mac
• mẹo cài hệ điều hành
• hệ điều hành unix
• hệ điều hành windows
• kỹ năng máy tính
• Hệ Điều Hành
• các hệ điều hành Windows
• giáo trình hệ điều hành
• các vấn đề hệ điều hành
• tài liệu hệ điều hành
• Tổng quan về hệ điều hành
• windows 7
• Refresh hệ điều hành Android
• Hệ điều hành Android cũ
• Hệ điều hành Android
• Cài đặt hệ điều hành Android
• Thủ thuật hệ điều hành Android
• Khôi phục hệ điều hành Android
• đồ họa máy tính
• mỹ thuật đa truyền thông
• học hệ điều hành
• cách sử dụng hệ điều hành
• hệ điều hành windows 7
• mẹo hay hệ điều hành