A. KỸ THUẬT CHIA ĐỂ TRỊ

1. Nội dung

Đây là một kỹ thuật rất quan trọng được áp dụng rộng rãi nhất để thiết kế giải thuật cho một lớp lớn các bài toán. Nội dung của nó có thể được phát biểu như sau:

  • Cần phải giải bài toán có kích thước n: kích thước (hay độ lớn của bài toán) thông thường là kích thước dữ liệu của bài toán.
  • Tìm cách phân chia bài toán ban đầu thành một số bài toán con đồng dạng với bài toán ban đầu có kích thước nhỏ hơn n. Đối với từng bài toán con, ta cũng sẽ áp dụng kỹ thuật này để chia chúng thành các bài toán con nhỏ hơn nữa. Quá trình phân chia này sẽ cho chúng ta các bài toán mà lời giải của chúng là hiển nhiên hay rất dễ dàng thực hiện. Ta gọi chúng là các bài toán cơ sở.
  • Tổng hợp lời giải của các bài toán con ta có được lời giải của bài toán ban đầu.

Chú ý:

  • Bước phân chia càng đơn giản thì bước tổng hợp càng phức tạp và ngược lại.
  • Đối với một số bài toán, việc tổng hợp lời giải của các bài toán con là không cần thiết vì nó được bao hàm trong bước phân chia bài toán. Do đó khi giải các xong bài con thì bài toán ban đầu cũng đã được giải xong.
  • Kỹ thuật này sẽ cho chúng ta một giải thuật đệ quy mà việc xác định độ phức tạp đã được trình bày trong phần đánh giá độ phức tạp của giải thuật.

2. Áp dụng

– Bài toán nhân các số nguyên lớn

– Xếp lịch thi đấu thể thao

– Bài toán con cân bằng

B. KỸ THUẬT “THAM ĂN”

1. Nội dung

– Đây là một kỹ thuật được dùng nhiều để giải các bài toán tối ưu tổ hợp. Áp dụng kỹ thuật này tuy không cho chúng ta lời giải tối ưu nhưng sẽ cho một lời giải “tốt”; bù lại chúng ta được lợi khá nhiều về thời gian.

– Tham ăn hiểu một cách dân gian là: trong một mâm có nhiều món ăn, món nào ngon nhất ta sẽ ăn trước và ăn cho hết món đó thì chuyển sang món ngon thứ hai, lại ăn hết món ngon thứ hai này và chuyển sang món ngon thứ ba, …

– Kỹ thuật tham ăn thường được vận dụng để giải bài toán tối ưu tổ hợp bằng cách xây dựng một phương án X. Phương án X được xây dựng bằng cách lựa chọn từng thành phần Xi của X cho đến khi hoàn chỉnh (đủ n thành phần). Với mỗi Xi, ta sẽ chọn Xi tối ưu. Với cách này thì có thể ở bước cuối cùng ta không còn gì để chọn mà phải chấp nhận một giá trị cuối cùng còn lại.

– Áp dụng kỹ thuật tham ăn sẽ cho một giải thuật thời gian đa thức, tuy nhiên nói chung chúng ta chỉ đạt được một phương án tốt chứ chưa hẳn là tối ưu.

2. Áp dụng

– Tối ưu tổ hợp

– Trả tiền của máy ATM

– Người đi giao hàng

– Cái ba lô

C. KỸ THUẬT NHÁNH CẬN

1. Nội dung

Với các bài toán tìm phương án tối ưu, nếu chúng ta xét hết tất cả các phương án thì mất rất nhiều thời gian, nhưng nếu sử dụng phương pháp tham ăn thì phương án tìm được chưa hẳn đã là phương án tối ưu. Nhánh cận là kỹ thuật xây dựng cây tìm kiếm phương án tối ưu, nhưng không xây dựng toàn bộ cây mà sử dụng giá trị cận để hạn chế bớt các nhánh.

Cây tìm kiếm phương án có nút gốc biểu diễn cho tập tất cả các phương án có thể có, mỗi nút lá biểu diễn cho một phương án nào đó. Nút n có các nút con tương ứng với các khả năng có thể lựa chọn tập phương án xuất phát từ n. Kỹ thuật này gọi là phân nhánh.

Vói mỗi nút trên cây ta sẽ xác định một giá trị cận. Giá trị cận là một giá trị gần với giá của các phương án. Với bài toán tìm min ta sẽ xác định cận dưới còn với bài toán tìm max ta sẽ xác định cận trên. Cận dưới là giá trị nhỏ hơn hoặc bằng giá của phương án, ngược lại cận trên là giá trị lớn hơn hoặc bằng giá của phương án.

Ðể dễ hình dung ta sẽ xét hai bài toán quen thuộc là bài toán TSP và bài toán cái ba lô.

2. Áp dụng

– Người đi giao hàng

– Bài toán cái ba lô

D. QUY HOẠCH ĐỘNG

1. Nội dung kỹ thuật

Kỹ thuật chia để trị thường dẫn chúng ta tới một giải thuật đệ quy. Trong các giải thuật đó, có thể có một số giải thuật có độ phức tạp thời gian mũ. Tuy nhiên, thường chỉ có một số đa thức các bài toán con, điều đó có nghĩa là chúng ta đã phải giải một số bài toán con nào đó nhiều lần. Ðể tránh việc giải dư thừa một số bài toán con, chúng ta tạo ra một bảng để lưu trữ kết quả của các bài toán con và khi cần chúng ta sẽ sử dụng kết quả đã được lưu trong bảng mà không cần phải giải lại bài toán đó. Lấp đầy bảng kết quả các bài toán con theo một quy luật nào đó để nhận được kết quả của bài toán ban đầu (cũng đã được lưu trong một số ô nào đó của bảng) được gọi là quy hoạch động (dynamic programming). Trong một số trường hợp, để tiết kiệm ô nhớ, thay vì dùng một bảng, ta chỉ dùng một véctơ.

Có thể tóm tắt giải thuật quy hoạch động như sau:

§         Tạo bảng bằng cách:

o        Gán giá trị cho một số ô nào đó.

o        Gán trị cho các ô khác nhờ vào giá trị của các ô trước đó.

§         Tra bảng và xác định kết quả của bài toán ban đầu.

2. Ưu và nhược điểm

Ưu điểm của phương pháp quy hoạch động là:

  • Chương trình thực hiện nhanh do không phải tốn thời gian giải lại một bài toán con đã được giải.
  • Kỹ thuật quy hoạch động có thể vận dụng để giải các bài toán tối ưu, các bài toán có công thức truy hồi.

Phương pháp quy hoạch động sẽ không đem lại hiệu quả trong các trường hợp sau:

  • Không tìm được công thức truy hồi.
  • Số lượng các bài toán con cần giải quyết và lưu giữ kết quả là rất lớn.
  • Sự kết hợp lời giải của các bài toán con chưa chắc cho ta lời giải của bài toán ban đầu.

3. Áp dụng

– Tính toán tổ hợp

– Tiết kiệm bộ nhớ

– Cái ba lô

– TSP

– Dãy con đơn điệu tăng dài nhất

E. THUẬT TOÁN QUY LUI

1. Phát biểu

Kỹ thuật quay lui (backtracking) như tên gọi của nó, là một quá trình phân tích đi xuống và quay lui trở lại theo con đường đã đi qua. Tại mỗi bước phân tích chúng ta chưa giải quyết được vấn đề do còn thiếu cứ liệu nên cứ phải phân tích cho tới các điểm dừng, nơi chúng ta xác định được lời giải của chúng hoặc là xác định được là không thể (hoặc không nên) tiếp tục theo hướng này. Từ các điểm dừng này chúng ta quay ngược trở lại theo con đường mà chúng ta đã đi qua để giải quyết các vấn đề còn tồn đọng và cuối cùng ta sẽ giải quyết được vấn đề ban đầu.

Ở đây chúng ta sẽ xét 3 kỹ thuật quay lui: “vét cạn” là kỹ thuật phải đi tới tất cả các điểm dừng rồi mới quay lui. “Cắt tỉa Alpha-Beta” và “Nhánh-Cận” là hai kỹ thuật cho phép chúng ta không cần thiết phải đi tới tất cả các điểm dừng, mà chỉ cần đi đến một số điểm nào đó và dựa vào một số suy luận để có thể quay lui sớm. Các kỹ thuật này sẽ được trình bày thông qua một số bài toán cụ thể.

2. Áp dụng

– Cây biểu thức toán học

– Cây trò chơi

– Sinh chuỗi nhị phân

– Sinh hoán vị

– Phân tích một số thành tổng các số nhỏ hơn

F. KỸ THUẬT CẮT TỈA ALPHA-BETA

1. Kỹ thuật cắt tỉa Alpha-Beta (Alpha-Beta Pruning)

Trong giải thuật vét cạn ở trên, ta thấy để định trị cho một nút nào đó, ta phải định trị cho tất cả các nút con cháu của nó, và muốn định trị cho nút gốc ta phải định trị cho tất cả các nút trên cây. Số lượng các nút trên cây trò chơi tuy hữu hạn nhưng không phải là ít. Chẳng hạn trong cây trò chơi ca rô nói trên, nếu ta có bàn cờ bao gồm n ô thì có thể có tới  n! nút trên cây (trong trường hợp trên là 9!). Ðối với các loại cờ khác như cờ vua chẳng hạn, thì số lượng các nút còn lớn hơn nhiều. Ta gọi là một sự bùng nổ tổ hợp các nút.

Chúng ta cố gắng tìm một cách sao cho khi định trị một nút thì không nhất thiết phải định trị cho tất cả các nút con cháu của nó. Trước hết ta có nhận xét như sau:

Nếu P là một nút MAX và ta đang xét một nút con Q của nó (dĩ nhiên Q là nút MIN). Giả sử Vp là một giá trị tạm của P, Vq là một giá trị tạm của Q và nếu ta có Vp ≥ Vq thì ta không cần xét các con chưa xét của Q nữa. Vì nếu có xét thì giá trị của Q cũng sẽ nhỏ hơn hoặc bằng Vq và do đó không ảnh hưởng gì đến Vp. Tương tự nếu P là nút MIN (tất nhiên Q là nút MAX) và Vp ≤ Vq thì ta cũng không cần xét đến các con chưa xét của Q nữa. Việc không xét tiếp các con chưa được xét của nút Q gọi là việc cắt tỉa Alpha-Beta các con của nút Q.

Trên cơ sở nhận xét đó, ta nêu ra quy tắc định trị cho một nút không phải là nút lá trên cây như sau:

  • §         Khởi đầu nút MAX có giá trị tạm là -¥ và nút MIN có giá trị tạm là ¥.
  • §         Nếu tất cả các nút con của một nút đã được xét hoặc bị cắt tỉa thì giá trị tạm của nút đó trở thành giá trị của nó.
  • §         Nếu một nút MAX n có giá trị tạm là V1 và một nút con của nó có giá trị là V2 thì đặt giá trị tạm mới của n là max(V1,V2). Nếu n là nút MIN thì đặt giá trị tạm mới của n là min(V1,V2).
  • §         Vận dụng quy tắc cắt tỉa Alpha-Beta nói trên để hạn chế số lượng nút phải xét.

2. Ví dụ

Vận dụng quy tắc trên để định trị cho nút A của cây trò chơi trong ví dụ trước.

A là nút MAX, vì A không phải là nút lá nên ta gán giá trị tạm là -¥, xét B là con của A, B là nút lá nên giá trị của nó là giá trị đã được gán 1, giá trị tạm của A bây giờ là max(-¥,1) = 1. Xét con C của A, C là nút MIN, giá trị tạm lúc đầu của C là ¥.  Xét con E của C, E là nút MAX, giá trị tạm của E là -¥. Xét con I của E, I là nút lá nên giá trị của nó là 0. Quay lui lại E, giá trị tạm của E bây giờ là max(-¥,0) = 0. Vì E chỉ có một con là I đã xét nên giá trị tạm 0 trở thành giá trị của E. Quay lui lại C, giá trị tạm mới của C là min(¥,0) = 0. A là nút MAX có giá trị tạm là 1, C là con của A, có giá trị tạm là 0, 1>0 nên ta không cần xét con F của C nữa. Nút C có hai con là E và F, trong đó E đã được xét, F đã bị cắt, vậy giá trị tạm 0 của C trở thành giá trị của nó. Sau khi có giá trị của C, ta phải đặt lại giá trị tạm của A, nhưng giá trị tạm này không thay đổi vì max(1,0) = 1. Tiếp tục xét nút D, D là nút MIN nên giá trị tạm là ¥, xét nút con G của D, G là nút MAX nên giá trị tạm của nó là -¥, xét nút con J của G. Vì J là nút lá nên có giá trị 0. Quay lui lại G, giá trị tạm của G bây giờ là max(-¥,0) = 0 và giá trị tạm này trở thành giá trị của G vì G chỉ có một con J đã xét. Quay lui về D, giá trị tạm của D bây giờ là min(¥,0) = 0. Giá trị tạm này của D nhỏ hơn giá trị tạm của nút A MAX là cha của nó nên ta cắt tỉa con H chưa được xét của D và lúc này D có giá trị là 0. Quay lui về A, giá trị tạm của nó vẫn không thay đổi, nhưng lúc này cả 3 con của A đều đã được xét nên giá trị tạm 1 trở thành giá trị của A.

Ta thu được kết quả giống như giải thuật vét cạn mà không cần phải xét hết tất cả các nút trong cây.

Tổng kết

Trong các kỹ thuật được trình bày trong chương này, kỹ thuật chia để trị là kỹ thuật cơ bản nhất. Hãy chia nhỏ các bài toán để giải quyết nó!

Với các bài toán tìm phương án tối ưu, kỹ thuật “tham ăn” giúp chúng ta nhanh chóng xây dựng được một phương án, dẫu rằng chưa hẳn tối ưu nhưng chấp nhận được. Kỹ thuật nhánh cận cho phép chúng ta tìm được phương án tối ưu. Trong kỹ thuật nhánh cận, việc phân nhánh không khó nhưng việc xác định giá trị cận là điều quan trọng. Cần phải xác định giá trị cận sao cho càng sát với giá của phương án càng tốt vì như thế thì có thể cắt tỉa được nhiều nút trên cây và đo đó sẽ giảm được thời gian thực hiện chương trình.

Vận dụng phương pháp quy hoạch động có thể giải được rất nhiều bài toán. Điều quan trọng nhất để áp dụng phương pháp quy hoạch động là phải xây dựng được công thức đệ quy để xác định kết quả bài toán thông qua kết quả các bài toán con.