Giáo trình hướng dẫn phân tích kĩ thuật thiết kế giải thuật ứng dụng trong sản xuất p7

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. 3.6.2 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...
Nội dung trích xuất từ tài liệu:
Giáo trình hướng dẫn phân tích kĩ thuật thiết kế giải thuật ứng dụng trong sản xuất p7 h a n g e Vi h a n g e Vi XC XC e e F- F- w w PD PD er er ! ! W W O O N N y y bu bu Giải thuật Kĩ thuật thiết kế giải thuật to to k k lic lic C C w w m m w w w w o o .c .c .d o .d o c u -tr a c k c u -tr a c k 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. 3.6.2 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 đó. n(n - 1) • Thàn ...