Quay lui và Nhánh cận

Quay lui (backtracking) và nhánh cận (branch and bound) là các mô hình tìm kiếm có hệ thống, khám phá không gian các nghiệm ứng viên dưới dạng cây, cắt tỉa các cây con không thể dẫn đến một nghiệm hợp lệ hoặc tối ưu để làm cho các tìm kiếm có độ phức tạp hàm mũ trở nên khả thi trên thực tế.

Definition

Quay lui là một tìm kiếm theo chiều sâu trên cây các nghiệm ứng viên cục bộ, cắt tỉa một nhánh ngay khi ứng viên cục bộ không thể hoàn thành thành một nghiệm hợp lệ; nhánh cận bổ sung điều này bằng các cận số trên mục tiêu để các nhánh có giá trị tốt nhất có thể không thể vượt qua nghiệm hiện tại sẽ bị loại bỏ.

Scope

Chủ đề này bao gồm các kỹ thuật tìm kiếm vét cạn được tổ chức xung quanh một cây tìm kiếm: quay lui, từ bỏ các ứng viên cục bộ ngay khi chúng vi phạm một ràng buộc, và nhánh cận, sử dụng các cận trên giá trị mục tiêu tốt nhất có thể đạt được để cắt tỉa các cây con trong tối ưu hóa. Nó bao gồm các ví dụ về thỏa mãn ràng buộc (bài toán N-queens, tô màu đồ thị, Sudoku) và các ví dụ về tối ưu hóa tổ hợp (bài toán người bán hàng, quy hoạch nguyên), và thảo luận lý do tại sao các phương pháp này vẫn có giá trị đối với các bài toán NP-khó mặc dù có chi phí hàm mũ trong trường hợp xấu nhất.

Core questions

• Không gian nghiệm của một bài toán được mô hình hóa như một cây tìm kiếm các phép gán cục bộ như thế nào?
• Những kiểm tra ràng buộc nào cho phép quay lui cắt tỉa các nhánh không khả thi sớm?
• Các cận dưới và cận trên được tính toán như thế nào để cắt tỉa các nhánh trong tối ưu hóa?
• Thứ tự phân nhánh và cận ảnh hưởng đến hiệu suất thực tế như thế nào?
• Tại sao các phương pháp này được sử dụng cho các bài toán NP-khó mặc dù có trường hợp xấu nhất là hàm mũ?

Key concepts

• cây tìm kiếm
• khám phá theo chiều sâu
• lan truyền ràng buộc
• cắt tỉa
• hàm cận
• nghiệm hiện tại
• bài toán N-queens
• nới lỏng quy hoạch nguyên

Key theories

Cắt tỉa cây tìm kiếm

Cả hai mô hình đều tổ chức các nghiệm ứng viên dưới dạng một cây được khám phá theo chiều sâu; tính đúng đắn đến từ sự vét cạn, trong khi hiệu quả đến từ việc cắt tỉa các cây con mà chứng minh được rằng không thể chứa một nghiệm hợp lệ hoặc cải thiện.

Hàm cận trong nhánh cận

Nhánh cận duy trì nghiệm tốt nhất đã tìm thấy cho đến nay và một cận (ví dụ: nới lỏng LP) trên giá trị tốt nhất có thể đạt được trong mỗi cây con; một cây con bị loại bỏ khi cận của nó không thể cải thiện nghiệm hiện tại.

Clinical relevance

Nhánh cận là xương sống của tối ưu hóa tổ hợp chính xác trong nghiên cứu vận trù học, bao gồm các bộ giải quy hoạch nguyên và quy hoạch nguyên hỗn hợp được sử dụng để lập lịch, định tuyến và lập kế hoạch. Quay lui là nền tảng của các bộ giải ràng buộc, tìm kiếm kiểu SAT, bộ giải câu đố và bộ phân tích cú pháp, nơi tìm kiếm có hệ thống với cắt tỉa là con đường thực tế để có được các câu trả lời chính xác.

History

Quay lui được hệ thống hóa thành một kỹ thuật tổng quát vào những năm 1950 và 1960, đáng chú ý được mô tả bởi Golomb và Baumert. Nhánh cận được giới thiệu bởi Ailsa Land và Alison Doig vào năm 1960 cho quy hoạch tuyến tính nguyên và từ đó đã trở thành trung tâm của tối ưu hóa tổ hợp, cung cấp sức mạnh cho các bộ giải quy hoạch nguyên hỗn hợp hiện đại.

Key figures

• Ailsa Land
• Alison Doig
• Solomon Golomb
• Robert Bixby

Seminal works

• landdoig1960
• cormen2009

Frequently asked questions

Sự khác biệt giữa quay lui và nhánh cận là gì?

Quay lui thường được sử dụng cho các bài toán khả thi và thỏa mãn ràng buộc và cắt tỉa các nhánh vi phạm ràng buộc. Nhánh cận nhắm mục tiêu tối ưu hóa và bổ sung cắt tỉa bằng cách sử dụng các cận số, loại bỏ bất kỳ cây con nào mà mục tiêu tốt nhất có thể của nó không thể vượt qua nghiệm tốt nhất đã tìm thấy.

Nếu các phương pháp này có độ phức tạp hàm mũ trong trường hợp xấu nhất, tại sao lại sử dụng chúng?

Đối với các bài toán NP-khó, không có thuật toán chính xác đa thức nào được biết đến, nhưng việc cắt tỉa hiệu quả thường loại bỏ phần lớn cây tìm kiếm trên các trường hợp thực tế, do đó các bộ giải nhánh cận và quay lui thường xuyên tìm thấy các nghiệm tối ưu đã được chứng minh nhanh hơn nhiều so với dự đoán của các cận trong trường hợp xấu nhất của chúng.