Thuật toán ngẫu nhiên và thuật toán xấp xỉ
Các thuật toán ngẫu nhiên và xấp xỉ đánh đổi tính chính xác hoặc tính xác định để đạt được hiệu quả: thuật toán ngẫu nhiên sử dụng các lựa chọn ngẫu nhiên để tăng tốc độ hoặc sự đơn giản, trong khi thuật toán xấp xỉ tìm các giải pháp gần tối ưu có thể chứng minh được cho các vấn đề quá khó để giải quyết chính xác.
Definition
Các thuật toán ngẫu nhiên đưa ra các lựa chọn ngẫu nhiên trong quá trình thực thi và được phân tích về thời gian chạy dự kiến hoặc xác suất chính xác; các thuật toán xấp xỉ chạy hiệu quả và trả về các giải pháp được đảm bảo nằm trong một yếu tố đã được chứng minh là tối ưu cho các bài toán tối ưu hóa khó.
Scope
Lĩnh vực này bao gồm các thuật toán nới lỏng mục tiêu về một câu trả lời chính xác, có tính xác định. Nó bao gồm các thuật toán ngẫu nhiên (Las Vegas và Monte Carlo), với các đảm bảo xác suất của chúng; các thuật toán xấp xỉ cho tối ưu hóa NP-khó với tỷ lệ xấp xỉ đã được chứng minh; và các thuật toán trực tuyến phải đưa ra quyết định mà không biết trước tương lai, được phân tích bằng tỷ lệ cạnh tranh. Đây là những phản ứng tiêu chuẩn đối với tính không khả thi và các tình huống không chắc chắn, được xây dựng dựa trên phân tích độ phức tạp và các mô hình thiết kế.
Sub-topics
Core questions
- Làm thế nào tính ngẫu nhiên cải thiện thời gian chạy, sự đơn giản hoặc tính mạnh mẽ?
- Sự khác biệt giữa các đảm bảo của Las Vegas và Monte Carlo là gì?
- Chất lượng của một thuật toán xấp xỉ được định lượng bằng tỷ lệ xấp xỉ như thế nào?
- Những bài toán NP-khó nào cho phép xấp xỉ tốt, và những bài toán nào chống lại chúng?
- Các quyết định trực tuyến, được đưa ra mà không có thông tin trong tương lai, được đánh giá cạnh tranh như thế nào?
Key concepts
- thuật toán ngẫu nhiên
- Las Vegas và Monte Carlo
- thời gian chạy dự kiến
- bất đẳng thức tập trung
- tỷ lệ xấp xỉ
- sơ đồ xấp xỉ thời gian đa thức
- thuật toán trực tuyến
- tỷ lệ cạnh tranh
Key theories
- Ngẫu nhiên hóa để đạt hiệu quả
- Các lựa chọn ngẫu nhiên có thể tạo ra các thuật toán nhanh hơn hoặc đơn giản hơn so với các thuật toán xác định tốt nhất, với các đảm bảo về thời gian dự kiến (Las Vegas) hoặc về xác suất lỗi (Monte Carlo), thường sử dụng các bất đẳng thức tập trung để phân tích.
- Tỷ lệ xấp xỉ cho các bài toán NP-khó
- Khi các giải pháp chính xác không khả thi, một thuật toán xấp xỉ cung cấp một giải pháp có thể chứng minh được nằm trong một yếu tố (tỷ lệ xấp xỉ) của tối ưu; tỷ lệ có thể đạt được đặc trưng cho mức độ một vấn đề có thể được xấp xỉ tốt.
Clinical relevance
Các phương pháp này là bộ công cụ thực tế cho các vấn đề khó và không chắc chắn: các thuật toán ngẫu nhiên thúc đẩy kiểm tra tính nguyên tố trong mật mã học, băm và cân bằng tải; các thuật toán xấp xỉ tạo ra các giải pháp khả thi cho các bài toán lập lịch, định tuyến, phân cụm và định vị cơ sở NP-khó; và các thuật toán trực tuyến mô hình hóa bộ nhớ đệm, phân trang và phân bổ tài nguyên, nơi các quyết định phải được đưa ra trong thời gian thực.
History
Các thuật toán ngẫu nhiên trở nên nổi bật với các kiểm tra tính nguyên tố Solovay-Strassen và Rabin vào những năm 1970 và sự ủng hộ rộng rãi hơn của Rabin đối với các phương pháp xác suất. Các thuật toán xấp xỉ phát triển cùng với lý thuyết NP-hoàn chỉnh từ những năm 1970, và phân tích cạnh tranh của các thuật toán trực tuyến được Sleator và Tarjan chính thức hóa vào những năm 1980, cùng nhau hình thành nghiên cứu hiện đại về các thuật toán không chính xác và xác suất.
Key figures
- Rajeev Motwani
- Prabhakar Raghavan
- Vijay Vazirani
- Michael Rabin
- Robert Solovay
- Volker Strassen
Related topics
Seminal works
- motwani1995
- vazirani2001
- cormen2009
Frequently asked questions
- Các thuật toán ngẫu nhiên có không đáng tin cậy vì chúng sử dụng tính ngẫu nhiên không?
- Không. Các thuật toán Las Vegas luôn trả về một câu trả lời đúng và chỉ thời gian chạy của chúng thay đổi. Các thuật toán Monte Carlo có thể mắc lỗi, nhưng xác suất lỗi có thể được giảm xuống tùy ý bằng cách lặp lại. Các đảm bảo của chúng là các tuyên bố xác suất chính xác, không phải là sự không thể đoán trước.
- Tại sao lại sử dụng thuật toán xấp xỉ thay vì chỉ tìm giải pháp tối ưu?
- Đối với các bài toán tối ưu hóa NP-khó, việc tìm ra giá trị tối ưu chính xác có thể không khả thi đối với các đầu vào lớn. Một thuật toán xấp xỉ chạy trong thời gian đa thức và đảm bảo một giải pháp nằm trong một yếu tố đã biết của tối ưu, điều này thường đủ tốt và thực tế hơn nhiều so với việc chờ đợi một câu trả lời chính xác.