Thuật toán nhanh cận trên môi trường Song song

Hệ thống gồm hai nhóm : một nhóm các lớp cung cấp (Provided) bao hàm các thủ tục chung cho thuật toán nhánh cận (ví dụ như khung của thuật toán nhánh cận tuần tự, khung của thuật toán nhánh cận song song .) và nhóm các lớp yêu cầu (Required) bao hàm các thủ tục riêng để giải quyết một bài toán cụ thể sử dụng kỹ thuật nhánh cận (ví dụ như các thủ tục tính cận, thủ tục phân nhánh, .). Để giải quyết một bài toán bằng kỹ thuật nhánh cận, người sử dụng chỉ cần viết các khai báo và xây dựng các hàm trong nhóm yêu cầu mà không cần xây dựng lại nhóm cung cấp. Hình 4.1 diễn tả mô hình UML tổng quan của hệ thống.

* Nhóm các lớp yêu cầu
Mô hình chung của nhóm các lớp yêu cầu

Các lớp yêu cầu được sử dụng để lưu trữ dữ liệu cơ bản của thuật toán : bài toán, trạng thái không gian tìm kiếm. Nó bao gồm các lớp chính sau :
- Bài toán (Problem): Diễn tả các tham số của bài toán cần giải quyết.
- Bài toán con (Subproblem) : Diễn tả vùng không gian chưa được khai thác và cung cấp các chức năng sau :
o InitSubProblem(pbm) : Sinh ra bài toán con đầu tiên từ bài toán ban đầu
o LowerBound(pbm, sol) : Tính toán cận dưới của hàm mục tiêu cho lời giải bộ phận sol của bài toán pbm.
o UpperBound(pbm, sol) : Tính giá trị hàm mục tiêu của lời giải toàn cục sol của bài toán pbm.
o Branch(pbm, sps) : Sinh ra một tập các bài toán con của bài toán đang xét và lưu vào sps.