[Thuật Toán] Phương Pháp Sinh ( Generation)

PHƯƠNG PHÁP SINH ( GENERATION )

phương pháp sinh ??? trước đây học khi mình đọc thấy cụm từ này mình thấy nó khá là "khó hiểu". vấn đề của chị em sao lại có mặt trong môn liên quan đến toán tin này nhỉ :/
nhưng sau khi học xong thì thấy nó có liên quan thật :V , nhưng mà không phải là liên quan theo nghĩa đen =)))
chúng ta sẽ tiếp cận với nó 1 cách tự nhiên nhất nhóe :3

* Cấu hình là gì ?

chúng ta sẽ xét ví dụ về bài toán tổ hợp sau :
giả sử mình có tập X ={1,2,3,4,5,6,7} gồm có 7 phần tử.
hãy liệt kê 1 số 1 số chỉnh hợp không lặp chập 5 của X.

ta dễ dàng nhận thấy 1 số chỉnh hợp không lặp chập 5 của 7 như là : 12345, 23456, 73241...
vậy thì mỗi bộ (12345), (23456),... được gọi là 1 cấu hình
đó, cấu hình về cơ bản nôm na chỉ là thế thôi :3  nó chỉ là 1 nghiệm thỏa mãn yêu cầu đề bài của bài toán tổ hợp. mỗi cấu hình đều có các phần tử. ví dụ cấu hình 12345 có các phần tử 1,2,3,4,5.

* Phương pháp sinh dùng để làm gì ?

mình cũng sẽ ví dụ luôn cho dễ hiểu. với dữ liệu đề như trên, nếu mình muốn liệt kê tất cả các chỉnh hợp không lặp chập 5 của X ( hay gọi là liệt kê tất cả các cấu hình của bài toán) thì phải làm như thế nào ?
chày cối đếm tay và viết vào máy ? :D điều này có thể thực hiện nếu chỉ có ít phần tử chứ cho liệt kê mà tập có 30 phần tử thì nổ não :D
vậy cách giải quyết ví dụ là gì ? câu trả lời là phương pháp sinh.

* vậy mục đích của phương pháp sinh là gì ? 

phương pháp sinh dùng có thể áp dụng để giải bài toán liệt kê tổ hợp, hay nói cách khác là liệt kê các cấu hình của bài toán.

* phương pháp sinh hoạt động như thế nào ?

rất đơn giản, nó sẽ "đẻ" ra các cấu hình tiếp theo từ các cấu hình trước đó cho đến khi nào hết nghiệm thì thôi. :D
ví dụ: trong ví dụ trên, từ cấu hình 123456 PPS sẽ đẻ ra tiếp cấu hình 23456 cho đến khi hết nghiệm của bài toán

* điều kiện để áp dụng được phương pháp sinh : 

có 2 điều kiện để sử dụng được phương pháp sinh :
– Xác định được trật tự các nghiệm. Biết được nghiệm đầu và nghiệm cuối cùng.
– Xây dựng được thuật toán từ một nghiệm (cấu hình) chưa phải là nghiệm cuối cùng ta đều sinh ra một cấu hình đứng sau nó.

cấu trúc của thuật toán sinh như sau :

while(chưa phải là cấu hình cuối cùng){
<đưa ra cấu hình hiện tại>;
<sinh cấu hình kế tiếp>;
}

như vậy là đã xong phần giới thiệu về phương pháp sinh :D
bài sau mình sẽ chi tiết phương pháp này vào 3 thuật toán cơ bản & đặc trưng của phương pháp sinh. đó là thuật toán sinh nhị phân, sinh hoán vị & sinh các tập con của 1 tập.
bài viết chắc chắn còn nhiều thiếu sót rất mong bạn đọc góp ý qua email : trieuhiepptit@gmail.com
Thanks for reading !