TAILIEUCHUNG - Toán rời rạc part 5

Tham khảo tài liệu 'toán rời rạc part 5', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Phần 1. Lý thuyết tổ hợp Khi đó thuật toán nhánh cận được thực hiện nhờ thủ tục sau procedure Nhanh_can begin f oo Nếu biết một phương án X nào đó thì có thể đặt f f X Try _l _ if f CO then f là giá trị tối ưu X là phương án tối ưu else bài toán không có phương án end Chú ý ràng nếu trong thủ tục Try ta thay câu lệnh ỉf k n then Cập nhật kỷ lục else if g alt a2 . ak f then Try k 1 bởi if k n then Cập nhật kỷ lục else Try k 1 thì thủ tục Try sẽ liệt kê toàn bộ các phương án của bài toán và ta thu được thuật toán duyệt toàn bộ. Việc xây dựng hàm g phụ thuộc vào từng bài toán tối ưu tổ hợp cụ thể. Thông thường ta cô gắng xây dựng nó sao cho Việc tính giá trị của g phải đơn giản hơn việc giải bài toán tối ưu tổ hợp ở vê phải của . Giá trị của g ứ15 a2 . . . ứt phải sát với giá trị của vế phải của . Rất tiếc là hai yêu cầu này trong thực tế thường đối lập nhau. Dưới đây chúng ta sẽ xét một sô thí dụ minh hoạ cho thuật toán vừa trình bày. a Bài toán cái túL Chúng ta sẽ xét một dạng bài toán cái túi nữa rất hay được sử dụng trong các ứng dụng thực tế về nguyên tắc mô hình ở đây và mô hình đã trình bày trong mục là có thể qui dản về nhau . Thay VI có n đồ vật như mô hình trong mục ở đây ta giả thiết ràng có n loại đổ vật và số lượng đồ vật mỗi loại là không hạn chế. Khi đó ta có mô hình bài toán cái túi biến nguyên sau đây Có n loại đổ vật đổ vật thứ j có trọng lượng ũj và giá trị sử dụng là Cj - 1 2 . n . Cần chất các đồ vật này vào một cái túi có trọng lượng là b sao cho tổng giá trị sử dụng của các đồ vật chất trong túi là lớn nhắt. 114 Chương 5. Bài toán tối ưu tổ hợp Mô hình toán học của bài toán có dạng sau Tìm f max x CjX . ajX. -b x e z j 1 2 . 1 j i 1 trong đó z là tập các số nguyên không âm. Ký hiệu D là tập các phương án của bài toán 1 D ịx x1x2 . x y. 2 itjXj b Xj z j l 2 . n . j i Không giảm tổng quát ta giả thiết rằng các đồ vật được đánh số sao cho bất đẳng thức sau được thoả mãn Cị cìị c2ỉa2 . cj a . 2 Để xây dựng hàm tính yặn dưới cùng với bài toán

• Toán học
• Toán rời rạc
• tài liệu Toán rời rạc
• giáo trình Toán rời rạc
• bài giảng Toán rời rạc
• tìm hiểu Toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• Bài tập về toán rời rạc
• Ôn tập toán rời rạc
• Đề thi toán rời rạc