Thuật toán sinh dữ liệu với Quy Hoạch Động

Quan hệ sinh dữ liệu và tiếp cận Quy hoạch động

Lê Đình Thanh

Chúng ta đã biết quy hoạch động (QHĐ) là một phương pháp giải toán rất hiệu quả một

khi nó được sử dụng. Đúng như tác giả Nguyễn Thanh Tùng - trong bài “Một số bài toán

quy hoạch động kinh điển”, Tạp chí Tin học và Nhà trường Số 1, Năm 2005- nhận xét:

điều khó nhất để giải một bài toán bằng QHĐ là biết rằng nó có thể giải theo QHĐ và tìm

được công thức QHĐ của nó. Nói cách khác, vấn đề khó nhất của việc giải một bài toán

QHĐ là tìm dấu hiệu nhận biết QHĐ và tìmquy luật quy hoạch dữ liệu của bài toán đó.

Trong bài báo này, tôi đưa ra một cách tiếp cận theo quan hệ sinh dữ liệu để giải quyết hai

vấn đề nói trên. Đây không phải là cách tiếp cận tối ưu nhưng nó giải quyết được một lớp

lớn các bài toán quy hoạch động.

Các góp ý xin gửi về địa chỉ: [email protected]

1. Quan hệ sinh dữ liệu tuyến tính và khả năng quy hoạch động

Nhận xét sau xuất phát từ chính định nghĩa về quy hoạch động:

Giả sử P là bài toán đang cần giải quyết trên mẫu dữ liệu D, và giả thiết từ D ta có thể tạo

ra các mẫu dữ liệu Di, (i = 1, 2...) là mẫu con của D và đồng dạng với D. Ví dụ, D là dãy số

tự nhiên và Di là các dãy con của nó, D là mã vạch có chiều dài L và Di là các mã vạch có

chiều dài nhỏ hơn L.

Cũng áp dụng yêu cầu của bài toán trên các mẫu Di ta được các bài toán Pi (i = 1, 2...) cùng

dạng với P và nhỏ hơn P. Pi là các bài toán con của P. Gọi Oi (i = 1, 2...) là dữ liệu được

sinh ra bởi Pi, và gọi O là dữ liệu được sinh ra bởi P. Đặt G = {O} U {Oi, i = 1, 2...}. Nếu

trên G ta lập được 2 quan hệ là quan hệ sinh và quan hệ thứ tự thì bài toán P có thể giải

quyết bằng QHĐ, trong đó quan hệ sinh là khả năng dữ liệu được sinh của một bài toán

này có thể tạo ra từ các dữ liệu sinh của các bài toán khác và quan hệ thứ tự là tính khả sinh

(hiểu theo nghĩa toán học).

Ta hình dung mỗi Oi hay O như một đỉnh của đồ thị và Oj là một trong các dữ liệu ra được

dùng để sinh Ok (Ok đứng sau Oj trong quan hệ thứ tự) được biểu diễn bằng một cung có

hướng từ đỉnh j đến đỉnh k, thì đồ thị được tạo là đồ thị có hướng, phi chu trình. Dữ liệu

được quy hoạch trên đồ thị bắt đầu từ các đỉnh không có cung vào. Khi một đỉnh đã được

xét (một bài toán con đã được giải quyết), ta xóa luôn các cung ra từ đỉnh đó. Một số đỉnh

mới lại trở thành đỉnh không có cung vào. Quá trình được lặp lại cho đến khi đỉnh tương

ứng với bài toán P được giải quyết.

Một trường hợp khác, từ D không tạo được các Di là con của D nhưng có thể tạo ra các bài

toán tương tự P trên D. Gọi các bài toán tương tự đó là Qj (j = 1,2...). Nếu trên các dữ liệu