Báo Cáo Thuật toán tìm xâu con chung lớn nhất bằng quy hoạch động

I. Giới thiệu phương pháp thiết kế thuật toán bằng quy hoạch động
Quy hoạch động là kỹ thuật từ dưới lên (bottom – up). Chúng ta xuất phát từ những trường hợp riêng đơn giản nhất của bài toán, thường là thấy ngay nghiệm của chúng. Sau đó kết hợp nghiệm của chúng, ta được nghiệm của bài toán con cỡ lớn hơn. Rồi lại kết hợp nghiệm của bài toán con này để được nghiệm của bài toán lớn hơn nữa, và cứ thế tiếp tục cho đến khi nhận được nghiệm của bài toán đã cho.
Tư tưởng cơ bản của phương pháp quy hoạch động là trong quá trình “đi từ dưới lên” ta sử dụng một bảng để lưu giữ lời giải của các bài toán con đã giải. Khi giải một bài toán con cần đến nghiệm của bài toán con cỡ nhỏ hơn, ta chỉ cần tìm trong bảng, không cần phải giải lại. Chính vì thế mà các thuật toán được thiết kế bằng quy hoạch động sẽ rất có hiệu quả.
Để giải một bài toán bằng quy hoạch động, chúng ta cần phải tiến hành những công việc sau:
· Tìm nghiệm của bài toán con (các trường hợp riêng) đơn giản nhất
· Tìm ra các công thức (hoặc quy tắc) xây dựng nghiệm của bài toán con thông qua nghiệm của các bài toán con cỡ nhỏ hơn.
· Tạo ra một bảng để lưu giữ các nghiệm của các bài toán con. Sau đó tính nghiệm của các bài toán con theo các công thức đã tìm ra và lưu vào bảng.
· Từ bảng đã làm đầy tìm cách xây dựng nghiệm của bài toán.

II. Thuật toán tìm xâu con chung lớn nhất bằng quy hoạch động
1. Phát biểu bài toán
Cho hai xâu văn bản a có độ dài là m ký tự và b có độ dài n ký tự.
a=a[SUB]1[/SUB]a[SUB]2[/SUB] a[SUB]m[/SUB]
b=b[SUB]1[/SUB]b[SUB]2 [/SUB]b[SUB]n[/SUB]
Chúng ta tìm xâu xâu con chung lớn nhất giữa xâu a và b là xâu c=c[SUB]1[/SUB]c[SUB]2 [/SUB]c[SUB]k[/SUB]
Ví dụ:
a=”van ban tieng viet”
b=”van hoa”
Ta phải tìm được xâu con con chung là c=”van a”