Kĩ thuật nhánh cận

<Just type to remember>

<Theo “Kỹ thuật thiết kế giải thuật” – Nguyễn Văn Linh >

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ả 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 đã 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.

Bài toán đường đi người giao hàng

Phân nhánh

Cây tìm kiếm phương án là cây nhị phân trong đó:

  • Nút gốc là nút biểu diễn cho cấu hình bao gồm tất cả các phương án.
  • Mỗi nút sẽ có 2 con, con trái biểu diễn cho cấu hình bao gồm tất cả các phương án chứa một cạnh nào đó, con phải biểu diễn cho cấu hình bao gồm tất cả các phương án không chứa cạnh đó (các cạnh để xét phân nhánh được lập tuân theo một thứ tự nào đó, chẳng hạn thứ tự từ điển).
  • Mỗi nút sẽ kế thừa các thuộc tính của tổ tiên của nó và có thêm một thuộc tính mới (chứa hay không chứa một cạnh nào đó).
  • Nút lá biểu diễn cho một cấu hình chỉ bao gồm một phương án.
  • Để quá trình phân nhánh mau chóng tới nút lá, tại mỗi nút ta cần có một quyết định bổ sung dựa trên nguyên tắc là mọi đỉnh trong chu trình đều có cấp 2 và không tạo ra một chu trình thiếu.
Advertisements

Greedy algorithm (Kĩ thuật tham lam)

<Just Type to Remember>

<Theo “Kỹ thuật thiết kế giải thuật – Nguyễn Văn Linh”>

 

1. Bài toán tối ưu tổ hợp:

Là một dạng của bài toán tối ưu, nó có dạng tổng quát như sau:

  • Cho hàm f(X) xác định trên một tập hữu hạn các phần tử D. Hàm f(X) được gọi là hàm mục tiêu.
  • Mỗi phần tử X thuộc D có dạng X = (x1, x2,…xn) được gọi là một phương án.
  • Cần tìm một phương án X thuộc D sao cho hàm  f(X) đạt min (max). Phương án X như vậy gọi là tối ưu.

Ta có thể tìm thấy phương án tối ưu bằng “vét cạn” nghĩa là xét tất cả các phương án trong tập D (hữu hạn) để tìm phương án tốt nhất. Mặc dù tập D là hữu hạn nhưng để tìm phương án tối ưu cho một bài toán kích thước n bằng vét cạn ta có thể cần một thời gian hàm mũ.

2. Nội dung kĩ thuật tham lam (tham ăn):

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 ăn món ngon thứ hai, lại ăn hết món ngon thứ hai và chuyển sang món ngon thứ 3..

Kĩ thuật tham lam 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 này đượ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 sẽ phải chấp nhận giá trị cuối cùng còn lại.

Áp dụng kĩ thuật tham lam sẽ cho ta 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.

Có rất nhiều bài toán mà ta có thể giải bằng kĩ thuật này.

Các bài toán ví dụ: Các bạn tìm hiểu các bài toán như: “Bài toán trả tiền của máy rút tiền tự động ATM”, “Bài toán cái balô”, “Bài toán đường đi của người giao hàng”, …