Phương pháp nhánh và cận

From Systems analysis wiki
Jump to navigation Jump to search

Phương pháp nhánh và cận (tiếng Anh: Branch and Bound, viết tắt B&B hoặc BnB) — là một mô hình tổng quát để xây dựng các thuật toán chính xác nhằm giải các bài toán tối ưu hóa rời rạc và tổ hợp, đặc biệt là các bài toán NP-khó[1]. Phương pháp này là một chiến lược duyệt có định hướng, trong đó toàn bộ tập nghiệm chấp nhận được được phân chia tuần tự thành các tập con (nhánh), và với mỗi tập con, các ước lượng (cận) của giá trị hàm mục tiêu được tính toán. Các ước lượng này cho phép loại bỏ (cắt tỉa) những tập con chắc chắn không chứa nghiệm tối ưu, qua đó thu hẹp đáng kể không gian tìm kiếm[2].

Phương pháp được đề xuất lần đầu bởi A. Land và A. Doig vào năm 1960 để giải các bài toán quy hoạch nguyên[3]. Kể từ đó, nó đã trở thành một trong những hướng tiếp cận cơ bản nhất trong nghiên cứu vận trù và khoa học máy tính. Đặc điểm nổi bật của phương pháp là tính linh hoạt: nó không phải là một thuật toán cụ thể, mà là một sơ đồ chiến lược cấp cao (framework), có khả năng thích nghi với cấu trúc của bài toán cần giải.

Các thành phần then chốt của phương pháp

Nền tảng của phương pháp là ba thao tác cơ bản, được áp dụng cho các tập con của không gian nghiệm được tổ chức dưới dạng cây tìm kiếm.

  • Phân nhánh (tiếng Anh: Branching) — là quá trình đệ quy phân chia tập nghiệm chấp nhận được hiện tại Si thành một số tập con nhỏ hơn, thông thường là không giao nhau Si1,Si2,…,Sik. Mỗi tập con như vậy tương ứng với một bài toán con mới và được biểu diễn dưới dạng một nút con trong cây tìm kiếm. Ví dụ, trong các bài toán quy hoạch nguyên, việc phân nhánh thường được thực hiện theo biến có giá trị phân số trong nghiệm của bài toán giãn lỏng LP.
  • Ước lượng cận (tiếng Anh: Bounding) — với mỗi nút trong cây tìm kiếm (tức là với mỗi bài toán con), một ước lượng giá trị hàm mục tiêu được tính toán. Với bài toán tối thiểu hóa, đây là cận dưới (lower bound), là một đánh giá đảm bảo từ phía dưới cho bất kỳ nghiệm nào trong tập con đó. Ước lượng này thường được tính bằng cách giải bài toán giãn lỏng của bài toán con gốc — phiên bản đơn giản hóa trong đó một số ràng buộc phức tạp (ví dụ, ràng buộc nguyên) được tạm thời bỏ qua. Phổ biến nhất là giãn lỏng LP.
  • Cắt tỉa (tiếng Anh: Pruning) — là quá trình loại bỏ khỏi xem xét các nút (và toàn bộ cây con tương ứng) mà chắc chắn không thể chứa nghiệm tối ưu. Một nút bị cắt tỉa trong một trong các trường hợp sau:
  1. Cắt tỉa theo cận: Cận dưới của nút này không tốt hơn (tức là lớn hơn hoặc bằng, đối với bài toán tối thiểu hóa) so với giá trị của nghiệm chấp nhận được tốt nhất tìm được cho đến thời điểm hiện tại, được gọi là kỷ lục (incumbent).
  2. Cắt tỉa theo tính chấp nhận được: Nghiệm của bài toán giãn lỏng tại nút này là nghiệm chấp nhận được cho bài toán gốc (ví dụ, tất cả các biến đều nguyên). Nghiệm này được so sánh với kỷ lục hiện tại và nếu tốt hơn, kỷ lục được cập nhật. Không cần phân nhánh thêm từ nút này.
  3. Cắt tỉa theo tính không khả thi: Bài toán con tương ứng với nút không có nghiệm chấp nhận được.

Thuật toán tổng quát

Thuật toán tổng quát của phương pháp nhánh và cận cho bài toán tối thiểu hóa có thể được mô tả theo các bước sau:

  1. Khởi tạo: Tìm một nghiệm chấp nhận được ban đầu (ví dụ, bằng phương pháp heuristic) và đặt giá trị của nó làm cận trên ban đầu (kỷ lục) U. Tạo hàng đợi các nút hoạt động Q chứa nút gốc (bài toán ban đầu).
  2. Vòng lặp chính: Trong khi hàng đợi Q chưa rỗng:
    • Chọn một nút từ Q theo chiến lược tìm kiếm (ví dụ, tìm kiếm theo chiều sâu hoặc theo ước lượng tốt nhất).
    • Giải bài toán giãn lỏng cho nút này, thu được cận dưới L.
    • Cắt tỉa nút nếu L≥U.
    • Nếu nghiệm của bài toán giãn lỏng là chấp nhận được cho bài toán gốc, cập nhật kỷ lục: U←L.
    • Nếu nút chưa bị cắt tỉa và nghiệm không chấp nhận được, thực hiện phân nhánh, chia nó thành các nút con, và thêm chúng vào hàng đợi Q.
  3. Kết thúc: Khi hàng đợi Q trở nên rỗng, thuật toán kết thúc. Nghiệm tìm được tương ứng với kỷ lục U là nghiệm tối ưu toàn cục.

Các tính chất và định lý then chốt

  • Tính đúng đắn và hội tụ: Thuật toán đảm bảo tìm được nghiệm tối ưu toàn cục trong một số hữu hạn bước, nếu tập nghiệm chấp nhận được là hữu hạn và thủ tục phân nhánh là hội tụ (tức là, khi phân chia đệ quy, các tập con «co lại» về các điểm)[4].
  • Chiến lược tìm kiếm: Hiệu quả của thuật toán phụ thuộc nhiều vào chiến lược chọn nút tiếp theo để phân nhánh (ví dụ, tìm kiếm theo chiều sâu, tìm kiếm theo chiều rộng, tìm kiếm theo ước lượng tốt nhất) và vào việc chọn biến để phân nhánh. Các bộ giải hiện đại thường sử dụng các chiến lược kết hợp[5].

Các ví dụ

  • Bài toán quy hoạch nguyên: Ứng dụng điển hình của phương pháp. Bài toán giãn lỏng sử dụng là quy hoạch tuyến tính. Phân nhánh diễn ra theo biến phân số xj, tạo ra hai bài toán con với các ràng buộc bổ sung xj≤⌊xj*⌋ và xj≥⌈xj*⌉.
  • Bài toán người bán hàng rong: Không gian nghiệm là tất cả các chu trình Hamilton trong đồ thị. Phân nhánh có thể được thực hiện theo các cạnh (đưa vào/loại khỏi hành trình). Cận dưới có thể được tính bằng cách giải các bài toán đơn giản hơn, như bài toán phân công hoặc xây dựng cây khung nhỏ nhất[6].

Các khái niệm liên quan và ứng dụng

  • Phương pháp nhánh và cắt (Branch-and-Cut): Phương pháp kết hợp B&B với phương pháp mặt phẳng cắt. Tại mỗi nút của cây tìm kiếm, ngoài việc giải bài toán giãn lỏng, các bất đẳng thức bổ sung (lát cắt) được sinh ra, giúp tăng cường cận dưới, dẫn đến việc cắt tỉa các nhánh hiệu quả hơn.
  • Tìm kiếm có quay lui (Backtracking): Phương pháp nhánh và cận có thể được xem như sự tổng quát hóa của thuật toán này cho các bài toán tối ưu hóa.
  • Cắt tỉa alpha-beta: Một phép tương đồng khái niệm được sử dụng trong cây trò chơi để cắt tỉa các nhánh chắc chắn thua.

Xem thêm

  • Quy hoạch nguyên
  • Tối ưu hóa tổ hợp
  • Bài toán người bán hàng rong
  • Bài toán NP-khó
  • Phương pháp đơn hình

Chú thích

[1] [2] [3] [4] [5] [6] </references>

  1. ↑ 1.0 1.1 Wikipedia contributors. (2025). Branch and bound. In Wikipedia, The Free Encyclopedia. Retrieved 2025-10-26, from https://en.wikipedia.org/wiki/Branch_and_bound
  2. ↑ 2.0 2.1 Wikipedia contributors. (2023). Метод ветвей и границ. In Русская Википедия. Retrieved 2025-10-26, from https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ
  3. ↑ 3.0 3.1 Land, A. H.; Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520. DOI: 10.2307/1910129. URL: https://www.jstor.org/stable/1910129
  4. ↑ 4.0 4.1 Conitzer, V. (2008). Solving (mixed) integer programs using branch and bound. Duke University, Department of Computer Science. URL: https://courses.cs.duke.edu/spring08/cps296.2/branch_and_bound.pdf
  5. ↑ 5.0 5.1 Maudet, G.; Danoy, G. (2024). Search Strategy Generation for Branch and Bound Using Genetic Programming. arXiv preprint arXiv:2412.09444. DOI: 10.48550/arXiv.2412.09444. URL: https://arxiv.org/abs/2412.09444
  6. ↑ 6.0 6.1 Little, J. D. C.; Murty, K. G.; Sweeney, D. W.; Karel, C. (1963). An Algorithm for the Traveling Salesman Problem. Operations Research, 11(6), 972–989. DOI: 10.1287/opre.11.6.972. URL: https://dspace.mit.edu/bitstream/handle/1721.1/46907/branchboundmetho00litt.pdf
Retrieved from "https://systems-analysis.ru/int/index.php?title=Phương_pháp_nhánh_và_cận&oldid=17079"