OmDoc | Hàm Sinh Kế Tiếp - OmOmega

Có thể bạn quan tâm

Python

Python Cơ Bản

Mục lục
D1: Intro, Setup, Hello
D2: Cú pháp, TP, Kiểu
D3: Cấu trúc điều khiển, Hàm
D4: Mod, P, Exception
D5: Numpy, Pandas, Plt
D6: Exercises

Python Ứng Dụng

D8: OOP
D9: RE, File thông dụng
D10: Dữ liệu ảnh
D11: Database
D12: Đa luồng, Socket
D13: PyQt
D14: Django
D15: Exercises

Machine Learning

Python với ML&DL

Mục lục
D18: Intro AI, ML
D19: Đại số, giải tích, XS
D20: K-means, KNN
D21: Regression, PLA
D22: Random Forest, SVM
D23: Neural Network
D24: Deep Learning, CNN
D25: OD-Segmentation
D26: Xử lý Tiếng Việt
D27: RNN, Text Classification

ML, Deep Learning

D1: Series Forecasting
D2: Seq2Seq with Attention
D3: Text Classify with BERT

Bài viết

Đo lường Model
BERT4Rec trong RS
Bayesian trong ML
BiLSTM Knowledge Tracing

Data Science

Data Science Python

Mục lục

Bài viết

Rough Set
PCA

Basic

Toán học trong KHMT

Toán Rời Rạc
Hàm sinh kế tiếp
Đại số Boole
Đại số Mệnh đề
Đồ Thị
Đại số tuyến tính
Đạo hàm

An toàn & Bảo mật TT

Tổng hợp Q&A

Tổng hợp

Vấn đề tự lập thân

Tài liệu tham khảo

Chuyên đề

Python
Natural Language Processing
An toàn & Bảo mật TT
Phương pháp NCKH
Triết học
Toán học trong KHMT
Khoa học dữ liệu
Trí tuệ nhân tạo

Tải ứng dụng OmOmega

Quét mã QR để tải ứng dụng (sử dụng camera của điện thoại)

iOS
Android

Quét mã QR hoặc truy cập App Store

Quét mã QR hoặc truy cập Google Play

Đóng None

Hàm sinh kế tiếp

Tác giả: Từ Nghĩa

Với sự phát triển “siêu to khổng lồ” của mạng Neuron (Neural Network) khi đi nghiên cứu LSTM với model Sequence generation hay Sequence to sequence trong bài toán tự sinh câu tự nhiên cho các ứng dụng trả lời tự động, tóm tắc văn bản, auto caption … Liên quan tới các loại “sinh sinh” làm mình hồi tưởng lại một kiến thức đã học trong toán rời rạc đó là hàm sinh kế tiếp, nghe tên nó có chút liên quan với công nghệ sinh câu phải không các bạn

Cụ thể như thế nào, bài viết này mình sẽ nhắc lại hàm sinh kế tiếp để ôn lại kỷ niệm thời đại học.

Giới thiệu:

Trong bài toán liệt kê như:

+ Liệt kệ danh sách các chuỗi nhị phân có độ dài bằng n.

+ Liệt kê các cặp thi đấu trong danh sách có 5 đội bóng.

+ Liệt kê các cách đi từ điểm A đến điểm D sao cho không qua điểm C (với một đồ thị đã cho).

…

Mình sẽ nhắc lại 2 nguyên tắc trong bài toán liệt kê:

+ Nguyên tắc 1: Các cấu hình không được trùng lặp

+ Nguyên tắc 2: Không bỏ sót cấu hình

Để giải các bài toán liệt kê tổ hợp này, trong lập trình chúng ta thường dùng hai cách là quay lui (đệ quy) và hàm sinh kế tiếp.

* Với hàm sinh kế tiếp, chúng ta cần xây dựng thuật toán từ một cấu hình đang có sinh ra một cấu hình kế tiếp của nó.

Như vậy để áp dụng thuật toán sinh kế tiếp, bài toán cần phải xác định:

+ Cấu hình đầu tiên và cấu hình cuối cùng (việc này thường khá đơn giản)

+ Quy tắc sinh dãy kế tiếp:

Tuỳ thuộc vào yêu cầu bài toán. Thông thường cấu hình tiếp theo là cấu hình thoả mãn và liền kề với cấu hình trước nó với các phần tử có thay đổi theo thứ tự từ trước ra sau, từ nhỏ tới lớn. ( phức tạp hơn ý thứ nhât )

Thông qua phần mô tả ở trên, thuật toán sinh kế tiếp được cài đặt dạng như sau:

""" Input: curr: cấu hình hiện tại m : số lượng phần tử trong cấu hình thông tin không gian liên quan Output: next_curr: cấu hình kế tiếp """ def next_generate([cấu hình hiện tại], [thông tin không gian]): if [cấu hình là cuối cùng]: return [cấu hình hiện tại] # tìm các vị trí phần tử sẽ thay đổi trong cấu hình hiện tại # thay đổi các phần tử trong cấu hình hiện tại để tạo ra cấu hình kế tiếp return [cấu hình kế tiếp]

Khá đơn giản phải không nào

Bây giờ chúng ta sẽ thử làm một số ví dụ cụ thể để hiểu rõ hơn và có cái nhìn ở mức ứng dụng của sinh kế tiếp nhé

Ứng dụng:

Bài 1

Bài Hello world của thuật toán sinh kế tiếp mình sẽ chọn là: Chuỗi nhị phân kế tiếp có độ dài n.

Input:

+ n: Độ dài của chuỗi nhị phân

vd: n = 4

+ curr: Chuỗi nhị phân hiện tại

vd: curr = [1, 0, 1, 1]

Output:

+ next_curr: Chuỗi nhị phân kế tiếp

vd next_curr = [1, 1, 0, 0]

Gọi $\ b_0b_1...b_{n-1} $ là một cấu hình | $\ b_i $ ∈ {0, 1} với i ∈ [0, n)

Chúng ta dễ dàng xác định:

+ Chuỗi đầu tiên: [0, 0, 0 ,0]

+ Chuỗi cuối cùng: [1, 1, 1, 1]

+ Quy luật sinh chúng ta xác định được ngay là chuỗi sau bằng chuỗi trước thêm 1 theo hệ nhị phân.

Đến đây các bạn sẽ thấy rất là đơn giản phải không nào, một dòng code là xong

next_curr = bin(0b1011 + 0b1)

Tuy nhiên, mình sẽ phân tích và xây dựng thuật toán ở mức tổng quát để có thể ứng dụng được vào những bài toán khó hơn nhé:

Cộng 1 vào chuỗi nhị phân chúng ta sẽ làm theo cách:

+ Đổi bit 0 ở phía phải cùng thành 1.

+ Đổi các bit 1 sau nó về 0 nếu có.

Phân tích xong, đến lúc cài đặt chương trình nào

def next_generate(curr, n): if set(curr) == {1}: # Nếu toàn bộ bit 1 thì đã là chuỗi cuối cùng return curr i = n - 1 # Bắt đầu từ vị trí phải cùng while curr[i]: # Trong khi bằng 1 thì đặt lại bằng 0 curr[i] = 0 i -= 1 curr[i] = 1 # Đặt vị trí 0 bên phải cùng về bằng 1 return curr # Trả về chuỗi kế tiếp if __name__ == '__main__': n = 3 curr = [1, 0, 1, 1] next_curr = next_generate(curr=curr, n=n) print(next_curr) # [1, 1, 0, 1]

Chuẩn hello world phải không các bạn

Bài 2

Lần này mình sẽ đưa ra một ví dụ mang tính ứng dụng thực tế hơn chút nhé:

Khi xem một trận bóng đá hay ví dụ U23 Châu Á chẳng hạn, một câu hỏi nhỏ đặt ra là coi hết trận này thì mình sẽ coi trận nào nữa (trận tiếp theo trong cùng bản đấu và bảng có 4 đội)

Bài toán khái quát của ví dụ này là: Tìm tổ hợp kế tiếp của k phần tử trong tập n phần. Đó là k = 2 và n = 4 phải không nào.

Chúng ta cùng đi phân tích bài toán.

Input:

+ n: Số lượng tập không gian phần tử

vd: n = 4

+ basket: Danh sách n phần tử

vd: basket = ['Triều Tiên', 'Việt Nam', 'UAE', 'Jordan']

+ k: độ dài của cấu hình.

vd: k = 2

+ curr: cấu hình hiện tại

vd: đang xem curr = ['Triều Tiên', 'Jordan']

Output:

+ next_curr: cấu hình kế tiếp

vd: tiếp theo có thể được xem next_curr = ['Việt Nam', 'UAE']

Theo luật lập cấu hình từ trái sang phải, từ nhỏ tới lớn thì chúng ta xác định được:

+ Cấu hình đầu tiên: ['Triều Tiên', 'Việt Nam']

+ Cấu hình cuối cùng: ['UAE', 'Jordan']

+ Quy luật sinh kế tiếp là cấu hình sau lớn hơn cấu hình trước theo chuỗi thứ tự chỉ số đại diện.

Gọi tập không gian bài toán S = {$\ {s_0, s_1, ..., s_{n-1}} $ }với a = {$\ a_0, a_1, ..., a_{n-1} $ } là chỉ số đại diện các phần tử của tập S và tổ hợp c = {$\ c_0, c_1, ..., c_{k-1} $ } với $\ c_i $ ∈ a:

+ $\ c_0 < c_1 < ... < c_{k-1} $

+ $\ c_i(c_i^0c_i^1...c_i^{k-1}) < c_j(c_j^0c_j^1...c_j^{k-1})$ với $\ i < j $

Trong bài này: s = ['Triều Tiên', 'Việt Nam', 'UAE', 'Jordan']

và a ={0 , 1 , 2, 3 }

Các tổ hợp sẽ là (0,1), (0,2), (0,3), (1,2), (1,3), (2,3)

Vậy khi sinh kế tiếp ta tìm cách thay đổi theo chiều tăng ưu tiên các phần tử từ phía bên phải cùng

Và thuật toán sinh tổ hợp kế tiếp sẽ thực hiện:

+ Tìm kiếm phần tử vị trí phía bên phải cùng (ci) còn có thể tăng được

$\ c_i = n - k + a_i $

+ Tăng phần tử $\ c_i $ đó lên 1

$ \ c_i += 1 $

+ Cài đặt lại các phần tử phía sau: $\ c_j $ (i < j) nếu có theo thứ tự tăng dần lên 1 bắt đầu từ $\ c_i $

$\ c_j = c_i + j - i $

Cài đặt thuật toán chạy thử nhé

def next_generate(n, basket, k, curr): pos = k - 1 while curr[pos] == basket[n - k + pos]: # Tìm vị trí phải cùng có thể tăng được pos -= 1 if pos < 0: # Không tìm thấy => là cấu hình cuối cùng return curr for j in range(pos, k): if j == pos: curr[j] = basket[basket.index(curr[j]) + 1] # tăng phần tử lại vị trí pos lên 1 else: curr[j] = basket[basket.index(curr[pos]) + j - pos] # cài đặt lại các phần tử theo sau return curr if __name__ == '__main__': n = 4 basket = ['Triều Tiên', 'Việt Nam', 'UAE', 'Jordan'] k = 2 curr = ['Triều Tiên', 'Jordan'] next_curr = next_generate(n=n, basket=basket, k=k, curr=curr) print(next_curr) # ['Việt Nam', 'UAE']

Kết quả đúng rồi phải không các bạn, nhưng chỉ đúng trong chương trình thôi còn thực tế thì tuỳ vào sự sắp xếp của ban tổ chức nhé

Kết luận

Trong bài toán liệt kê, sinh kế tiếp (next generation) và quay lui (backtracking) là những dạng thuật toán giúp chúng ta có thể liệt kê được tất cả các cấu hình.

Tuy nhiên khác với backtracking, next generation cho phép chúng ta có thể linh hoạt hơn khi sử dụng như trường hợp chỉ cần một vài cấu hình mong muốn chứ không phải toàn bộ, mặt dù thường cùng bài toán cài đặt với next generation khó hơn là so với trackbacking.

Tới đoạn này thì mình đoán các bạn cũng có câu trả lời cho câu hỏi “Next generation có liên quan gì đến bài toán sinh câu tự động” rồi :))

Chào thân ái các bạn và hẹn gặp lại

Tham khảo

+ [1] Nguyễn Đức Nghĩa và Nguyễn Tô Thành, Toán rời rạc, NXB Giáo dục, 1997.

Từ khóa » Sinh Kế Tiếp