Lập trình động không phải là ma thuật đen

Lập trình động không phải là ma thuật

• Lập trình động là một kỹ thuật dùng để giải các bài toán phức tạp bằng cách chia chúng thành các bài toán nhỏ hơn để tiếp cận.
• Kỹ thuật này là một điều tự nhiên, và nhiều thuật toán phổ biến thực chất là áp dụng lập trình động cho những bài toán cụ thể.
• Để giúp việc hiểu về lập trình động dễ hơn, bài viết cung cấp phần giới thiệu đơn giản hơn cùng lời giải thích chi tiết.

Lời than phiền

• Kỹ nghệ phần mềm thường rất tệ trong việc đặt tên.
• Các thuật ngữ như 'bootstrap', 'daemon', 'Cascading Style Sheets', 'cookie', 'trí tuệ nhân tạo' đều mơ hồ hoặc dễ gây hiểu lầm.
• Thuật ngữ 'lập trình động' cũng vậy: bản thân nó không liên quan đến 'động', mà thực ra là một ý tưởng được dùng trong thiết kế thuật toán.

Bộ nhớ đệm cơ bản

• Khi cố gắng giải một bài toán bằng cách chia nó thành các bài toán nhỏ tương tự nhau, bạn có thể phải giải đi giải lại cùng một bài toán nhỏ nhiều lần.
• Lấy dãy Fibonacci làm ví dụ: nếu cài đặt bằng hàm đệ quy đơn giản, bạn sẽ lặp lại cùng một phép tính nhiều lần.
• Có thể tránh tính toán trùng lặp bằng cách lưu kết quả vào bộ nhớ đệm (hoặc memoization).

Bộ nhớ đệm được tối ưu hóa

• Dùng memoization cho phép giữ nguyên đệ quy, nhưng chỉ tính những gì cần khi cần.
• Thay vào đó, cũng có thể tiếp cận bằng cách tính trước mọi thứ cần thiết.
• Cách làm này giải bài toán mà không cần lời gọi đệ quy, và đó chính là lập trình động.

Khoảng cách chỉnh sửa

• Khoảng cách chỉnh sửa giữa hai chuỗi là số lần chỉnh sửa tối thiểu cần để biến một chuỗi thành chuỗi kia.
• Khoảng cách chỉnh sửa có thể được tính bằng các thao tác thay ký tự, chèn và xóa, và đây là bài toán có thể được giải hiệu quả bằng lập trình động.
• Cần tìm ra cách suy ra lời giải tổng thể từ lời giải của các bài toán nhỏ.

Advent of Code, Day 12

• Trong bài toán Advent of Code ngày 12/12/2023, người giải phải xử lý một nonogram 1D.
• Có thể giải bằng cách vét cạn, nhưng độ phức tạp là hàm mũ.
• Thay vào đó, có thể áp dụng lập trình động để giải hiệu quả.

Kết luận

• Lập trình động không dễ, nhưng cũng không phải điều vượt ngoài tầm với của phần lớn lập trình viên.
• Nếu hiểu cách chia bài toán thành các bài toán nhỏ, bạn có thể dùng memoization trong nhiều tình huống, và điều đó mang lại cải thiện lớn so với cách cài đặt ngây thơ.
• Khi làm chủ lập trình động, bạn sẽ hiểu được cả một lớp thuật toán, nắm rõ hơn các đánh đổi và mở ra những tối ưu hóa khác.

Ý kiến của GN⁺

• Lập trình động là một kỹ thuật quan trọng để giải quyết hiệu quả các bài toán phức tạp, giúp giảm đáng kể chi phí tính toán bằng cách lưu lời giải của các bài toán con thay vì lặp lại phép tính trong cách tiếp cận đệ quy.
• Bài viết này rất hữu ích cho các kỹ sư phần mềm mới bắt đầu muốn hiểu các khái niệm cơ bản của lập trình động.
• Các ví dụ về dãy Fibonacci và khoảng cách chỉnh sửa giúp hiểu khái niệm lập trình động, đồng thời mang lại điểm khởi đầu tốt để áp dụng vào giải quyết bài toán thực tế.

[GN⁺]

Ý kiến trên Hacker News

• Việc bài viết giải thích thuật toán quy hoạch động (DP) như là cache cho đệ quy là một điểm hay.

  • Tìm ra lời giải đệ quy là điểm khởi đầu tối ưu để tìm ra lời giải DP.
  • Áp dụng memoization cho lời giải đệ quy có thể giúp tăng tốc đáng kể.
  • Điều quan trọng không phải là cây lời gọi có nhiều bài toán con, mà là phải có số lượng bài toán con độc nhất tương đối ít.

• Thích cách bài viết trước tiên xử lý bài toán theo hướng đệ quy, rồi dần thêm cache và sau đó thu gọn xuống đúng kích thước cache cần thiết.

  • Đã từng có trải nghiệm bị mắc kẹt hoặc phải bỏ ra rất nhiều công sức khi cố tìm trực tiếp lời giải quy hoạch động.
  • Từ nay sẽ tự buộc mình tiếp cận theo đúng thứ tự đó.

• Một trong những ứng dụng hay của quy hoạch động là căn chỉnh cặp chuỗi axit nucleic/protein.

  • Ví dụ như căn chỉnh chuỗi, thuật toán Needleman–Wunsch, thuật toán Smith–Waterman.

• Chia sẻ trải nghiệm về một giáo sư thuật toán cực kỳ xuất sắc.

  • Giáo sư học ở UCLA và bài giảng về quy hoạch động thật sự xuất sắc.
  • Bắt đầu từ một bài toán đơn giản nhưng có độ phức tạp theo cấp số mũ, sau đó chia bài toán thành các bài toán nhỏ hơn và giảm độ phức tạp xuống đa thức, rồi áp dụng memoization để hạ xuống độ phức tạp tuyến tính.
  • Muốn nhớ lại những bài toán đã được dùng.

• Chia sẻ liên kết tới bài viết Quy hoạch động không phải là black magic.

  • Bài viết đó hiện khó truy cập do lượng truy cập quá lớn (hug of death).

• Một người chủ yếu tự học lập trình nói rằng nếu lúc tìm việc mà trong phỏng vấn bị yêu cầu dùng quy hoạch động thì có lẽ họ đã không biết.

  • May mắn là điều đó không xảy ra, và nhờ biết kỹ năng này nên đã dùng nó trong nhiều buổi phỏng vấn.

• Cái tên "quy hoạch động" có thể không khiến người ta nghĩ nó xuất phát từ lĩnh vực lập trình.

  • Thực ra nó liên quan đến tối ưu hóa và là một phương pháp giải các bài toán quyết định theo thời gian rời rạc.
  • Quy hoạch động là cách định nghĩa hàm giá trị V* để giảm mạnh số chiều của bài toán tối ưu hóa.

• Đặt câu hỏi liệu việc chỉ nghĩ đến "memoization" khi nghe "quy hoạch động" có phải là sai hay không.

  • Phần còn thiếu có thể là việc chia bài toán một cách khéo léo để có thể dùng memoization hiệu quả.

• Quy hoạch động không phải là black magic; điều khó là chứng minh rằng một bài toán có thể được lập trình động và chứng minh tính đúng đắn của nó.

  • Cần có chứng minh hình thức bằng quy nạp toán học, tương tự như với thuật toán tham lam.

• Để thành thạo quy hoạch động, có người khuyên dùng sách thuật toán DPV và khóa học Udacity của Georgia Tech.

  • Có thể học quy hoạch động bằng cách luyện giải bài tập.