TAILIEUCHUNG - Giáo trình hình thành phương pháp cấu tạo dữ liệu giải thuật ứng dụng trong hệ thống p3

Tham khảo tài liệu 'giáo trình hình thành phương pháp cấu tạo dữ liệu giải thuật ứng dụng trong hệ thống p3', công nghệ thông tin, quản trị mạng phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Giải thuật Thông thường một phép biến đổi chỉ thay đổi một bộ phận nào đó của phương án hiện hành để được một phương án mới nên phép biến đổi được gọi là phép biến đổi địa phương và do đó ta có tên kĩ thuật tìm kiếm địa phương. Sau đây ta sẽ trình bày một số ví dụ áp dụng kĩ thuật tìm kiếm địa phương. Bài toán cây phủ tối thiểu Cho G V E là một đồ thị vô hướng liên thông trong đó V là tập các đỉnh và E là tập các cạnh. Các cạnh của đồ thị G đều có trọng số. Cây T có tập hợp các nút là V được gọi là cây phủ spaning tree của đồ thị G. Cây phủ tối thiểu là một cây phủ của G mà tổng độ dài trọng số các cạnh nhỏ nhất. Bài toán cây phủ tối thiểu thường được áp dụng trong việc thiết kế một mạng lưới giao thông giữa các thành phố hay thiết kế một mạng máy tính. Kĩ thuật tìm kiếm địa phương áp dụng vào bài toán này như sau Phương án ban đầu là một cây phủ nào đó. 6 Hình 3-15 Bài toán cây phủ tối thiểu n n-1 Thành lập tập tất cả các cạnh theo thứ tăng dần của độ dài có 2 cạnh đối với đồ thị có n đỉnh . Phép biến đổi địa phương ở đây là Chọn một cạnh có độ dài nhỏ nhất trong tập các cạnh chưa sử dụng để thêm vào cây. Trong cây sẽ có một chu trình loại khỏi chu trình cạnh có độ dài lớn nhất trong chu trình đó. Ta được một cây phủ mới. Lặp lại bước này cho đến khi không còn cải thiện được phương án nữa. Ví dụ 3-12 Cho đồ thị G bao gồm 5 đỉnh a b c d e và độ dài các cạnh được cho trong hình 3-15. Tập hợp các cạnh để xét được thành lập theo thứ tự từ nhỏ đến lớn là ad ab be bc ac cd bd de ae và ce. Cây xuất phát với giá là 20 Hình 316 . Thêm cạnh ad 2 bỏ cạnh cd 5 ta được cây mới có giá là 17 Hình 3-17 . Lại thêm cạnh ab 3 bỏ cạnh bc 4 ta được cây có giá là16 Hình 3-18 . Thêm cạnh be 3 bỏ cạnh ae 7 ta được cây có giá là 12. Hình 3-19 . Việc áp dụng các phép biến đổi đến đây dừng lại vì nếu tiếp tục nữa thì cũng không cải thiện được phương án. Vậy cây phủ tối thiểu cần tìm là cây trong hình 3-19 Trang 79 Giải thuật Hình 3-16 Cây xuất phát giá 20 Hình 3-18 Giá 16 Hình 3-19 .

• Quản trị mạng
• giáo trình lập trình
• thủ thuật quản trị mạng
• kỹ năng lập trình
• phương pháp lập trình
• mẹo quản lập trình
• kinh nghiệm lập trình
• code lập trình
• kỹ thuật phần mềm
• chương trình lập trình
• lập trình máy tính
• lập trình SQL
• giáo trình lập trình SQL
• tài liệu lập trình SQL
• ngôn ngữ lập trình SQL
• tự học lập trình SQL
• thủ thuật lập trình
• lập trình căn bản
• kỹ thuật máy tính
• lập trình hướng đối tượng
• tài liệu lập trình
• chuyên ngành lập trình
• tổng quan về lập trình
• mẹo lập trình
• lập trình ASP
• ngôn ngữ kịch bản
• Giáo trình ngôn ngữ lập trình Java
• Ngôn ngữ lập trình
• Lập trình Java
• Lập trình mạng
• Kỹ thuật lập trình Java
• Giáo trình Ngôn ngữ lập trình C
• Giáo trình lập trình C
• Giáo trình Ngôn ngữ lập trình
• Ngôn ngữ lập trình C
• Lập trình C
• ngôn ngữ C++
• Giáo trình C
• Phương pháp lập trình C
• chương trình
• thuật toán
• đối tượng
• lập trình C++
• Lập trình hợp ngữ
• lập trình tuyến tính
• bài giảng lập trình C++
• phương pháp lập trình cấu trúc
• phép tham chiếu
• lập trình Visual C++
• Lập trình C trên Windows
• phần mềm máy tính
• Lập trình Windows
• kỹ thuật lập trình
• lập trình đối tượng
• giáo trình lập trình đối tượng
• Giáo trình lập trình C++
• Ngôn ngữ lập trình C++
• Học lập trình C
• Kỹ thuật lập trình C cơ bản
• Giáo trình kỹ thuật lập trình c
• Tài liệu lập trình c cơ bản
• Giáo trình kỹ thuật lập trình C nâng cao
• Lập trình mạng bằng java
• Lập trình PHP
• ngôn ngữ lập trình Perl
• lập trình web
• tập hợp các trang web
• Giáo trình Điều khiển lập trình cỡ nhỏ
• Điều khiển lập trình cỡ nhỏ
• Điện công nghiệp
• Sơ đồ khối cấu trúc bộ lập trình cỡ nhỏ
• Thiết bị điều khiển lập trình
• Lập trình điều khiển hệ thống bơm nước
• Lập trình điều khiển hệ thống băng tải