Bài toán tối ưu mảng hai chiều

Quy hoạch tối ưu một bảng hai chiều - Bài toán tổng quát

Đỗ Sơn Huỳnh

Córất nhiều bài toán tối ưu trên một bảng cho trước gồm M dòng, N cộtnhư các dạng bài

tìm một hành trình đi từ dòng thứ nhất tới dòngthứ M thoả mãn một điều kiện tối ưu nào

đó. Nhưng cũng có nhữngbài toán tối ưu với số liệu ban đầu là các mảng phần tử một

chiềuđều có thể đưa về bài toán quy hoạch tối ưu trên một bảng hai chiều.Một ví dụ dễ

thấy và dễ gặp nhất là bài toán tìm xâu con lớn nhất,tìm đoạn dãy con đơn điệu dài nhất,

bài toán cây xăng, và điểnhình nhất là bài toán cái túi (với dữ liệu đầu vào là nguyên).

Tất cả các bài toán đó chúng ta đều có thể đưa về một dạngtổng quát mà tôi tạm gọi là

″Bài toán tổng quát quy hoạch tốiưu trên một bảng hai chiều ″. Bài viết này là sự tổng

hợp củabản thân tôi trong quá trình học môn tin học PASCAL.Xin nêu ra để các bạn có

thể tham khảo và cho nhữngý kiến quý báu.

Phát biểu bài toán

Cho một bảng gồm M dòng, N cột. Hãy tìm một phương án tối ưuđể ″đi ″ từ dòng thứ

nhấtđến hết dòng thứ M với các nguyên tắc sau:

1.Điều kiện tối ưu:

Làđiều kiện bài toán đưa ra. Đường đi tối ưu được tính bằng tổngtrọng số các ô đi qua.

Trọng số của một ô phụ thuộc quy tắc tínhtrọng số của bài toán.

2.Quy tắc tính trọng số:

-Trọng số bằng trị sốchính số liệu tại ô.

-Trọng số được tính bằngquy tắc do ô đứng trước quy định tuỳ theo từng bài toán.

-Trọng số phụ thuộc vàoô đứng trước ô đang xét.

3.Quy tắc ″Đitừ trên xuống dưới ″:

Từdòng thứ i bạn có thể đi ngang sang trái hoặc sang phải trên dòng đóvà đi xuống dưới

dòng thứ (i+1) theo các hướng chéo hoặc thẳng đứng.

Thuậtgiải chung

1.Bước 0:Mô hình hoá:

Nếu bài toán không phải là dạng tối ưu trênmột bảng hai chiều, ta phải tìm cách mô hình

hoá để đưa nó về dạngnày.

2.Bước 1:Xây dựng các quy tắc tính trọng số:

Xin lưu ý rằng điều kiện tối ưu ở đâyđã có sẵn ngay từ đầu.

Tuỳtheo dạng của bài toán ta sẽ có các quy tắc tính trọng số khác nhau.Khi đi xem xét với

các bài toán cụ thể ta sẽ rõ hơn điều này.

3.Bước 2:Xây dựng quy tắc ″đi ″:

Đôi khi quy tắc đi chưa có sẵn mà phải tựngười lập trình đặt ra cho phù hợp với cách mô

hình hoá của mình.Vấn đề này thuộc vào tư duy của mỗi người nên rất phong phú và

phứctạp.

4.Bước 3:Xây dựng công thức tối ưu:

Đây là bước quan trọng nhất của bài toán.Để xây dựng được công thức, ta cần phải dựa

vào các quy tắc đi vàtính trọng số.

5.Bước 4:Duyệt phương án tối ưu: