Le minh hoang bai giang cac chuyen de

THÔNG TIN TÀI LIỆU

Thông tin cơ bản

Tiêu đề	Bài Toán Li T Kê
Tác giả	Lê Minh Hoàng
Trường học	Trường Đại Học
Thể loại	Bài giảng

Định dạng
Số trang	258
Dung lượng	4,62 MB

Nội dung

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

{ 1z Bài toán li t kê M CL C §0 GI I THI U §1 NH C L I M T S KI N TH C I S T H P I CH NH H P L P II CH NH H P KHÔNG L P III HOÁN V IV T H P .3 §2 PH NG PHÁP SINH (GENERATE) 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 III LI T KÊ CÁC HOÁN V .9 §3 THU T TỐ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 TỐ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 Hồng { 2z Bài tốn li t kê §0 GI I THI U Trong th c t , có m t s tốn u c u ch rõ: m t t p đ i t ng cho tr c có đ i t ng tho mãn nh ng u ki n nh t đ nh Bài tốn g i tốn đ m c u hình t h p Trong l p toán đ m, có nh ng tốn cịn u c u ch rõ nh ng c u hình tìm đ c tho mãn u ki n cho nh ng c u hình Bài tốn u c u đ a danh sách c u hình có th có g i tốn li t kê t h p gi i toán li t kê, c n ph i xác đ nh đ c m t thu t tốn đ có th theo l n l t xây d ng đ c t t c c u hình 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ê ph ng k cu i đ gi i đ c m t s toán t h p hi n Khó kh n c a ph ng pháp s bùng n t h p xây d ng t c u hình (con s không ph i l n đ i v i tốn t h p - Ví d li t kê cách x p n≥13 ng i quanh m t bàn tròn) gi thi t r ng m i thao tác xây d ng m t kho ng giây, ta ph i m t quãng 31 n m m i gi i xong Tuy nhiên v i s phát tri n c a máy tính n t , b ng ph ng pháp li t kê, nhi u 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ê khơng cịn m t ph ng pháp khác tìm l i gi i Chính nh ng n l c gi i quy t tố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, v ngh a không ph i đ ng nh t, nh ng m t s tr ng h p ng i ta có th dùng l n ngh a c a đ c ó là: • Ph ng pháp li t kê • Ph ng pháp vét c n t p ph ng án • Ph ng pháp t tồn b Lê Minh Hồng { 3z Bài tốn li t kê §1 NH C L I M T S KI N TH C IS T H P Cho S m t t p h u h n g m n ph n t k m t s t nhiên G i X t p s nguyên d ng t đ 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 ch m t ph n t f(i) ∈ S c g i m t ch nh h p l p ch p k c a S Nh ng X t p h u h n (k ph n t ) nên ánh x f có th xác đ nh qua b ng giá tr f(1), f(2), , f(k) Ví d : S = {A, B, C, D, E, F}; k = M t ánh x f có th cho nh sau: i 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)) coi dãy giá tr c ng m t ch nh h p l p ch p k c a S Nh ví d (E, C, E) m t ch nh h p l p ch p 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 : k An = nk II CH NH H P KHƠNG L P Khi f đ n ánh có ngh a v i ∀i, j ∈ X ta có f(i) = f(j) ⇔ i = j Nói m t cách d hi u, dãy giá tr f(1), f(2), , f(k) g m ph n t thu c S khác đơi m t f đ c g i m t ch nh h p khơng l p ch p k c a S Ví d m t ch nh h p không l p (C, A, E): i f(i) C A E S ch nh h p không l p ch p k c a t p g m n ph n t : n! A kn = n (n − 1)(n − 2) (n − k + 1) = (n − k )! III HOÁN V Khi k = n M t ch nh h p không l p ch p n c a S đ c g i m t hoán v ph n t c a S Ví d : m t hốn v : (A, D, C, E, B, F) c a S = {A, B, C, D, E, F} i f(i) A D C E B F ý r ng k = n s ph n t c a t p X = {1, 2, , n} b ng s ph n t c a S Do tính ch t đơi m t khác nên dãy f(1), f(2), , f(n) s li t kê đ c h t ph n t S Nh v y f toàn ánh M t khác gi thi t f ch nh h p không l p nên f đ n ánh Ta có t ng ng 1-1 gi a ph n t c a X S, f song ánh V y nên ta có th đ nh ngh a m t hoán v c a S m t song ánh gi a {1, 2, , n} S S hoán v c a t p g m n ph n t = s ch nh h p không l p ch p n: Pn = n! IV T H P M t t p g m k ph n t c a S đ Lê Minh Hoàng c g i m t t h p ch p k c a S { 4z Bài toán li t kê L y m t t p k ph n t c a S, xét t t c k! hoán v c a t p D th y r ng hoán v ch nh h p khơng l p ch p k c a S Ví d l y t p {A, B, C} t p c a t p S ví d thì: (A, B, C), (C, A, B), (B, C, A), ch nh h p không l p ch p c a S i u t c li t kê t t c ch nh h p khơng l p ch p k m i t h p ch p k s đ c tính k! l n V y: S t h p ch p k c a t p g m n ph n t : A kn n! C = = k! k!(n − k )! k n S t p c a t p n ph n t : C 0n + C1n + + C nn = (1 + 1) n = n Lê Minh Hoàng { 5z Bài tốn li t kê §2 PH NG PHÁP SINH (GENERATE) Ph ng pháp sinh có th áp d ng đ gi i toán li t kê t h p đ t n u nh hai u ki n sau tho mãn: Có th xác đ nh đ c m t th t t p c u hình t h p c n li t kê T có th xác đ nh đ c c u hình đ u tiên c u hình cu i th t xác đ nh Xây d ng đ c thu t tốn t c u hình ch a ph i c u hình cu i, sinh đ c c u hình k ti p Ph ng pháp sinh có th mơ t nh sau: ; repeat < a c u hình có>; ; Th t t n Trên ki u d li u đ n gi n chu n, ng i ta th ng nói t i khái ni m th t Ví d ki u s có quan h : < 2; < 3; < 10; , ki u ký t Char c ng có quan h 'A' < 'B'; 'C' < 'c' Xét quan h th t toàn ph n "nh h n ho c b ng" ký hi u "≤" m t t p h p S, quan h hai ngơi tho mãn b n tính ch t: V i ∀a, b, c ∈ S • Tính ph bi n: Ho c a ≤ b, ho c b ≤ a; • Tính ph n x : a ≤ a • Tính ph n đ i x ng: N u a ≤ b b ≤ a b t bu c a = b • Tính b c c u: N u có a ≤ b b ≤ c a ≤ c Trong tr ng h p a ≤ b a ≠ b, ta dùng ký hi u "

Ngày đăng: 26/08/2013, 20:14

Xem thêm