tailieunhanh - Giáo trình phân tích khả năng ứng dụng kĩ thuật thiết kế giải thuật ứng dụng trong sản xuất p1

Tham khảo tài liệu 'giáo trình phân tích khả năng ứng dụng kĩ thuật thiết kế giải thuật ứng dụng trong sản xuất p1', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Gi áo trình phân tích khả năng ứng dụng kĩ thi uật thiết kế giải thuật ứng dụng trong sản xuất Chiến lược chia để trị xây dựng lịch thi đấu như sau Để sắp lịch cho n đấu thủ ta sẽ sắp lịch cho n 2 đấu thủ để sắp lịch cho n 2 đấu thủ ta sẽ sắp lịch cho n 4 đấu thủ. Quá trình này sẽ dẫn đến bài toán cơ sở là sắp lịch thi đấu cho 2 đấu thủ. Hai đấu thủ này sẽ thi đấu một trận trong một ngày lịch thi đấu cho họ thật dễ sắp. Khó khăn chính là ở chỗ từ các lịch thi đấu cho hai đấu thủ ta tổng hợp lại để được lịch thi đấu của 4 đấu thủ 8 cấu thủ . Xuất phát từ lịch thi đấu cho hai đấu thủ ta có thể xây dựng lịch thi đấu cho 4 đấu thủ như sau Lịch thi đấu cho 4 đấu thủ sẽ là một bảng 4 dòng 3 cột. Lịch thi đấu cho 2 đấu thủ 1 và 2 trong ngày thứ 1 chính là lịch thi đấu của hai đấu thủ bài toán cơ sơ . Như vậy ta có Ô 1 1 2 và Ô 2 1 1 . Tương tự ta có lịch thi đấu cho 2 đấu thủ 3 và 4 trong ngày thứ 1. Nghĩa là Ô 3 1 4 và Ô 4 1 3 . Ta cố thể thấy rằng Ô 3 1 Ô 1 1 2 và Ô 4 1 Ô 2 1 2 . Bây giờ để hoàn thành lịch thi đấu cho 4 đấu thủ ta lấy góc trên bên trái của bảng lắp vào cho góc dưới bên phải và lấy góc dưới bên trái lắp cho góc trên bên phải. Lịch thi đấu cho 8 đấu thủ là một bảng gồm 8 dòng 7 cột. Góc trên bên trái chính là lịch thi đấu trong 3 ngày đầu của 4 đấu thủ từ 1 đến 4. Các ô của góc dưới bên trái sẽ bằng các ô tương ứng của góc trên bên trái cộng với 4. Đây chính là lịch thi đấu cho 4 đấu thủ 5 6 7 và 8 trong 3 ngày đầu. Bây giờ chúng ta hoàn thành việc sắp lịch bằng cách lấp đầy góc dưới bên phải bởi góc trên bên trái và góc trên bên phải bởi góc dưới bên trái. 2 đấu thủ 4 đấu thủ 8 đấu thủ 1 2 3 4 5 6 7 2 3 4 5 6 7 8 1 4 3 6 5 8 7 4 1 2 7 8 5 6 3 2 1 8 7 6 5 6 7 8 1 2 3 4 5 8 7 2 1 4 3 8 5 6 3 4 1 2 7 6 5 4 3 2 1 Hình 3-1 Lịch thi đấu của 2 4 và 8 đấu thủ Bài toán con cân bằng Balancing Subproblems Đối với kĩ thuật chia để trị nói chung sẽ tốt hơn nếu ta chia bài toán cần giải thành các bài toán con có kích thước gần bằng nhau. Ví dụ sắp xếp trộn .