Tìm các che chắn tối thiểu của một khoảng thời gian với subintervals

Question

Giả sử tôi có một khoảng (a, b), và một số subintervals {(a _i, b _i)} _i mà công đoàn là tất cả (a, b). Có cách nào hiệu quả để chọn một tập hợp con nhỏ nhất của các phân đoạn này vẫn bao gồm (a, b) không?

Answer 1

Thuật toán tham lam bắt đầu từ a hoặc b luôn mang lại giải pháp tối ưu.

Bằng chứng: xem xét bộ S _a của tất cả các khoảng con bao gồm a. Rõ ràng, một trong số đó phải thuộc về giải pháp tối ưu. Nếu chúng ta thay thế nó bằng một subinterval (một max , b _max) từ S _một mà ngay endpoint b _max là tối đa trong S _{một (đạt xa nhất bên phải), khoảng thời gian phát hiện còn lại} (b _max, b) sẽ là một tập hợp con của khoảng thời gian còn lại từ giải pháp tối ưu, vì vậy nó có thể được bao phủ không có khoảng cách nhỏ hơn khoảng thời gian phát hiện tương tự từ giải pháp tối ưu.Do đó, một giải pháp được xây dựng từ (a _max, b _max) và giải pháp tối ưu cho khoảng thời gian còn lại (b _max, b) cũng sẽ tối ưu.

Vì vậy, chỉ cần bắt đầu tại một và lặp lại chọn khoảng thời gian đạt đến bên phải xa nhất (và bao gồm kết thúc của khoảng thời gian trước đó), lặp lại cho đến khi bạn nhấn b. Tôi tin rằng việc chọn khoảng thời gian tiếp theo có thể được thực hiện trong log (n) nếu bạn lưu trữ các khoảng trong một cây khoảng thời gian tăng cường.

Answer 2

Âm thanh như lập trình động.

Dưới đây là một minh hoạ của thuật toán (giả định khoảng thời gian nằm trong danh sách được sắp xếp theo thời gian kết thúc):

//works backwards from the end 
int minCard(int current, int must_end_after) 
{ 
    if (current < 0) 
     if (must_end_after == 0) 
      return 0; //no more intervals needed 
     else 
      return infinity; //doesn't cover (a,b) 

    if (intervals[current].end < must_end_after) 
     return infinity; //doesn't cover (a,b) 

    return min(1 + minCard(current - 1, intervals[current].start), 
       minCard(current - 1, must_end_after)); 
      //include current interval or not? 
} 

Nhưng nó cũng nên liên quan đến bộ nhớ đệm (memoisation).

Answer 3

Bạn có nghĩa là các khoảng con vẫn chồng chéo theo cách sao cho (a, b) vẫn được bao phủ hoàn toàn ở tất cả các điểm?

Có thể chia nhỏ các đoạn con thành các khối cơ bản liên quan đến chúng đến từ đâu, vì vậy bạn có thể liệt kê các tùy chọn cho mỗi khoảng khối cơ bản kế toán cho các khu vực khác được bao phủ bởi khoảng con. Sau đó, bạn có thể sử dụng một tìm kiếm dựa trên mỗi sub-subinterval và ít nhất là chắc chắn không có khoảng trống còn lại.
Sau đó, cần phải tìm kiếm .. hiệu quả .. điều đó sẽ khó hơn.

Có thể loại bỏ bất kỳ tập hợp các khoảng thời gian nào được bao phủ hoàn toàn bởi một tập số nhỏ hơn và xử lý vấn đề sau khi xử lý trước.
Sẽ không tối thiểu cho toàn bộ tối thiểu cho ít nhất một nửa? Tôi không chắc.

Tìm thấy một link vào nhật ký nhưng không đọc được. :(

Đây sẽ là một vấn đề hitting set và được NP_hard nói chung.
Không thể đọc this một trong hai nhưng trông giống như loại đối diện của vấn đề.
Không thể đọc nó nhưng khác link đề cập đến khoảng thời gian chia tay.
Here là một tài liệu tham khảo có sẵn trên ngẫu nhiên thuật toán cho GeometricOptimization vấn đề.
trang 35 của pdf này có một thuật toán tham lam.
trang 11 của Karp (1972) đề cập đến đánh thiết lập và được trích dẫn rất nhiều.
01.Google result. Nghiên cứu thật vui nhưng tôi phải đi ngay bây giờ.

Answer 4

Có hai trường hợp cần xem xét: Trường hợp 1: Không có khoảng thời gian quá giới hạn sau thời gian kết thúc của một khoảng thời gian. Trong trường hợp này, chọn khoảng thời gian tiếp theo với thời gian bắt đầu nhỏ nhất và thời gian kết thúc dài nhất. (amin, bmax). Trường hợp 2: Có một hoặc nhiều khoảng thời gian quá giới hạn với khoảng thời gian cuối cùng bạn đang xem. Trong trường hợp này, thời gian bắt đầu không quan trọng vì bạn đã bảo hiểm điều đó. Vì vậy, tối ưu hóa cho thời gian hoàn thiện. (a, bmax).

Trường hợp 1 luôn chọn khoảng thời gian đầu tiên làm khoảng thời gian đầu tiên trong tập hợp tối ưu (bằng chứng giống như những gì @RafalDowgrid cung cấp).