TAILIEUCHUNG - BÀI GIẢNG GIẢI THUẬT VÀ LẬP TRÌNH - QUY HOẠCH ĐỘNG - LÊ MINH HOÀNG - 7

Bài tập Bài 1 Phương pháp cài đặt như trên có thể nói là rất hay và hiệu quả, đòi hỏi ta phải hiểu rõ bản chất thuật toán, nếu không thì rất dễ nhầm. Trên thực tế, còn có một phương pháp khác dễ hiểu hơn, tuy tính hiệu quả có kém hơn một chút. Hãy viết chương trình mô tả phương pháp sau: Vẫn dùng thuật toán tìm kiếm theo chiều sâu với thủ tục Visit nói ở đầu mục, đánh số lại các đỉnh từ 1 tới n theo thứ tự duyệt xong, sau đó đảo chiều. | Các thuật toán trên đồ thị 203 Init Solve Close fo end. Bài tập Bài 1 Phương pháp cài đặt như trên có thể nói là rất hay và hiệu quả đòi hỏi ta phải hiểu rõ bản chất thuật toán nếu không thì rất dễ nhầm. Trên thực tế còn có một phương pháp khác dễ hiểu hơn tuy tính hiệu quả có kém hơn một chút. Hãy viết chương trình mô tả phương pháp sau vẫn dùng thuật toán tìm kiếm theo chiều sâu với thủ tục Visit nói ở đầu mục đánh số lại các đỉnh từ 1 tới n theo thứ tự duyệt xong sau đó đảo chiều tất cả các cung của đồ thị. Xét lần lượt các đỉnh theo thứ tự từ đỉnh duyệt xong sau cùng tới đỉnh duyệt xong đầu tiên với mỗi đỉnh đó ta lại dùng thuật toán tìm kiếm trên đồ thị BFS hay DFS liệt kê những đỉnh nào đến được từ đỉnh đang xét đó chính là một thành phần liên thông mạnh. Lưu ý là khi liệt kê xong thành phần nào ta loại ngay các đỉnh của thành phần đó khỏi đồ thị. Tính đúng đắn của phương pháp có thể hình dung không mấy khó khăn Trước hết ta thêm vào đồ thị đỉnh x và các cung x v với mọi v sau đó gọi Visit x để xây dựng cây DFS gốc x. Hiển nhiên x là chốt của thành phần liên thông chỉ gồm mỗi x. Sau đó bỏ đỉnh x khỏi cây DFS cây sẽ phân rã thành các cây con. Đỉnh r duyệt xong sau cùng chắc chắn là gốc của một cây con bởi khi duyệt xong nó chắc chắn sẽ lùi về x suy ra r là chốt. Hơn thế nữa nếu một đỉnh u nào đó tới được r thì u cũng phải thuộc cây con gốc r. Bởi nếu giả sử phản chứng rằng u thuộc cây con khác thì u phải được thăm trước r do cây con gốc r được thăm tới sau cùng có nghĩa là khi Visit u thì r chưa thăm. Vậy nên r sẽ thuộc nhánh DFS gốc u mâu thuẫn với lập luận r là gốc. Từ đó suy ra nếu u tới được r thì r tới được u tức là khi đảo chiều các cung nếu r tới được đỉnh nào thì đỉnh đó thuộc thành phần liên thông chốt r. Loại bỏ thành phần liên thông với chốt r khỏi đồ thị. Cây con gốc r lại phân rã thành nhiều cây con. Lập luận tương tự như trên với v là đỉnh duyệt xong sau cùng Hình 66 . Ví dụ Lê Minh Hoàng 204 Chuyên đề Hình 66 Đánh số lại đảo chiều các cung và .

• Cơ sở dữ liệu
• toán kinh tế
• kiến thức thống kê
• giáo trình đại học
• bài giảng chứng khoán
• đề cương ôn tập
• câu hỏi trắc nghiệm
• Đề cương toán kinh tế
• Ôn tập toán kinh tế
• Ôn thi toán kinh tế
• Lý thuyết toán kinh tế
• Kiến thức toán kinh tế
• Nghiên cứu toán kinh tế
• Đáp án Toán kinh tế
• Đề thi Toán kinh tế
• Đề cao học Toán kinh tế
• Đề thi Toán kinh tế 2013
• Đề thi Toán kinh tế 118
• Đề thi sau đại học Toán kinh tế
• Bài thi Toán kinh tế
• Câu hỏi thi Toán kinh tế
• Luyện thi Toán kinh tế
• Nội dung thi Toán kinh tế
• Bài giảng Toán kinh tế
• Tài liệu Toán kinh tế
• Tham khảo Toán kinh tế
• Mô hình toán kinh tế
• Hướng dẫn thi Toán kinh tế
• Tài liệu thi Toán kinh tế
• Mô hình toán
• Phân tích mô hình toán kinh tế
• Phương pháp phân tích toán kinh tế
• Bài tập toán kinh tế
• Bài tập mô hình toán kinh tế
• Bài tập phân tích toán kinh tế
• Học phần Toán kinh tế
• Đề cương học phần Toán kinh tế
• Tìm hiểu Toán kinh tế
• Bài toán Kinh tế
• Đáp án tham khảo Toán kinh tế 2011
• Câu hỏi Toán kinh tế
• Dự toán kinh tế
• Tiểu luận Dự toán kinh tế
• Bài tập Dự toán kinh tế
• Câu hỏi Dự toán kinh tế
• Phương pháp luận của Dự toán kinh tế
• Vai trò của Dự toán kinh tế
• Đề thi cao học Toán kinh tế
• Bài giảng Mô hình Toán kinh tế
• Cấu trúc mô hinh toán kinh tế
• Mô hình toán kinh tế phổ biến
• Mô hình giải tích phân tích kinh tế
• Phân tích kinh tế
• Phân tích kinh doanh
• Mô hình giải tích
• Công cụ toán
• Mô hình kinh tế
• Các phương tiện thanh toán quốc tế
• phương tiện thanh toán quốc tế
• bài giảng phương tiện thanh toán quốc tế
• tài liệu phương tiện thanh toán quốc tế
• nhập môn Kinh tế học Vi mô
• kinh tế vi mô
• kinh tế vĩ mô
• kinh tế phát triển
• kinh tế lượng
• Toán ứng dụng kinh tế
• Giáo trình mô hình toán kinh tế
• Lý thuyết toán học
• Phương pháp mô hình
• Nghiên cứu mô hình toán kinh tế
• Bài giảng Toán kinh tế 1
• Toán kinh tế 1
• Cấu trúc của môn học
• Kinh tế học