[Lý Thuyết quy hoạch động] Lỗi phụ thuộc tiền sử

[huynguyen]

Quy Hoạch Động (QHD) là 1 phương pháp rất mạnh mẽ trong Tin học. Nếu phân tích kĩ các bạn
sẽ thấy những thuật toán nổi tiếng như Ford-Bellman, Dijkstra, hay Floyd đều có bản chất là
QHD. Nhưng không phải bài toán nào cũng giải bằng QHD được, nếu quá áp đặt, cố sức giải nó
như vậy bạn sẽ dễ dàng mắc phải 1 sai lầm gọi là Phụ thuộc tiền sử.

Để tìm hiểu sai lầm này chúng ta nhắc lại về nguyên lí QHD do Bellman phát minh ra: "Một dãy là
tối ưu thì các dãy con của nó cũng là tối ưu". Nghe có vẻ khó hiểu nhưng đại loại là ta có 1 cái
bảng rồi lần lượt điền các số vào bảng đó, các số điền vào đầu tiên thường đơn giản, các số sau
đó dựa vào các số trước mà điền, cho đến khi điền kín bảng. Kết quả bài toán là số mà ta điền
cuối cùng. Như vậy nguyên lí "chia để trị" đã được đẩy tới cao độ ở đây.

Khâu quan trọng nhất là làm thế nào điền được số sau dựa trên các số trước, hay nói cách
khác là ta đang tìm 1 hệ thức truy hồi.

Gọi f(i) là hàm QHD tại i, ta xây dựng công thức truy hồi tính f(i) dựa vào các f(j) với j = i - 1, i - 2,
... Công thức truy hồi này chỉ được phụ thuộc vào các f(j) cùng các đại lượng cố định của các j
(cho trong đề bài) tuyệt đối không được phụ thuộc vào tiền sử, cách thức tạo nên f(j). Đây là
chính là sai lầm mà tôi muốn nói đến!

Để dễ hiểu chúng ta xét 1 ví dụ rất thú vị sau:
Bài toán: ngày xửa ngày xưa, có 1 chàng Hoàng tử bị 1 mụ Phù thủy hóa phép biến thành
1 con ếch, còn Công chúa thì bị mụ ta nhốt trong 1 tòa lâu đài nằm trên 1 hòn đảo giữa hồ. Bây
giờ ếch đang đứng ở bờ hồ, trên đoạn thẳng từ chỗ đó đến tòa lâu đài có các lá sen nổi trên mặt
nước ở những vị trí, khoảng cách khác nhau, ếch phải nhảy qua các lá sen để vào tòa lâu đài
cứu Công chúa. Bước nhảy kề sau không được dài hơn bước nhảy kề trước A mét cho trước.
Ếch có 1 túi rất nhiều muỗi thần, ăn K con muỗi, ếch có thể nhảy tối đa trong 1 bước là K mét.
Mỗi bước nhảy (dù dài hay ngắn) đều tốn 1 giây. Cho trước thời gian giới hạn là T giây, hãy tính
số muỗi ít nhất mà ếch cần ăn để có thể nhảy đến tòa lâu đài!

Dữ liệu vào cho trong file ECHOP.INP có cấu trúc:
Dòng đầu là 3 số nguyên N A T
Dòng 2 là N số nguyên dương tăng dần thể hiện tọa độ các lá sen.
Các số trên cùng 1 dòng cách nhau bởi ít nhất 1 dấu cách.
Dữ liệu ra file ECHOP.OUT gồm 1 số duy nhất là số muỗi tối thiểu, nếu không có phương án giải
cứu Công chúa in ra số -1

Rồi, đọc xong là biết phải dùng QHD, đây là cách sai:
Gọi d[t, i] là số muỗi ít nhất cần ăn khi phải nhảy đến lá sen thứ i và thời gian giới hạn là t. Để
tính d[t, i] ta chỉ cần xét các d[j, t - 1] với j = i - 1, i - 2, ... kiểm tra xem khoảng cách từ lá sen j
đến lá sen i là bao nhiêu (là P), xem tiền sử của d[j, t - 1] xem lá sen kề trước j là lá nào (lá thứ
z), tính khoảng cách giữa lá sen z và j là Q, kiểm tra Q + A >= P được thỏa mãn rồi đặt x =
max(d[t, j], P), trong các x như thế chọn ra cái nhỏ nhất và đó chính là d[t, i]

Cách đúng: gọi d[t, i, j] là số muỗi ít nhất khi trong thời gian t, cần nhảy đến lá sen j nhưng lá kề
trước j phải là i. Lúc này hệ thức truy hồi tương tự như trên nhưng không còn phụ thuộc tiền sử
nữa.

Bạn cũng dễ mắc sai lầm này khi đi tìm cách giải hoàn hảo cho các bài toán "bất trị", cho đến
nay loài người vẫn chưa giải được như bài toán Người du lịch, bài toán Tìm đường đi dài nhất
không lặp lại đỉnh trên đồ thị trọng số dương, bài toán Tập thống trị nhỏ nhất...
{Sưu tầm từ congdongtinhoc.com}

[hailoc12]

Đúng là trong nguyên lý quy hoạch động em thấy khó hiểu nhất là chỗ "Một dãy là tối ưu thì các dãy con của nó cũng là tối ưu". "tối ưu" ở đây không biết phải hiểu là tối ưu một cách khách quan (nghĩa là từ bước i đến bước i+1 thì chọn lựa này là tốt nhất) hay một cách chủ quan ( phụ thuộc vào các giá trị đã chọn trước ). Trong một số ví dụ như tìm đường đi ngắn nhất thì việc chọn đường đi ngắn nhất từ i tới i+1 là khách quan, chỉ có một đường ngắn nhất duy nhất. Nhưng trong ví dụ mà anh huynguyen đưa ra nó lại phụ thuộc vào những bước thực hiện trước nữa. Đúng là quá khó hiểu

[kidkid]

Chậc sao mình lại chả thấy gì khó hiểu dù mình chả biết QHD là cái gì cả ? Hix chẳng lẽ mình tệ thế sao ?

Để làm rõ tí nào ?

Giả sử như thế này đi có 5 điểm A,B,C,D,E , từ 1 điểm có thể đi đến tất cả các điểm và chúng ta phải tìm đường đi ngắn nhất từ A -> E

Đầu tiên theo cách hiểu của kid thì tìm Min (A->B,C,D,E) giả sử là B.
Tiếp tục thì từ B ta có đường tiếp theo là C .
Bây giờ ta mới lui lại và tính Min(A->C, A->B->C) rồi tiếp tục các bước lần lượt từ C.

Không biết tớ hiểu vậy có đúng với ....

[kanavaro]

bài toán người đi du lịch cũng thuộc quy hoạc động đúng k các bạn ?

[MrChicKen_NAD]

mấy bạn ui cho mình hỏi phụ thuộc tiền sử là sao???
Giải thik rõ cho mìh 1 xíu.thx