tailieunhanh - Bài giảng chuyên đề: Bài toán liệt kê, cấu trúc dữ liệu và giải thuật, quy hoạch động, lý thuyết đồ thị -

Bài giảng cung cấp cho người học những kiến thức về bài toán liệt kê, cấu trúc dữ liệu và giải thuật, quy hoạch động, lý thuyết đồ thị. Đây là tài liệu tham khảo hữu ích cho sinh viên các ngành Công nghệ thông tin và các ngành liên quan. Mời các bạn cùng tham khảo. | Bài toán liệt kê 1 MỤC LỤC 0. GIỚI THIỆU. 2 1. NHẮC LẠI MỘT SỐ KIẾN THỨC ĐẠI SỐ TỔ HỢP. 3 I. CHỈNH HỢP LẶP. 3 II. CHỈNH HỢP KHÔNG LẶP. 3 III. HOÁN VỊ. 3 IV. TỔ HỢP. 3 2. PHƯƠNG PHÁP SINH GENERATE . 5 I. SINH CÁC DÃY NHỊ PHÂN ĐỘ DÀI N . 6 II. LIỆT KÊ CÁC TẬP CON K PHẦN TỬ . 7 III. LIỆT KÊ CÁC HOÁN VỊ. 9 3. THUẬT TOÁN QUAY LUI. 12 I. LIỆT KÊ CÁC DÃY NHỊ PHÂN ĐỘ DÀI N. 13 II. LIỆT KÊ CÁC TẬP CON K PHẦN TỬ . 14 III. LIỆT KÊ CÁC CHỈNH HỢP KHÔNG LẶP CHẬP K. 15 IV. BÀI TOÁN PHÂN TÍCH SỐ. 16 V. BÀI TOÁN XẾP HẬU . 18 4. KỸ THUẬT NHÁNH CẬN. 22 I. BÀI TOÁN TỐI ƯU. 22 II. SỰ BÙNG NỔ TỔ HỢP. 22 III. MÔ HÌNH KỸ THUẬT NHÁNH CẬN. 22 IV. BÀI TOÁN NGƯỜI DU LỊCH. 23 V. DÃY ABC. 25 Lê Minh Hoàng Bài toán liệt kê 2 0. GIỚI THIỆU Trong thực tế có một số bài toán yêu cầu chỉ rõ trong một tập các đối tượng cho trước có bao nhiêu đối tượng thoả mãn những điều kiện nhất định. Bài toán đó gọi là bài toán đếm cấu hình tổ hợp. Trong lớp các bài toán đếm có những bài toán còn yêu cầu chỉ rõ những cấu hình tìm được thoả mãn điều kiện đã cho là những cấu hình nào. Bài toán yêu cầu đưa ra danh sách các cấu hình có thể có gọi là bài toán liệt kê tổ hợp. Để giải bài toán liệt kê cần phải xác định được một thuật toán để có thể theo đó lần lượt xây dựng được tất cả các cấu hình đang quan tâm. Có nhiều phương pháp liệt kê nhưng chúng cần phải đáp ứng được hai yêu cầu dưới đây Không được lặp lại một cấu hình Không được bỏ sót một cấu hình Có thể nói rằng phương pháp liệt kê là phương kế cuối cùng để giải được một số bài toán tổ hợp hiện nay. Khó khăn chính của phương pháp này chính là sự bùng nổ tổ hợp. Để xây dựng 1 tỷ cấu hình con số này không phải là lớn đối với các bài toán tổ hợp - Ví dụ liệt kê các cách xếp n 13 người quanh một bàn tròn và giả thiết rằng mỗi thao tác xây dựng mất khoảng 1 giây ta phải mất quãng 31 năm mới giải xong. Tuy nhiên cùng với sự phát triển của máy tính điện tử bằng phương pháp liệt kê nhiều bài toán tổ hợp đã tìm thấy lời giải. Qua đó ta cũng nên biết rằng chỉ nên dùng .