DP_part1

DP_quy hoạch động

Lời mở đầu

Đây là blog đầu tiên của tôi nên không tránh khỏi sai sót, mong bạn đọc thông cảm và góp ý với

mình ạ. ^^

Tin học mới xuất hiện, nhưng tầm ảnh hưởng của nó là vô cùng lớn. Thời đại nay, đâu đâu cũng thấy tin học, từ những chiếc máy tính để bàn, đến các công cụ, các phần mềm lập trình như C, C++ , Pascal, Python, VC , ... , hay lớn hơn nữa chính là mạng xã hội :facebook, twitter ,instagram,.. Trong bài viết này mình sẽ đề cập đến 1 vấn đề như hạt cát nhưng mang tính nền móng của tin
học, đó là quy hoạch động 

* Lưu ý: Ngôn ngữ minh họa của mình là C++.

Tổng quan:Mình sẽ giới thiệu cho các bạn theo 2 phần chính mang tính SGK.

                + Phần I: Khái niệm cơ bản và tính lý thú của DP.

                + Phần II: các bài toán cơ bản và áp dụng

Tại phần I mình sẽ đề cập đến khái niệm cơ bản và bản chất của DP. Mình sẽ không khoét xâu phần này, các bạn có thể tìm hiểu thêm trên mạng, nó vốn dĩ rất nhiều.

Còn phần II mình sẽ đề cập đến các bài toán cơ bản : LIS , LCS , coin changes , biến đổi xâu , ... và các biến thể của nó.

Chúc các bạn có buổi khám phá vui vẻ !!!

                                                                                                 

-------------------------------------------------------------------------------------------------------

Mục lục: < Còn sửa đổi > 

Phần I: Khái niệm cơ bản và tính lý thú của DP

                I.1: Khái niệm cơ bản và thông tin chung.

                I.2: Từ đệ quy đến quy hoạch động

                I.3: Ưu và nhược.

Phần II: Các bài toán và áp dụng.

            II.1: LIS – Khởi đầu của DP

            II.2: LCS- Dãy con chung dài nhất

            II.3: Coin change – Đổi xu.

            II.4: Bài toán biến đổi xâu.

           II.5: Kho báu kia kìa .

            II.6: Nhiều thông tin hơn nữa….

--------------------------------------------------------------------------------------------------------

Phần I : Khái niệm cơ bản và tính lý thú của DP.

I.1:  Khái niệm cơ bản và thông tin chung.

“Trong ngành khoa học máy tính, quy hoạch động là một phương pháp giảm thời gian chạy của các thuật toán thể hiện các tính chất của các bài toán con gối nhau (overlapping subproblem) và cấu trúc con tối ưu (optimal substructure).

Nhà toán học Richard Bellman đã phát minh phương pháp quy hoạch động vào năm 1953. Ngành này đã được thành lập như là một chủ đề về kỹ nghệ và phân tích hệ thống đã được tổ chức IEEE thừa nhận.”

 _wiki.

Người ta thường sử dụng quy hoạch động để giải các bài toán tối ưu. Bài giải tối ưu là lời giải “hoàn hảo” cho bài toán con để từ đó giải bài toán cha.Bài toán tối ưu có thể là tìm min , max ,không hẳn như trong toán học là tìm min max của một biểu thức, mà còn rộng hơn là 1 con đường, 1 đường đi, 1 quá trình tiêu tiền, …

I.2: Từ đệ quy đến quy hoạch động

 Ta sẽ xét 1 bài toán kinh điển. Dãy Fibonacci

Đề bài:

F[0] = F[1] = 1;

N >= 2 F[n] = F[n-1] + F[n-2];
Tính F[n]

Tất nhiên, ta có thể tìm ra cách giải dễ ràng bằng đệ quy, như sau:

Source code:

          int fibonacci(int n){

                    if (n < 2) return 1;

                    return fibonacci(n-1) + fibonacci(n-2);

}

Bằng cách làm này: từ F[n] ta sẽ tìm đến F[n-1] , F[n-2] xong tìm từ từ xuống F[1] , F[0];

Ví Dụ :tính F[4]

----------------------------------------------------------------------------------------------------          

Với cách làm trên, chúng ta duyệt bị lặp rất nhiều lần  à rất tốn thời gian.Tất nhiên các bạn đang bảo rằng : “ Cách quái gì đây, rõ ràng mình chỉ cần lưu vào mảng xong tính dần là được.”. Vâng , cái cách tính dần của bạn chính là quy hoạch động, quy hoạch động chân chính đấy ạ. Và cách làm trên được mô tả hết sức đơn giản , bằng việc tận dụng mảng F[] để lưu kết quả khi mình tính xong, để tránh lặp lại.

Source code:

f[1] = f[0] = 1

for (int i=2;i<=n;++i){

    f[i] = f[i-1] + f[i-2];

}

Với cách làm trên, ta tiết kiệm được thời gian, đáng kể. Rõ ràng quy hoạch động cũng chỉ là đệ quy, nhưng lại là đệ quy thông minh thôi !!!.

Nói chung quy hoạch động có thể giải theo 3 bước chính

1.    Chia bài toán thành các bài toán con nhỏ hơn.

2.    Giải các bài toán này một cách tối ưu bằng cách sử dụng đệ quy quy trình ba bước này.

3.    Sử dụng các kết quả tối ưu đó để xây dựng một lời giải tối ưu cho bài toán ban đầu.

Trong trường hợp kinh điển của dãy Fibonacci trên, bài toán nhỏ hơn chính là F[i] = F[i-1] + F[i-2] và ta sử dụng nó lặp đi lặp lại cho đến khi tính được F[n].

Vừa rồi, tôi vừa chỉ ra 2 cách tiếp cận quy hoạch động:

·         top-down (Từ trên xuống): Bài toán được chia thành các bài toán con, các bài toán con này được giải và lời giải được ghi nhớ để phòng trường hợp cần dùng lại chúng. Đây là đệ quy và lưu trữ được kết hợp với nhau. ( cách 1)

·         bottom-up (Từ dưới lên): Tất cả các bài toán con có thể cần đến đều được giải trước, sau đó được dùng để xây dựng lời giải cho các bài toán lớn hơn. Cách tiếp cận này hơi tốt hơn về không gian bộ nhớ dùng cho ngăn xếp và số lời gọi hàm. Tuy nhiên, đôi khi việc xác định tất cả các bài toán con cần thiết cho việc giải quyết bài toán cho trước không được trực giác lắm. (cách 2)

-----------------------------------------------------------------------------------------------------

I.3: Ưu và nhược.

* So với đệ quy, quy hoạch động nhiều khi có nhiều ưu điểm vượt trội

          + Tiết kiệm thời gian duyệt

          +Cách mạng hóa trong việc code

          + Giảm thiểu việc gọi hàm

          + Dễ kiểm soát hơn

Tôi chỉ nói là nhiều khi, chứ không có nghĩa là tất cả, trong 1 số trường hợp , nếu DP không đúng cách, hoặc là lạm dụng dp thì có thể dẫn tới chạy lặp quá nhiều à chậm hơn cả đệ quy.

*Cái gì cũng có 2 mặt , tất nhiên DP cũng không tránh khỏi những xu thế chung đó.

Sau đây là 1 vài nhược điểm:

          + Tiêu tốn bộ nhớ (Vd như bài toán Fibonacci trên cách 1 thậm chí còn không tốn bộ nhớ , còn các 2 cần một mảng F[] )

          + Việc đưa ra lời giải bằng DP nhiều lúc vô cùng khó khăn.

Đến đây, chúng ta đã kết thúc phần I – phần theo mình nghĩ là tính chất minh họa, nhưng lại quan trọng và cần thiết cho phần II sắp tới. Hi vọng các bạn đón đọc.

Mình xin cảm ơn