Biểu đồ quyết định nhị phân (binary decision diagram, viết tắt là BDD) là một cấu trúc dữ liệu dạng đồ thị có hướng phi chu trình có gốc dùng để biểu diễn và thao tác các hàm Boole một cách cô đọng. Trong cấu trúc này, mỗi đỉnh nội bộ gắn với một biến nhị phân và phân tách theo hai nhánh giá trị sai hoặc đúng, còn hai đỉnh lá biểu diễn kết quả hằng số của hàm, cho phép chia sẻ các đồ thị con giống nhau để tránh bùng nổ kích thước như bảng chân trị. Bài viết trình bày khái niệm, ranh giới thuật ngữ, tiến trình phát triển, cơ sở toán học với dạng rút gọn có thứ tự (ROBDD), các biến thể, ứng dụng trong kiểm chứng hệ thống và những giới hạn tính toán đã được chứng minh của cấu trúc này.
Khái niệm, cấu trúc và ranh giới thuật ngữ
Về mặt toán học, một hàm Boole bậc là ánh xạ nhận biến đầu vào nhị phân và trả về một giá trị đầu ra nhị phân. Thay vì liệt kê toàn bộ tổ hợp đầu vào trong bảng chân trị hoặc biểu diễn dưới dạng cây quyết định đầy đủ vốn phình to theo hàm mũ, biểu đồ quyết định nhị phân nén biểu diễn đó thành một đồ thị có hướng phi chu trình (directed acyclic graph, DAG) có duy nhất một đỉnh gốc.
Một biểu đồ quyết định nhị phân chuẩn gồm hai loại đỉnh chính:
- Đỉnh quyết định (đỉnh nội bộ): Mỗi đỉnh được gắn nhãn bởi một biến Boole (với là thành phần thứ của vector đầu vào) và có đúng hai cạnh có hướng đi ra: cạnh thấp (low edge) ứng với phép gán (sai) và cạnh cao (high edge) ứng với phép gán (đúng).
- Đỉnh lá (đỉnh tận cùng): Chỉ có tối đa hai đỉnh lá không có cạnh đi ra, mang nhãn hằng số (sai) và (đúng), tương ứng với giá trị đầu ra cuối cùng của hàm Boole theo đường đi đã chọn.
Để tính giá trị của hàm tại một bộ giá trị biến cụ thể, thuật toán xuất phát từ đỉnh gốc và lần theo cạnh ứng với giá trị hoặc của biến tại từng đỉnh cho đến khi chạm một trong hai đỉnh lá. Nhờ cấu trúc DAG cho phép nhiều đỉnh cha cùng trỏ tới một đỉnh con chung, các phần lặp lại của hàm Boole chỉ cần lưu trữ một lần.
Trong tài liệu tiếng Việt về khoa học máy tính, cần phân biệt rạch ròi biểu đồ quyết định nhị phân (còn gọi là đồ thị quyết định nhị phân, BDD) với cây quyết định nhị phân (binary decision tree) trong học máy:
- Biểu đồ quyết định nhị phân (BDD): Thuộc lĩnh vực lý thuyết mạch số, logic hình thức và kiểm chứng phần cứng, có cấu trúc đồ thị DAG chia sẻ đồ thị con, biểu diễn chính xác hàm Boole và đạt tính chuẩn tắc ở dạng rút gọn có thứ tự.
- Cây quyết định nhị phân (trong học máy): Thuộc lĩnh vực phân loại và hồi quy trên dữ liệu thực nghiệm, có cấu trúc cây thuần túy không chia sẻ nhánh con, các đỉnh thường kiểm tra ngưỡng trên thuộc tính liên tục hoặc rời rạc và không mang tính biểu diễn chuẩn tắc duy nhất cho hàm logic.
Nguồn gốc và tiến trình phát triển
Ý tưởng dùng cây hay chương trình rẽ nhánh nhị phân cho mạch chuyển mạch đã được nghiên cứu trước đó (được Bryant (1992) tổng thuật lại) và được Sheldon B. Akers (1978) chính thức đặt tên cùng hệ thống hóa thành một dạng biểu diễn đồ họa hoàn chỉnh. Trong công trình công bố trên tạp chí IEEE Transactions on Computers, Akers (1978) sử dụng tên gọi Binary Decision Diagrams, trình bày cách định nghĩa và phân tích các hàm chuyển mạch số thông qua đồ thị nhị phân.
Bước ngoặt đưa cấu trúc này trở thành công cụ chủ lực trong tin học lý thuyết và thiết kế vi mạch diễn ra khi Randal E. Bryant (1986) đề xuất biểu đồ quyết định nhị phân có thứ tự được rút gọn (reduced ordered binary decision diagram, ROBDD). Bằng cách áp đặt một thứ tự biến cố định dọc theo mọi đường đi kết hợp hai quy tắc rút gọn, Bryant (1986) chứng minh cấu trúc thu được là biểu diễn chuẩn tắc duy nhất cho mọi hàm Boole dưới thứ tự biến đã chọn, đồng thời xây dựng các thuật toán thao tác trực tiếp trên đồ thị.
Tiếp nối nền tảng của Bryant (1986), J. R. Burch và cộng sự (1992) kết hợp phép tính -calculus với BDD để xây dựng phương pháp kiểm chứng mô hình biểu tượng (symbolic model checking), thay thế việc liệt kê tường minh từng trạng thái. Theo báo cáo của Burch và cộng sự (1992), cách tiếp cận biểu tượng này giúp kiểm chứng các hệ thống hữu hạn trạng thái đạt quy mô trạng thái và lớn hơn, vượt xa các phương pháp duyệt tường minh trước đó vốn phải lưu trữ danh sách hoặc bảng trạng thái tăng tỷ lệ thuận với số trạng thái. Cùng năm, Bryant (1992) xuất bản bài tổng quan trên ACM Computing Surveys hệ thống hóa lý thuyết OBDD và các ứng dụng trong thiết kế hệ thống số, trí tuệ nhân tạo và logic toán học.
Song song với các ứng dụng kiểm chứng, cộng đồng nghiên cứu cũng làm rõ giới hạn lý thuyết và mở rộng cấu trúc BDD cho các bài toán đặc thù: Bryant (1991) chứng minh cận dưới hàm mũ đối với phép nhân số nguyên, Shin-ichi Minato (1993) đề xuất biến thể BDD triệt tiêu số không (zero-suppressed BDD, ZDD) cho tập thưa trong bài toán tổ hợp, còn Beate Bollig và Ingo Wegener (1996) chứng minh bài toán cải thiện thứ tự biến của OBDD là NP-đầy đủ. Sau này, bên cạnh sự phát triển mạnh của các bộ giải thỏa mãn logic dựa trên tìm kiếm, hướng nghiên cứu của Randal E. Bryant và Marijn J. H. Heule (2023) đã mở rộng bộ giải SAT dựa trên BDD để tự động sinh chứng minh phân giải mở rộng (extended resolution proofs) có thể kiểm tra độc lập.
Cơ sở toán học và hai quy tắc rút gọn ROBDD
Cơ sở đại số của biểu đồ quyết định nhị phân là phép khai triển Shannon (Shannon expansion). Với bất kỳ hàm Boole và biến nào trong tập biến đầu vào, hàm luôn được phân tách thành hai hàm con ứng với hai giá trị của :
Trong biểu thức trên, là hàm Boole gốc, là biến phân nhánh tại đỉnh đang xét, là hàm phần dư thu được khi cố định (ứng với cạnh thấp), và là hàm phần dư khi cố định (ứng với cạnh cao). Quá trình khai triển đệ quy theo từng biến tạo nên một cây quyết định nhị phân hoàn chỉnh, trong đó mỗi đỉnh tương ứng với một phép rẽ nhánh theo công thức trên.
Ràng buộc thứ tự biến (OBDD)
Trong một BDD tổng quát (không có thứ tự), các biến có thể xuất hiện theo những trình tự khác nhau trên các đường đi khác nhau từ gốc tới lá, thậm chí một biến có thể bị kiểm tra nhiều lần trên cùng một đường đi. Để khắc phục sự thiếu nhất quán này, mô hình biểu đồ quyết định nhị phân có thứ tự (ordered binary decision diagram, OBDD) áp đặt một thứ tự toàn phần nghiêm ngặt trên tập biến (ví dụ , với là các biến đầu vào của hàm). Theo định nghĩa được Bryant (1986) và Bryant (1992) trình bày, trên mọi đường đi có hướng từ đỉnh gốc đến đỉnh lá trong OBDD, nếu đỉnh mang nhãn biến có cạnh đi tới đỉnh không phải lá mang nhãn biến , thì biến bắt buộc phải đứng trước trong thứ tự . Nhờ vậy, mỗi biến xuất hiện tối đa một lần trên mỗi đường đi.
Hai quy tắc rút gọn và tính chuẩn tắc
Từ một OBDD hợp lệ, dạng ROBDD (reduced ordered binary decision diagram) được tạo ra bằng cách áp dụng lặp lại hai quy tắc rút gọn chuẩn cho tới khi không còn đỉnh nào rút gọn được nữa:
- Hợp nhất các đỉnh đẳng cấu (loại bỏ đồ thị con trùng lặp): Nếu hai đỉnh quyết định phân biệt và mang cùng nhãn biến , đồng thời cạnh thấp của cả hai trỏ tới cùng một đỉnh con và cạnh cao của cả hai cũng trỏ tới cùng một đỉnh con, thì một trong hai đỉnh bị xóa và mọi cạnh trỏ vào nó được chuyển hướng sang đỉnh còn lại.
- Loại bỏ các đỉnh thừa (redundant nodes): Nếu một đỉnh có cả cạnh thấp và cạnh cao cùng trỏ tới một đỉnh con duy nhất , thì giá trị của biến tại không ảnh hưởng tới kết quả hàm (); đỉnh được loại bỏ và các cạnh đi vào được nối thẳng tới .
Hệ quả quan trọng nhất của hai quy tắc này là tính chuẩn tắc (canonicity): với một thứ tự biến cố định trước, mọi hàm Boole chỉ có duy nhất một đồ thị ROBDD đẳng cấu đại diện (Bryant, 1986; Bryant, 1992). Tính chất này biến nhiều bài toán logic phức tạp thành thao tác đơn giản trên đồ thị:
- Kiểm tra tính thỏa được (satisfiability): Hàm Boole có nghiệm khi và chỉ khi ROBDD của nó không suy biến thành duy nhất đỉnh lá .
- Kiểm tra hằng đúng (tautology): Hàm luôn đúng với mọi đầu vào khi và chỉ khi ROBDD của nó chỉ gồm duy nhất đỉnh lá .
- Kiểm tra tính tương đương logic: Hai hàm và tương đương nhau khi và chỉ khi ROBDD của chúng trùng khớp nhau hoàn toàn về cấu trúc (trong các cài đặt dùng bảng băm duy nhất, hai hàm trỏ tới cùng một đỉnh gốc trong bộ nhớ).
Phép toán trên biểu đồ và các biến thể chính
Một ưu thế cốt lõi của ROBDD là các phép toán Boole không cần quay lại bảng chân trị mà được thực hiện trực tiếp bằng thuật toán đệ quy trên cấu trúc đồ thị, kết hợp kỹ thuật ghi nhớ kết quả trung gian (memoization) và bảng băm duy nhất để duy trì tính rút gọn ở mọi bước.
Các phép toán cơ bản và độ phức tạp
Trong bài báo nền tảng, Bryant (1986) xây dựng thuật toán Apply để tính (với , là hai hàm Boole được biểu diễn bởi hai đồ thị ROBDD có kích thước số đỉnh lần lượt là và , còn là phép toán hai ngôi bất kỳ như AND, OR, XOR). Thuật toán đệ quy song song theo biến đứng trước trong thứ tự dựa trên khai triển Shannon và lưu cặp trạng thái đã tính vào bảng băm để tránh tính lặp, đạt độ phức tạp thời gian (Bryant, 1986). Nghĩa là thời gian thực thi tỷ lệ với tích kích thước hai đồ thị đầu vào chứ không nhất thiết phụ thuộc hàm mũ vào tổng số biến .
Bên cạnh phép toán hai ngôi (thường được cài đặt thống nhất qua toán tử ite — If-Then-Else), thư viện ROBDD còn hỗ trợ hiệu quả phép gán hằng số cho biến (restriction), phép hợp hàm (composition), phép đếm số nghiệm thỏa mãn và phép lượng từ hóa tồn tại hay phổ quát trên từng biến Boole (tuy nhiên, khi lượng từ hóa đồng thời trên nhiều biến để tính tập trạng thái kế tiếp thì kích thước đồ thị trung gian vẫn có thể bùng nổ, theo Bryant, 1992).
So sánh các biến thể phổ biến
Nhằm khắc phục giới hạn của ROBDD trong những lớp bài toán chuyên biệt (như biểu diễn tập hợp thưa), nhiều biến thể của biểu đồ quyết định nhị phân đã được đề xuất:
| Biến thể | Ràng buộc thứ tự | Quy tắc rút gọn đặc trưng | Đặc điểm và phạm vi phù hợp |
|---|---|---|---|
| BDD tự do / tổng quát (Binary Decision Diagram) | Không bắt buộc thứ tự biến cố định; nếu mỗi biến xuất hiện tối đa một lần trên mỗi đường đi gọi là free BDD | Có thể gộp nhánh giống nhau nhưng thiếu ràng buộc thứ tự chung | Linh hoạt hơn OBDD về mặt biểu diễn, nhưng đánh mất tính chuẩn tắc đơn giản và khó thực hiện phép toán kết hợp hai hàm hiệu quả. |
| OBDD chưa rút gọn (Ordered BDD) | Mọi đường đi từ gốc đến lá tuân thủ chặt chẽ một thứ tự biến toàn phần | Không hoặc chưa áp dụng đủ hai quy tắc rút gọn | Tránh kiểm tra lặp biến trên một đường đi, nhưng còn chứa đỉnh thừa và đồ thị con trùng lặp nên chưa phải dạng chuẩn tắc duy nhất. |
| ROBDD (Reduced Ordered BDD, Bryant, 1986) | Tuân thủ chặt chẽ một thứ tự biến toàn phần cố định | Hợp nhất đồ thị con đẳng cấu và xóa đỉnh có hai cạnh trỏ cùng một đích | Chuẩn tắc (duy nhất theo thứ tự biến), hỗ trợ phép toán hai ngôi trong thời gian tỷ lệ với tích kích thước đồ thị; phù hợp mạch logic và kiểm chứng mô hình. |
| ZDD / 0-Sup-BDD (Zero-Suppressed BDD, Minato, 1993) | Tuân thủ thứ tự biến cố định như OBDD | Hợp nhất đỉnh đẳng cấu và xóa đỉnh có cạnh 1 (high edge) trỏ thẳng tới lá 0 | Biểu diễn gọn hơn đáng kể cho họ các tập con thưa (mỗi phần tử chỉ xuất hiện trong ít tổ hợp), hiệu quả trong bài toán tổ hợp và thiết kế CAD LSI. |
Ứng dụng trong thiết kế mạch, kiểm chứng và giải bài toán SAT
Trong thực tiễn kỹ thuật và nghiên cứu khoa học máy tính, biểu đồ quyết định nhị phân (chủ yếu ở dạng ROBDD và ZDD) đóng vai trò cấu trúc dữ liệu nền tảng ở nhiều lĩnh vực:
- Kiểm chứng tương đương mạch số (equivalence checking): Trong quy trình tự động hóa thiết kế điện tử (EDA), kỹ sư cần chứng minh mạch mô tả ở mức thanh ghi (RTL) và mạch sau tổng hợp cổng logic (gate-level netlist) thực hiện cùng một chức năng toán học. Khi chuyển hai biểu diễn sang ROBDD với cùng thứ tự biến đầu vào, việc so sánh tương đương quy về kiểm tra hai đồ thị có đồng nhất hay không (Bryant, 1992).
- Kiểm chứng mô hình biểu tượng (symbolic model checking): Để xác minh các giao thức truyền thông hoặc hệ thống tuần tự đồng bộ không rơi vào trạng thái lỗi hay bế tắc, tập hợp các trạng thái và quan hệ chuyển tiếp được mã hóa thành hàm Boole và lưu bằng BDD thay vì liệt kê từng đỉnh trạng thái. Công trình của Burch và cộng sự (1992) cho thấy kỹ thuật này cho phép kiểm chứng các hệ thống có quy mô trạng thái và hơn thế nữa, bao gồm cả mạch ống đồng bộ (synchronous pipeline circuit).
- Thao tác tập hợp và tối ưu tổ hợp: Biến thể ZDD do Minato (1993) đề xuất được dùng để biểu diễn và thao tác các họ tập hợp thưa, danh sách các tích nguyên tố không dư thừa trong tổng hợp logic mạch tích hợp cỡ lớn (LSI CAD) và các bài toán đếm tổ hợp.
- Giải bài toán SAT kèm chứng minh kiểm chứng được: Dù bộ giải SAT hiện đại chủ yếu dựa trên tìm kiếm quay lui có học mệnh đề xung đột (CDCL), nghiên cứu của Bryant và Heule (2023) cho thấy bộ giải SAT dựa trên BDD kết hợp lượng từ tồn tại tùy ý có thể sinh chứng minh phân giải mở rộng có kích thước đa thức cho một số họ bài toán rất khó đối với CDCL, như bài toán bàn cờ bị cắt góc (mutilated chessboard) và bài toán nguyên lý chuồng bồ câu (pigeonhole problem), đồng thời cho phép trình kiểm tra độc lập xác nhận tính đúng đắn mà không cần tin cậy mù quáng vào mã nguồn bộ giải.
Tại Việt Nam, biểu đồ quyết định nhị phân là nội dung được giảng dạy và nghiên cứu trong các học phần về toán rời rạc, thiết kế hệ thống số, logic hình thức và kiểm chứng phần mềm tại các trường đại học kỹ thuật và công nghệ thông tin, thường đi kèm các công cụ phân tích mạch, kiểm tra tính khả đạt của hệ chuyển đổi trạng thái hoặc phân tích cây lỗi.
Hạn chế, điều kiện áp dụng và vấn đề còn mở
Mặc dù mang lại bước tiến lớn cho xử lý ký hiệu hàm Boole, biểu đồ quyết định nhị phân có những giới hạn toán học nghiêm ngặt khiến nó không thể áp dụng vạn năng cho mọi hàm logic:
- Phụ thuộc cực mạnh vào thứ tự biến: Kích thước của một ROBDD cho cùng một hàm Boole có thể thay đổi từ tuyến tính đến hàm mũ theo số biến tùy thuộc thứ tự được chọn (Bryant, 1986; Bollig và Wegener, 1996). Chẳng hạn, với hàm cộng có nhớ nối tiếp hoặc các hàm ghép cặp biến, sắp xếp xen kẽ các cặp biến tương ứng giữ đồ thị ở kích thước tuyến tính, trong khi gom toàn bộ một nhóm biến lên trước nhóm kia làm số đỉnh bùng nổ theo hàm mũ.
- Bài toán tìm thứ tự biến tối ưu là NP-đầy đủ: Beate Bollig và Ingo Wegener (1996) đã chứng minh rằng bài toán quyết định cải thiện thứ tự biến—tức cho trước một OBDD biểu diễn hàm và ngưỡng kích thước , xác định xem có tồn tại OBDD tương đương theo một thứ tự biến khác với tối đa đỉnh hay không—là bài toán NP-đầy đủ. Hệ quả thực hành là các thư viện BDD phải dựa vào thuật toán heuristic sắp xếp động cục bộ (như đổi chỗ biến lân cận) thay vì tìm thứ tự tối ưu tuyệt đối.
- Bùng nổ hàm mũ nội tại ở một số hàm số học: Ngay cả khi được phép chọn thứ tự biến tốt nhất có thể, vẫn tồn tại những hàm quan trọng trong thực tế không có bất kỳ OBDD kích thước đa thức nào. Bryant (1991) chứng minh rằng đối với phép nhân hai số nguyên bit, một số bit đầu ra ở vùng giữa của tích (cụ thể là bit thứ ) đòi hỏi mọi OBDD phải chứa ít nhất đỉnh bất kể thứ tự biến nào được sử dụng. Vì vậy, ROBDD thuần túy không phù hợp để kiểm chứng trực tiếp các mạch nhân cỡ lớn, mạch mật mã học hoặc bộ xử lý số học mà cần chuyển sang các biểu diễn cấp từ (word-level) hoặc phương pháp khác.
- Chi phí bộ nhớ và cạnh tranh với phương pháp tìm kiếm: Trong quá trình thực hiện liên tiếp các phép toán trung gian (ví dụ hợp hoặc giao các quan hệ chuyển tiếp lớn), kích thước đồ thị tạm thời có thể vượt quá dung lượng bộ nhớ khả dụng ngay cả khi đồ thị kết quả cuối cùng nhỏ. Tính đến năm 2023, hướng nghiên cứu tiếp tục tập trung vào việc kết hợp sức mạnh suy diễn của BDD với khả năng kiểm chứng chứng minh độc lập (như chứng minh phân giải mở rộng trong Bryant và Heule, 2023) và khai thác cấu trúc quyết định chuyên biệt thay cho việc dùng ROBDD đơn thuần trên toàn bộ bài toán công nghiệp.