Chuyen de BD HSG 5

MỤC LỤC
MỤC LỤC 1
§0. GIỚI THIỆU 3
§1. NHẮC LẠI MỘT SỐ KIẾN THỨC ĐẠI SỐ TỔ HỢP 4
I. CHỈNH HỢP LẶP 4
II. CHỈNH HỢP KHÔNG LẶP 4
III. HOÁN VỊ 4
IV. TỔ HỢP 4
§2. PHƯƠNG PHÁP SINH (GENERATE) 6
I. SINH CÁC DÃY NHỊ PHÂN ĐỘ DÀI N 7
II. LIỆT KÊ CÁC TẬP CON K PHẦN TỬ 8
III. LIỆT KÊ CÁC HOÁN VỊ 10
§3. THUẬT TOÁN QUAY LUI 13
I. LIỆT KÊ CÁC DÃY NHỊ PHÂN ĐỘ DÀI N 14
II. LIỆT KÊ CÁC TẬP CON K PHẦN TỬ 15
III. LIỆT KÊ CÁC CHỈNH HỢP KHÔNG LẶP CHẬP K 16
IV. BÀI TOÁN PHÂN TÍCH SỐ 17
V. BÀI TOÁN XẾP HẬU 19
§4. KỸ THUẬT NHÁNH CẬN 24
I. BÀI TOÁN TỐI ƯU 24
II. SỰ BÙNG NỔ TỔ HỢP 24
III. MÔ HÌNH KỸ THUẬT NHÁNH CẬN 24
IV. BÀI TOÁN NGƯỜI DU LỊCH 25
V. DÃY ABC 27
§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 phương pháp liệt kê khi không còn một phương pháp nào khác tìm ra lời giải. Chính những nỗ lực giải quyết các bài toán thực tế không dùng phương pháp liệt kê đã thúc đẩy sự phát triển của nhiều ngành toán học.
Cuối cùng, những tên gọi sau đây, tuy về nghĩa không phải đồng nhất, nhưng trong một số trường hợp người ta có thể dùng lẫn nghĩa của nhau được. Đó là:
Phương pháp liệt kê
Phương pháp vét cạn trên tập phương án
Phương pháp duyệt toàn bộ
§1. NHẮC LẠI MỘT SỐ KIẾN THỨC ĐẠI SỐ TỔ HỢP
Cho S là một tập hữu hạn gồm n phần tử và k là một số tự nhiên.
Gọi X là tập các số nguyên dương từ 1 đến k: X = {1, 2, ..., k}
I. CHỈNH HỢP LẶP
Mỗi ánh xạ f: X ( S. Cho tương ứng với mỗi i ( X, một và chỉ một phần tử f(i) ( S.
Được gọi là một chỉnh hợp lặp chập k của S.
Nhưng do X là tập hữu hạn (k phần tử) nên ánh xạ f có thể xác định qua bảng các giá trị f(1), f(2), ..., f(k).
Ví dụ: S = {A, B, C, D, E, F}; k = 3. Một ánh xạ f có thể cho như sau:
i
1
2
3

f(i)
E
C
E

Nên người ta đồng nhất f với dãy giá trị (f(1), f(2), ..., f(k)) và coi dãy giá trị này cũng là một chỉnh hợp lặp chập k của S. Như ví dụ trên (E, C, E) là một chỉnh hợp lặp chập 3 của S. Dễ dàng chứng minh được kết quả sau bằng quy nạp hoặc bằng phương pháp đánh giá khả năng lựa chọn:
Số chỉnh hợp lặp chập k của tập gồm n phần tử:

II. CHỈNH HỢP KHÔNG LẶP
Khi f là đơn ánh có nghĩa là với (i, j ( X ta có