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.
Nội dung trích xuất từ tài liệu:
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 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................................................................................................................................................... 25Lê Minh HoàngBài toán liệt kê 2[ §0. GIỚI THIỆUTrong 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ó baonhiê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ìnhCó 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ợphiệ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ấuhì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≥13ngườ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ấtquã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ươngpháp liệt kê, nhiều bài toán tổ hợp đã tìm thấ ...
