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 p6

Sau khi tất cả các con đã được phân nhánh hoặc bị cắt tỉa thì phương án có giá nhỏ nhất trong các phương án tìm được là phương án cần tìm. Trong quá trình xây dựng cây có thể ta đã xây dựng được một số nút lá, như ta biết mỗi nút lá biểu diễn cho một phương án. Giá nhỏ nhất trong số các giá của các phương án này được gọi là giá nhỏ nhất tạm thời.
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 p6 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 • Sau khi tất cả các con đã được phân nhánh hoặc bị cắt tỉa thì phương án có giá nhỏ nhất trong các phương án tìm được là phương án cần tìm. Trong quá trình xây dựng cây có thể ta đã xây dựng được một số nút lá, như ta biết mỗi nút lá biểu diễn cho một phương án. Giá nhỏ nhất trong số các giá của các phương án này được gọi là giá nhỏ nhất tạm thời. Ví dụ 3-10: Xét bài toán TSP trong ví dụ 3-7 nói trên. Tập hợp các cạnh để xét phân nhánh là ab, ac, ad, ae, bc, bd, be, cd, ce và de. Ðiều kiện bổ sung ở đây là mỗi đỉnh phải được chọn hai cạnh, bị loại hai cạnh và không được tạo ra chu trình thiếu. Nút gốc A bao gồm tất cả các phương án, có cận dưới là 17.5. Phân nhánh cho A, xây dựng hai con là B và C. Tính cận dưới cho hai nút này được cận dưới của B là 17.5 và C là 18.5. Nút B có cận dưới nhỏ hơn nên được phân nhánh trước. Hai con của B là D và E. Các ràng buộc của D và E giống nh-ư ta đã nói trong ví dụ của phần phân nhánh. Tính cận cho D và E, được cận dưới của D là 20.5 và của E là 18. Nút E được xét trước. Phân nhánh cho nút E theo cạnh ad, hai con của E ...