Thuật toán trực tuyến

Các thuật toán trực tuyến phải đưa ra các quyết định không thể đảo ngược khi dữ liệu đầu vào đến, mà không có kiến thức về các yêu cầu trong tương lai; chất lượng của chúng được đo lường bằng phân tích cạnh tranh so với một thuật toán tối ưu có thể xem toàn bộ dữ liệu đầu vào trước.

Definition

Một thuật toán trực tuyến nhận đầu vào dưới dạng một chuỗi các yêu cầu và phải phản hồi từng yêu cầu ngay lập tức và không thể đảo ngược mà không nhìn thấy các yêu cầu trong tương lai; tỷ lệ cạnh tranh của nó là tỷ lệ trường hợp xấu nhất giữa chi phí của nó và chi phí của một thuật toán ngoại tuyến tối ưu biết toàn bộ chuỗi yêu cầu.

Scope

Chủ đề này bao gồm các thuật toán xử lý đầu vào tuần tự và cam kết các quyết định trước khi biết dữ liệu đầu vào sau này, cũng như khuôn khổ tỷ lệ cạnh tranh được sử dụng để đánh giá chúng so với một đối thủ ngoại tuyến tối ưu. Nó bao gồm các vấn đề kinh điển — phân trang và bộ nhớ đệm, cập nhật danh sách, vấn đề thuê ván trượt, vấn đề k-máy chủ, và lập lịch trực tuyến và đóng gói thùng — và vai trò của việc ngẫu nhiên hóa trong việc cải thiện tỷ lệ cạnh tranh so với các đối thủ yếu hơn.

Core questions

• Các thuật toán trực tuyến được đánh giá như thế nào khi tương lai không thể biết trước?
• Tỷ lệ cạnh tranh đo lường điều gì, và đối thủ ngoại tuyến là gì?
• Các vấn đề kinh điển như phân trang và thuê ván trượt minh họa sự đánh đổi trực tuyến như thế nào?
• Việc ngẫu nhiên hóa có thể cải thiện khả năng cạnh tranh chống lại một đối thủ không biết gì như thế nào?
• Những giới hạn dưới nào hạn chế mức độ cạnh tranh của bất kỳ thuật toán trực tuyến nào?

Key concepts

• trực tuyến so với ngoại tuyến
• tỷ lệ cạnh tranh
• đối thủ ngoại tuyến
• phân trang và bộ nhớ đệm
• cập nhật danh sách
• vấn đề thuê ván trượt
• vấn đề k-máy chủ
• khả năng cạnh tranh ngẫu nhiên

Key theories

Phân tích cạnh tranh

Phân tích cạnh tranh đánh giá một thuật toán trực tuyến bằng tỷ lệ trường hợp xấu nhất giữa chi phí của nó và chi phí của một thuật toán ngoại tuyến tối ưu, đưa ra một đảm bảo có giá trị đối với bất kỳ chuỗi đầu vào nào thay vì dựa vào các giả định về đầu vào.

Ngẫu nhiên hóa chống lại các đối thủ không biết gì

Các thuật toán trực tuyến ngẫu nhiên có thể đạt được tỷ lệ cạnh tranh tốt hơn đáng kể so với bất kỳ thuật toán xác định nào chống lại một đối thủ không biết gì, bởi vì đối thủ phải cố định đầu vào mà không biết các lựa chọn ngẫu nhiên của thuật toán.

Clinical relevance

Các thuật toán trực tuyến mô hình hóa các quyết định mà hệ thống đưa ra trong thời gian thực mà không có kiến thức trong tương lai: thay thế bộ nhớ đệm và trang trong hệ điều hành và CPU, tự tổ chức cấu trúc dữ liệu, phân bổ tài nguyên động và cân bằng tải, và các quyết định thuê hoặc mua trong điện toán đám mây. Phân tích cạnh tranh đưa ra các đảm bảo trường hợp xấu nhất cho các hệ thống phản ứng như vậy.

History

Phân tích cạnh tranh được Sleator và Tarjan giới thiệu vào năm 1985 thông qua nghiên cứu của họ về các quy tắc cập nhật danh sách và phân trang, định hình lại việc đánh giá các thuật toán trực tuyến xung quanh việc so sánh với một giải pháp ngoại tuyến tối ưu. Khuôn khổ này đã mở rộng thông qua vấn đề k-máy chủ và các thuật toán trực tuyến ngẫu nhiên vào những năm 1990, được khảo sát trong chuyên khảo năm 1998 của Borodin và El-Yaniv.

Key figures

• Daniel Sleator
• Robert Tarjan
• Allan Borodin
• Ran El-Yaniv

Seminal works

• sleator1985
• borodin1998
• cormen2009

Frequently asked questions

Tỷ lệ cạnh tranh là gì?

Đó là tỷ lệ trường hợp xấu nhất giữa chi phí của một thuật toán trực tuyến và chi phí của một thuật toán tối ưu có thể xem toàn bộ đầu vào trước. Một thuật toán cạnh tranh 2 không bao giờ tốn kém hơn hai lần chi phí ngoại tuyến tốt nhất có thể trên bất kỳ chuỗi đầu vào nào.

Tại sao việc ngẫu nhiên hóa lại giúp ích cho các thuật toán trực tuyến?

Chống lại một đối thủ không biết gì cố định đầu vào mà không nhìn thấy các lựa chọn ngẫu nhiên của thuật toán, việc ngẫu nhiên hóa ngăn cản đối thủ điều chỉnh một trường hợp xấu nhất theo hành vi của thuật toán, cho phép đạt được tỷ lệ cạnh tranh tốt hơn đáng kể so với bất kỳ thuật toán xác định nào có thể đạt được.