BÀI 5

BÀI TOÁN LIỆT KÊ

Giáo viên: TS. Nguyễn Văn Hiệu Email: nvhieuqt@dut.udn.vn

1 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.1. Giới thiệu

Nội dung

 5.1. Giới thiệu  5.2. Phương pháp sinh  5.3. Phương pháp quay lui

2 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.1. Giới thiệu

Mục đích  Đưa ra danh sách tất cả các cấu hình có

thể có

Bản chất  Xác định một thuật toán để theo đó có thể lần lượt xây dựng được tất cả các cấu hình đang quan tâm.

3 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.1. Giới thiệu

Nguyên tắc  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

Lưu ý  Chỉ giải với bài toán chưa có phương

pháp giải

 Phương pháp Sinh  Phương pháp quay lui

4 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

Thường sử dụng  Giải bài toán liệt kê tổ hợp

Điều kiện

 Xác định được một thứ tự.  Có cấu hình đầu tiên  Có cấu hình cuối cùng  Xác định được thuật toán để xây dựng

cấu hình kế tiếp

5 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

Bản chất

Chú thích

Generating_method(…) {

 Stop = =1, là cấu hình

cuối cùng

;

 Stop == 0, chưa phải là cấu hình cuối cùng

stop = islastconfigure(…); while (stop==0) { ;

} }

là thuật toán sinh cấu hình tiếp theo trên thứ tự đã xác định trước

6 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

Ví dụ

 Liệt kê dãy nhị phân có độ dài n.  Liệt kê các tập con k phần tử của tập

n phần tử.

 Liệt kê các hoán vị của tập n phần tử

7 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

Ví dụ 1: Liệt kê các dãy nhị phân có độ dài n

Bước 1: Xác định thứ tự

Dãy nhị phân được biểu diễn: b = (b1 b2 … bn ) thỏa mản bi €{0,1}  Định nghĩa thứ tự từ điển: b = (b1 b2 ... bn) và *b = (*b1 *b2 ... *bn) thứ tự b < *b, nếu q(b) < q(*b)

8 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

Ví dụ 1: Liệt kê các dãy nhị phân có độ dài n

Bước 2: Cấu hình đầu và cuối  Khi n = 4 phần tử, có 24

dãy nhị phân được liệt kê

9 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

Ví dụ 1: Liệt kê các dãy nhị phân có độ dài n

q(b)

q(b)

Bước 2:

b 1000 8 1001 9 1010 10 1011 11 1100 12 1101 13 1110 14 1111 15

b 0000 0 0001 1 0010 2 0011 3 0100 4 0101 5 0110 6 0111 7

10 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

Thuật toán

Bước 3: xác định thuật toán

0000

0001

0001

0010

 Tìm i từ bên phải: bi = 0.  Gán lại bi = 1 và bj = 0 với mọi j> i.

0011

0100

i= n;

0111

1000

while (i>=1 && b[i]==‘1’)

b[i--] = ‘0’;

b[i] = ‘1’;

11 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

12 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

13 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

Ví dụ 1:

Liệt kê các dãy nhị phân có độ dài n

Kết quả

Chương trình

Source Code

Result

14 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

Ví dụ 2 Liệt kê các tập con k phần tử của tập n phần tử

Chuẩn bị

 Ánh xạ tập n phần tử vào tập X = {1,2,…,n}  Mỗi tập con k phần tử của X được biểu diễn bởi

bộ có thứ tự gồm k thành phần:

a = (a1 a2 a3 ..... ak ) thỏa mản 1≤ a1< a2 < a3 <..... < ak ≤ n

15 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

Ví dụ 2 Liệt kê các tập con k phần tử của tập n phần tử

Bước 1: Xác định thứ tự

 Định nghĩa thứ tự từ điển: a = (a1 a2 a3 ...ak) và b = (b1 b2 b3 ... bk) thứ tự a < b, nếu tồn tại j (1≤ j≤ k): a1 = b1,...,aj-1= bj-1, aj < bj

16 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

Ví dụ 2: Liệt kê các tập con k phần tử của tập n phần tử

Cấu hình đầu

Bước 2:

Cách sinh

 𝑪𝟑

 Các tập con 3 phần tử của tập 5 phần tử {1,2,3,4,5} 5 = 10

Cấu hình cuối

{ 1,2,3 } { 1,2,4 } { 1,2,5 } { 1,3,4 } { 1,3,5 } { 1,4,5 } { 2,3,4 } { 2,3,5 } { 2,4,5 } { 3,4,5 }

17 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

Thuật toán

Bước 3: xác định thuật toán

n=5, k=3

Giả sử a = (a1...ak ) không là cuối cùng.

1 2 3

i = a = {1, 4, 5 } n-k+i = 3 4 5

{ 2, , } { 2, 3, 4}

 B1: Tìm vị trí i đầu tiên từ bên phải của dãy: ai ≠ n-k+i.  B2: Thay ai bởi ai + 1.  B3: Thay aj bởi ai - i +j, với j = i+1,...,k

18 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

Thuật toán

Code

Giả sử a = (a1...ak ) không là cuối cùng.

 B1: Tìm vị trí i đầu tiên từ bên phải của dãy: ai ≠ n-k+i.  B2: Thay ai bởi ai + 1.  B3: Thay aj bởi ai - i +j, với j = i+1,...,k

B1: i=k; while (a[i]==n-k+i) i-- ; B2: a[i]= a[i] + 1; B3: for (j=i+1;j<=k;j++) a[j]= a[i]+ j –i;

19 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

20 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

21 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

Ví dụ 2

Liệt kê các tập con k phần tử từ tập n phần tử

Kết quả

Chương trình

Source Code

Result

22 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

Ví dụ 3

Liệt kê hoán vị của tập n phần tử

23 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

Minh họa

 {1,2,3,4} ?

 {4,3,2,1}?

 {3,4,2,1}  {4,1,2,3}?

 Xây dựng thuật toán

sinh

{3,1,2,4} {3,1,4,2} {3,2,1,4} {3,2,4,1} {3,4,1,2} {3,4,2,1} {4,1,2,3} {4,1,3,2} {4,2,1,3} {4,2,3,1} {4,3,1,2} {4,3,2,1}

{1,2,3,4} {1,2,4,3} {1,3,2,4} {1,3,4,2} {1,4,2,3} {1,4,3,2} {2,1,3,4} {2,1,4,3} {2,3,1,4} {2,3,4,1} {2,4,1,3} {2,4,3,1}

24 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

Định nghĩa

Định nghĩa

 Ánh xa tập n phần tử bất kỳ

vào tập

 Thứ tự từ điển: a = (a1 a2 a3 ...an) b = (b1 b2 b3 ... bn) thứ tự a < b, nếu tồn tại j (1≤ j≤ n): a1 = b1,...,aj-1= bj-1, aj < bj

X = {1,2,…,n}  Mỗi hoán vị của X được biểu diễn bởi bộ có thứ tự gồm n thành phần: a = (a1 a2 ... an ) thỏa mản ai € X,

i=1,…,n , ap ≠ aq , p ≠ q.

25 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

Bước 3:

Thuật toán

n= 4

 a = (a1 a2...an ) chưa phải là cuối

cùng.

 B1: Tìm Right -> Left, j đầu

i = 1 2 3 4 a = {1 3 4 2}

tiên:

k = 1 2 3 4 a = { 1 3 4 2}

aj ≤ aj+1  B2: Tìm Right -> Left, k đầu

tiên:

a = { , 4 , 3, }

a = { , , 2, 3 }

ak > aj.  B3: hoán vị aj và ak  B4: Lật ngược đoạn aj+1 đến an

26 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

Bước 3:

 B1: Tìm Right -> Left, j

 int j = n-1; while(j>=1&&a[j]>a[j+1])j--;

đầu tiên: aj ≤ aj+1  B2: Tìm Right -> Left, k

đầu tiên:

a[l]=

ak > aj.  B3: hoán vị aj và ak  B4: Lật ngược đoạn aj+1

đến an

 int k = n; while(a[j]>a[k])k--;  int temp = a[j]; a[j] = a[k]; a[k] = temp;  int l = j+1;int r = n; while(l

27 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

28 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

29 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

30 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

Ví dụ 2

Liệt kê các tập hoán vị của tập n phần tử

Kết quả

Chương trình

Source Code

Result

31 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

Bài toán liệt kê

Nội dung

 5.1. Giới thiệu  5.2. Phương pháp sinh  5.3. Phương pháp quay lui

32 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

Phương pháp quay lui

Nội dung

 Mục đích  Khái niệm  Phương pháp  Mã giả  Minh họa

33 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.3. Phương pháp quay lui

Mục đích

Khái niệm

 Để giải bài toán liệt kê hoặc tối ưu tổ hợp

 Backtracking  Поиск с возвратом  Quay lui

 Đã giải:

 Backtracking  1950,  D.H.Lehmer

 Bài toán mã đi tuần  Bài toán xếp hậu  Bài toán mê cung  Bài toán người giao

hàng

34 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.3. Phương pháp quay lui

Khái niệm

Khái niệm  Một cấu hình hay một nghiệp: s 1 s 2… s n s i ∈ D

 Bài toán: Liệt kê tất cả các cấu hình của S S = s 1 s 2… s n

 Backtracking– đi tìm lời giải cho bài toán mà nghiệm của nó là một cấu hình hoặc một tập cấu hình:  Tính chất P: xác định

cấu hình

 Bài toán con: Giả sử đã tìm được s 1… s i , i < 𝑛 Hãy tìm cấu hình S

 Tính chất Q: xác định tính dừng của bài toán

35 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.3. Phương pháp quay lui

Phương pháp

Bản chất  Một quy trình tìm kiếm theo chiều

sâu

 Ví dụ tìm số có 3 chữ số đầu tiên

 Giả sử có: s1…s i-1 Tìm giá trị cho s i:  Duyệt ∀ j ∈ 𝐷 đề cử cho si  Mỗ𝑖 j ∈ 𝐷 kiểm tra:

 D = {1,2, 3}  P:

 Nếu j chấp nhận (∈ P ), si = j  Nếu i = n (∈ Q ) , được 1

cấu hình,

 (2,1,3) – chấp nhận  (2,2,3) – không chấp nhận

 Nếu i< 𝑛, tìm s i +1.  Nếu ∀ j không được cấp nhận (∉ P ) (ngõ cụt) thì quay lại bước xác định si-1

1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1

36 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.3. Phương pháp quay lui

Phương pháp

 Giả sử có: s1…s i-1 Tìm giá trị cho s i:  Duyệt ∀ j ∈ 𝐷 đề cử cho si  Mỗ𝑖 j ∈ 𝐷 kiểm tra:

 Nếu j chấp nhận (∈ P ), si = j  Nếu i = n (∈ Q ) , được 1

cấu hình,

 Nếu i< 𝑛, tìm s i +1.  Nếu ∀ j không được cấp nhận (∉ P ) (ngõ cụt) thì quay lại bước xác định si-1

Mã giả void try (i, n){ ∀j ∈ Di{ if (< chấp nhận j>){ si = j; if (i==n) else try (i+1, n); } } }

38 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.3. phương pháp quay lui

Bắt đầu

S1

D1 ( 2pt)

D2 (2pt)

s2

D3 (2pt)

s3

D4 ( 3pt)

s4

Một cấu hình

39 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp quay lui

Ví dụ

 Liệt kê dãy nhị phân có độ dài n.  Liệt kê hoán vị tập n phần tử.  Bài toán Xếp Hậu.

40 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.3. Phương pháp quay lui

Ví dụ 1

 Liệt kê xâu nhị phân độ dài n

 Biểu diễn dãy nhị phân:

b = ( b1 b2... bn ,) bi ∈ {0,1}

 Try(i,…) - xác định bi  D = {0,1}  P  i = n - được 1 cấu hình ∈ 𝑄

Mã giả void Try(int i, char b[]){ char j; for(j='0'; j<='1';j++){ //P – bỏ qua kiêm tra b[i]=j; if(i==n) Out(b); else Try(i+1,b); } }

41 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.3. Phương pháp quay lui

Bit 1

2

3

4

0

0

0

0  0000

1  0001

1

0  0010

,

1  0011

1

0

0  0100

) b 1 ( y r T

1  0101

1

0  0110

1  0111

1

0

0

0  1000

1  1001

1

0  1010

1  1011

Mã giả void Try(int i, char b[]){ char j; for(j='0'; j<='1';j++){ //P – bỏ qua kiêm tra b[i]=j; if(i==n) Out(b); else Try(i+1,b); } }

1

0

0  1100

1  1101

1

0  1110

1  1111

42 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.3. Phương pháp quay lui

43 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp quay lui

Ví dụ 1

Liệt kê xâu nhị phân độ dài n

Kết quả

Chương trình

Source Code

Result

44 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.3. Phương pháp quay lui

Ví dụ 2

Ví dụ 2

 Liệt kê các hoán vị của tập X = {1,2,…,n}.

𝑗 𝑐ℎư𝑎 𝑐ℎọ𝑛 𝑗 đã đượ𝑐 𝑐ℎọ𝑛

 Sử dụng mảng b b = { b[1], b[2],…, b[n]} b[j] = 1 , 0 ,

 Biểu diễn hoán vị dạng s1 s2 ... sn si ∈ X , sp ≠ sq , p ≠ q.  Try(i,…) - xác định si  D = {0,1,…,n}  Chấp nhận j ∈ 𝐷 nếu j chưa

 Khởi tạo b[j] = 1, ∀𝑗 ∈ 𝑋  i = n - được 1 cấu hình ∈ 𝑄

được chọn.

45 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.3. Phương pháp quay lui

Ví dụ 2

 Liệt kê các hoán vị của tập X = {1,2,…,n}.

 Biểu diễn hoán vị dạng s1 s2 ... sn si ∈ X , sp ≠ sq , p ≠ q.  Try(i,…) - xác định si

Mã giả void Try(int i,int b[],int s[]){ int j; for(j=1;j<=n;j++){ if(b[j]==1){ s[i]=j; b[j]=0; if(i==n) Out(s); else Try(i+1,b,s); b[j]=1; } } }

46 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.3. Phương pháp quay lui

47 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.3. Phương pháp quay lui

48 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp sinh

Ví dụ 2

Liệt kê hoán vị của tập n phần tử

Kết quả

Chương trình

Source Code

Result

49 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.3. Phương pháp quay lui

Ví dụ 3

Ví dụ 3

 Liệt kê tất cả các cách xếp 8 quân Hậu trên bàn cờ 8x8 sao cho chúng không ăn được nhau.

 Đánh số cột từ 1.. 8  Đánh số hàng từ 1.. 8  Biểu diễn cách xếp: x1 x2 … x8  xi được xếp ở hàng i  D = {1,…,8}

 xi= j : Hậu thứ i được

xếp vào cột j  j được chấp nhận nếu ô

(i,j) được tự do

50 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.3. Phương pháp quay lui

Ví dụ 3

Ví dụ 3

 Mảng a – quản lý cột a = { a[1], …, a[8]}

1 , 𝑐ộ𝑡 𝑗 𝑡ự 𝑑𝑜

 ô (i,j) được tự do  Quản lý cột  Quản lý đường chéo thuận  Quản lý đường chéo

a[j] =

0 ,

𝑐ộ𝑡 𝑗 đã 𝑐ℎ𝑖ế𝑢

nghịch

51 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.3. Phương pháp quay lui

Ví dụ 3:

Ví dụ 3  Mảng b – quản lý đường

 Quản lý đường chéo thuận

chéo thuận

b = { b[2], …,b[16]}  b[k]=

1 , đ𝑐 𝑐ℎ𝑢ậ𝑛 𝑘 𝑡ự 𝑑𝑜

0 ,

đ𝑐 𝑡ℎ𝑢ậ𝑛 𝑘 đã 𝑐ℎ𝑖ế𝑢

52 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.3. Phương pháp quay lui

Ví dụ 3:

Ví dụ 3

 Mảng c – quản lý đường

 Quản lý đường chéo nghịch

chéo nghịch

c = { c[-7], …,b[7]}  c[k]=

1 , đ𝑐 𝑛𝑔ℎị𝑐ℎ 𝑘 𝑡ự 𝑑𝑜

0 ,

đ𝑐 𝑛𝑔ℎị𝑐ℎ 𝑘 đã 𝑐ℎ𝑖ế𝑢

53 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.3. Phương pháp quay lui

Ví dụ 3:

Ví dụ 3

1

2

3

4

5

6

7

8

X1

X2

 Khởi tạo: ∀ 𝑖, 𝑘 aj =1&& bk=1&& ck =1

X3

X4

 j được chấp nhận khi aj ==1&& bi+j==1 && ci-j ==1

X5

X6

 Try (i,.. ) – tìm cột đặt con

X7

X8

hậu ở hang i

54 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.3. Phương pháp quay lui

55 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.3. Phương pháp quay lui

56 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.3. Phương pháp quay lui

57 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

5.2. Phương pháp quay lui

Ví dụ 3 Liệt kê cách xếp hậu

Kết quả

Chương trình

Result

Source Code x = (3 6 4 2 8 5 7 1)

58 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

Tóm lại

 Kỹ thuật sinh:

(1) Xác định trạng thái đầu của bài toán. (2) Xác định trạng thái kết thúc. (3) Xác định một thứ tự cho các trạng thái. (4) Tìm giải thuật đi từ trạng thái này sang trạng thái khác.

 Kỹ thuật quay lui:

59 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

(1) Tại 1 thời điểm, chỉ xét thành phần thứ i của cấu hình (2) Với mọi trị j trong miền trị của thành phần này 2.1- Nếu chọn được 1 trị hợp lệ thì Gán xi = j Xử lý cấu hình ở thành phần thứ i+1 Nếu i=0 thì bài toán không có lời giải.

Bài Tập

1. Liệt kê nghiệm nguyên của pt x1 + x2 + x3 =

15 với x1 ≥ 0 , x2 ≥ 0 , x3 ≥ 0.

2. Liệt kê số chuổi có độ dài 3 ký tự xyz với x ∈ { a,b,c}, y ∈ { d,e}, z ∈ { m,n,t} 3. Viết lại các bài mẫu về giải thuật quay lui

nhưng ghi kết qủa lên file.

60 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

Bài Tập

Cấu hình ban đầu: trị đầu tiên của mỗi miền trị

Dùng thứ tự từ điển để so sánh:

Cách sinh:Lấy trị kế tiếp của mỗi miền trị theo cơ chế vòng tròn

adm < adn

Cấu hình cuối: trị cuối cùng của mỗi miền trị

x y z a d m a d n a d t a e m a e n a e t b d m b d n b d t b e m b e n b e t c d m c d n c d t c e m c e n c e t

61 Nguyễn Văn Hiệu, 2012, Discrete Mathematics

THAT’S ALL; THANK YOU

• WHAT NEXT? LÝ THUYẾT ĐỒ THỊ