🌱 Slope Trick

🔗 Link:
📌 Tags: Slope Trick Optimization
✍🏻 Writer: @SPyofgame
🔎 Editor:
⚒️ Contributor:
📋 Content:

Giới thiệu

Đối tượng độc giả

Kiến thức đề xuất

Slope Trick là gì ?

Slope Trick hoạt động như nào ?

Giới thiệu

Đối tượng độc giả

Những bạn đã học về quy hoạch động và muốn có thêm một thủ thuật tối ưu bài toán dựa trên tính chất đặc biệt của hàm lồi. Thường là dạng bài

f_{i} (x) = m i n (f_{i - 1} (v) + c o s t_{i} (v) ∣ v \leq x)

, ví dụ tiêu biểu có thể là

c o s t_{i} (v) = | a_{i} - v |

Kiến thức đề xuất

Hàm số: Hiểu cách vẽ đồ thị hàm số và biểu diễn
$y = f (x) = a x + b$
Đạo hàm: Hiểu cách biểu diễn độ dốc của hàm số
$m = \frac{Δ y}{Δ x} = t a n (θ)$
Hình học: Hiểu tính chất hàm lồi, biểu diễn điểm
$(x, y)$ trên mặt phẳng
$O x y$
Quy hoạch động: Dựng lên hàm quy hoạch động từ công thức truy hổi, và hiểu cách biến đổi thành công thức khác.
Cấu trúc dữ liệu: Dựng cấu trúc dữ liệu lên để quản lí các đoạn thẳng và duy trì kết quả tối ưu (thêm xoá, truy vấn).
Cài đặt nâng cao: Tuy đoạn code thường khá ngắn so với các bài tương tự song có thể dễ gây lú khi xét trường hợp.

Slope Trick là gì ?

Slope Trick là kĩ thuật tối ưu hoá quy hoạch động liên quan tới các STF (Slope-Trickable-Function)
Slope Trickable Function là một hàm liên tục y = f(x) thoả các tính chất

Có thể biểu diễn thành một lượng hữu hạn các đoạn thẳng, mỗi đoạn thẳng là một hàm tuyến tính với một giá trị độ dốc Δy = g(x) = ax + b (thường là số nguyên).
Hàm đó phải là hàm lồi, tức là mỗi đoạn thẳng được tách ra phải ko giảm hoặc ko tăng (Trên hàm quy hoạch động em cho một đại lượng thay đổi thì nó sẽ vẽ ra hình dạng U lật ngược).

Ví dụ 0:

f0(x) = |x|
      = { -x      khi x < 0
        { +x      khi x ≥ 0

Ví dụ 1:

[]

        { -2x + 1      khi x < -1
f1(x) = {   x + 2      khi -1 ≤ x < +1
        {  3x - 4      khi x ≥ +1

Ví dụ 2:

        {   27x + 784  khi x < λ
f2(x) = {   -2x + 126  khi λ ≤ x < Λ
        { 2004x - 953  khi x ≥ Λ

Ví dụ 3:

        {  ax + α      khi     x < A
        {  bx + β      khi A ≤ x < B 
f3(x) = {  cx + ζ      khi B ≤ x < C
        {  dx + δ      khi C ≤ x < D
        {  ex + ε      khi D ≤ x

Slope Trick hoạt động như nào ?

Ý tưởng của slope trick là thay vì ta lưu các hàm khác nhau để quản lí từng đoạn, thì sao ta không dùng một hàm duy nhất, nhưng lưu lại các vị trí mà nó thay đổi (x, y) ?

Ví dụ 0:

f0(x) = |x|
      = { -x      khi x < 0
        { +x      khi x ≥ 0

có thể được biểu diễn thành [y = x | {x=0, Δy=+2}]

Ví dụ 1:

        { -2x + 1      khi x < -1
f1(x) = {   x + 2      khi -1 ≤ x < +1
        {  3x - 4      khi x ≥ +1

có thể được biểu diễn thành [y = 3x - 4 | {x=-1, Δy=+3}, {x=+1, Δy=+2}]
Giải thích:
{x=-1, Δy=+3} vì -2x + 1 -> x + 2 thay đổi y đi Δy=1-(-2)=3
{x=+1, Δy=+3} vì x + 2 -> 3x - 4 thay đổi y đi Δy=3-1=2

Ví dụ 2:

        {   27x + 784      khi x < λ
f2(x) = {   -2x + 126      khi λ ≤ x < Λ
        { 2004x - 953      khi x ≥ Λ

có thể được biểu diễn thành [y = 2004x - 953 | {x=λ, Δy=-29}, {x=Λ, Δy=+2006}]
{x=λ, Δy=-29} vì 27x + 784 -> -2x + 126 thay đổi y đi Δy=-2-27=-29
{x=Λ, Δy=+2006} vì -2x + 126 -> 2004x - 953 thay đổi y đi Δy=2004-(-2)=+2006

Ví dụ 3:

        {  ax + α      khi     x < A
        {  bx + β      khi A ≤ x < B 
f3(x) = {  cx + ζ      khi B ≤ x < C
        {  dx + δ      khi C ≤ x < D
        {  ex + ε      khi D ≤ x

có thể được biểu diễn thành [y = ex + ε | {x=A, Δy=b-a}, {x=B, Δy=c-b}, {x=C, Δy=d-c}, {x=D, Δy=e-d}]