lập bảng

lập bảng

Lập bảng là một kỹ thuật được sử dụng để giải quyết vấn đề.

Việc lập bảng sử dụng một bảng trong đó kết quả của các bài toán con cơ bản nhất được lưu trữ trước tiên. Sau đó, bảng sẽ ngày càng chứa nhiều kết quả của bài toán con cho đến khi chúng ta tìm thấy kết quả của bài toán hoàn chỉnh mà chúng ta đang tìm kiếm.

Kỹ thuật lập bảng được cho là giải quyết các vấn đề "từ dưới lên" vì cách nó giải quyết các vấn đề con cơ bản nhất trước tiên.

Lập bảng là một kỹ thuật được sử dụng trong Lập trình động , có nghĩa là để sử dụng lập bảng, bài toán mà chúng ta đang cố gắng giải quyết phải bao gồm các bài toán con chồng chéo.

Sử dụng bảng tính để tìm số Fibonacci thứ \(n\)

Các số Fibonacci rất phù hợp để thể hiện các kỹ thuật lập trình khác nhau, cũng như khi thể hiện cách lập bảng hoạt động.

Việc lập bảng sử dụng một bảng chứa các số Fibonacci thấp nhất \(F(0)=0\) và \(F(1)=1\) trước tiên (từ dưới lên). Số Fibonacci tiếp theo được lưu trong bảng là \(F(2)=F(1)+F(0)\).

Số Fibonacci tiếp theo luôn là tổng của hai số trước đó:

\[ F(n)=F(n-1)+F(n-2) \]

Bằng cách này, bảng tiếp tục chứa đầy các số Fibonacci tiếp theo cho đến khi chúng ta tìm thấy số Fibonacci thứ \(n\) mà chúng ta đang tìm kiếm.

 def fibonacci_tabulation(n):     if n == 0: return 0     elif n == 1: return 1      F = [0] * (n + 1)     F[0] = 0      F[1] = 1      for i in range(2, n + 1):         F[i] = F[i - 1] + F[i - 2]          print(F)     return F[n]   
n = 10
result = fibonacci_tabulation(n)
print(f"\nThe {n}th Fibonacci number is {result}")

Các cách khác để tìm số Fibonacci thứ \(n\)th bao gồm đệ quy hoặc phiên bản cải tiến của nó bằng cách sử dụng tính năng ghi nhớ .

Lập bảng là cách tiếp cận từ dưới lên

Xem các hình vẽ bên dưới để hiểu rõ hơn lý do tại sao việc lập bảng được gọi là phương pháp "từ dưới lên".

Để tham khảo để so sánh, hãy xem bản vẽ phương pháp đệ quy "từ trên xuống" để tìm số Fibonacci thứ \(n\).

Phương pháp lập bảng bắt đầu xây dựng bảng từ dưới lên để tìm số Fibonacci thứ 10, bắt đầu bằng \(F(0)\) và \(F(1)\).

Cách tiếp cận đệ quy bắt đầu bằng cách cố gắng tìm \(F(10)\), nhưng để thấy rằng nó phải gọi \(F(9)\) và \(F(8)\), và cứ thế đi xuống đến \(F(0)\) và \(F(1)\) trước khi lệnh gọi hàm bắt đầu trả về các giá trị có thể được kết hợp với câu trả lời cuối cùng.

Các vấn đề khác được giải quyết bằng cách lập bảng

Cũng giống như việc tìm số Fibonacci thứ \(n\), việc lập bảng cũng có thể được sử dụng để tìm lời giải cho các vấn đề khác:

• Bài toán về chiếc ba lô 0/1 là về việc có một tập hợp các vật phẩm mà chúng ta có thể đóng gói trong một chiếc ba lô (một chiếc ba lô đơn giản), mỗi vật phẩm có một giá trị khác nhau. Để giải quyết vấn đề, chúng ta cần tìm những món đồ sẽ mang lại tổng giá trị lớn nhất cho những món đồ mà chúng ta đóng gói, nhưng chúng ta không thể mang theo tất cả những món đồ mình muốn vì chiếc ba lô có giới hạn về trọng lượng.
• Vấn đề về đường đi ngắn nhất có thể được giải quyết bằng thuật toán Bellman-Ford , thuật toán này cũng sử dụng phương pháp lập bảng để tìm đường đi ngắn nhất trong biểu đồ. Cụ thể hơn, cách tiếp cận lập bảng của thuật toán Bellman-Ford là cách cập nhật các giá trị trong mảng "khoảng cách".
• Bài toán Người bán hàng du lịch có thể được giải một cách chính xác bằng thuật toán Held-Karp, thuật toán này cũng sử dụng cách lập bảng. Thuật toán này không được mô tả trong hướng dẫn này vì nó mặc dù tốt hơn so với thuật toán vũ phu \(O(n!)\), nhưng vẫn không hiệu quả lắm \(O(2^nn^2)\) và khá tiên tiến.

Lập bảng trong lập trình động

Như đã đề cập ở trên, lập bảng (giống như ghi nhớ) là một kỹ thuật được sử dụng trong một thứ gọi là Lập trình động .

Lập trình động là một cách thiết kế các thuật toán để giải quyết vấn đề.

Để Lập trình động hoạt động được, bài toán chúng ta muốn giải quyết phải có hai thuộc tính sau:

• Bài toán phải được xây dựng bằng các bài toán con nhỏ hơn, chồng chéo lên nhau . Ví dụ: lời giải cho số Fibonacci \(F(3)\) trùng lặp với lời giải cho số Fibonacci \(F(2)\) và \(F(1)\), vì chúng ta nhận được \(F(3) \) bằng cách kết hợp \(F(2)\) và \(F(1)\).
• Bài toán cũng phải có một cấu trúc con tối ưu , nghĩa là lời giải của bài toán có thể được xây dựng từ lời giải của các bài toán con của nó. Khi tìm số Fibonacci thứ \(n\)th, \(F(n)\) có thể được tìm thấy bằng cách thêm \(F(n-1)\) và \(F(n-2)\). Như vậy việc biết 2 số đứng trước thôi chưa đủ để tìm \(F(n)\), chúng ta còn phải biết cấu trúc để biết cách ghép chúng lại với nhau.

Đọc thêm về Lập trình động ở trang tiếp theo .