Thuật toán sắp xếp cho một vấn đề sắp xếp dựa trên không so sánh?

Question

Tôi hiện đang phải đối mặt với một vấn đề phân loại khó khăn. Tôi có một bộ sưu tập các sự kiện cần được sắp xếp với nhau (một số comparison sort) và chống lại vị trí tương đối của chúng trong danh sách. Trong điều kiện đơn giản nhất, tôi có danh sách các sự kiện mà mỗi người có một ưu tiên (số nguyên), một khoảng thời gian (giây), và một thời gian sớm nhất mà sự kiện có thể xuất hiện trong danh sách. Tôi cần sắp xếp các sự kiện dựa trên mức độ ưu tiên, nhưng không có sự kiện nào có thể xuất hiện trong danh sách trước thời gian xuất hiện sớm nhất của nó. Đây là một ví dụ để (hy vọng) làm cho nó rõ ràng hơn:

// Psuedo C# code 
class Event { int priority; double duration; double earliestTime ; } 

void Example() 
{ 
    Event a = new Event { priority = 1, duration = 4.0, earliestTime = 0.0 }; 
    Event b = new Event { priority = 2, duration = 5.0, earliestTime = 6.0 }; 
    Event c = new Event { priority = 3, duration = 3.0, earliestTime = 0.0 }; 
    Event d = new Event { priority = 4, duration = 2.0, earliestTime = 0.0 }; 

    // assume list starts at 0.0 seconds 
    List<Event> results = Sort(new List<Event> { a, b, c, d }); 

    assert(results[ 0 ] == a); // 4.0 seconds elapsed 
    assert(results[ 1 ] == c); // 7.0 seconds elapsed 
    assert(results[ 2 ] == b); // 12.0 seconds elapsed 
    assert(results[ 3 ] == d); // 14.0 seconds elapsed 
} 

Mục "b" phải đến cuối cùng vì nó không được phép bắt đầu cho đến 6,0 giây trong danh sách, do đó, nó được hoãn lại và "c" được để đi trước "b" mặc dù ưu tiên của nó thấp hơn. (Hy vọng rằng ở trên giải thích vấn đề của tôi, nếu không cho tôi biết và tôi sẽ chỉnh sửa nó.)

Ý tưởng hiện tại của tôi là sử dụng insertion sort để quản lý quá trình sắp xếp. Không giống như nhiều thuật toán phân loại phổ biến khác, sắp xếp chèn sẽ quyết định thứ tự của danh sách một lần và theo thứ tự. Vì vậy, đối với mỗi chỉ số tôi sẽ có thể tìm thấy sự kiện ưu tiên thấp nhất tiếp theo có thời gian xuất hiện sớm nhất sẽ được thỏa mãn.

Tôi hy vọng tìm được tài nguyên về sắp xếp thuật toán và cấu trúc dữ liệu để giúp tôi thiết kế giải pháp tốt cho "sắp xếp" sự cố này. Vấn đề thực sự của tôi thực sự phức tạp hơn điều này: phân loại phân cấp, bộ đệm biến giữa các sự kiện, nhiều ràng buộc thời gian không liên tục, vì vậy càng có nhiều thông tin hoặc ý tưởng càng tốt. Tốc độ và không gian không thực sự là một mối quan tâm. Độ chính xác trong phân loại và bảo trì mã là một mối quan tâm.

Edit: Làm rõ (dựa trên ý kiến)

• Sự kiện tiêu thụ toàn bộ thời gian của họ (có nghĩa là không có sự chồng chéo của các sự kiện cho phép)
• Sự kiện phải xảy ra tại hoặc sau earliestTime của họ, chúng không thể xảy ra trước thời gian sớm nhất của chúng.
• Sự kiện có thể xảy ra muộn hơn earliestTime họ nếu sự kiện ưu tiên thấp hơn tồn tại
• Sự kiện không thể bị gián đoạn
• Có một khoảng thời gian tối đa tổng của tất cả các sự kiện mà có thể phù hợp trong một danh sách. Điều này không được hiển thị ở trên. (Trong thực tế, thời gian của tất cả các sự kiện sẽ lớn hơn nhiều so với thời gian tối đa của danh sách thời gian.)
• Không thể có bất kỳ khoảng trống nào. (Hiện tại không có lỗ để thử và điền lại.)

Edit: trả lời

Trong khi David Nehme đã đưa ra câu trả lời tôi đã chọn, tôi muốn chỉ ra rằng câu trả lời của ông là một loại chèn vào tim và một số người khác đã cung cấp câu trả lời loại câu trả lời. Điều này xác nhận với tôi rằng một loại chèn chuyên dụng có lẽ là con đường để đi. Nhờ tất cả các bạn cho câu trả lời của bạn.

Answer 1

Đây thực sự không chỉ là vấn đề phân loại. Đó là một vấn đề lập kế hoạch một máy với ngày phát hành. Tùy thuộc vào những gì bạn đang cố gắng làm, vấn đề có thể là NP-Hard. Ví dụ, nếu bạn đang cố gắng mimimize các trọng-sum của thời đại hoàn thành (trọng lượng là tỉ lệ nghịch với ưu tiên), các vấn đề là categorized như

1|ri;pmtn|Σ wiCi 

và là NP-hard. Có rất nhiều papers về chủ đề này, nhưng nó có thể nhiều hơn những gì bạn cần.

Trong trường hợp của bạn, bạn không bao giờ muốn một giải pháp có khoảng trống, vì vậy những gì bạn chỉ cần làm là mô phỏng sự kiện rời rạc đơn giản (thời gian O (n log (n))). Bạn cần lưu trữ release_jobs làm hàng đợi ưu tiên.

unreleased_jobs = jobs // sorted list of jobs, by release date 
released_jobs = {}  // priority queue of jobs, by priority 
scheduled_jobs = {}  // simple list 
while (!unreleased_jobs.empty() || !released_jobs.empty()) { 

    while (unreleased_jobs.top().earliestTime <= t) { 
     released_jobs.push(unreleased_jobs.pop()) 
    } 
    if (!released_jobs.empty()) { 
     next_job = released_jobs.pop(); 
     scheduled_jobs.push_back(next_job) 
     t = t + next_job.duration 
    } else { 
     // we have a gap 
     t = unreleased_jobs.top().earliestTime 
    } 
} 

Một vấn đề là bạn có thể có một công việc có mức ưu tiên thấp với thời gian phát hành ngay trước khi một công việc có mức ưu tiên cao ngắn, nhưng nó sẽ tạo ra một lịch trình với các tài sản mà không có khoảng trống (nếu một lịch trình không có khoảng trống là có thể).

Answer 2

Tôi nghĩ bạn nên sắp xếp danh sách hai lần: đầu tiên theo mức độ ưu tiên và sau đó theo thời gian sớm nhất, sử dụng bất kỳ thuật toán sắp xếp ổn định nào. Bằng cách đó, thời gian sẽ tăng lên và mỗi lần mọi thứ sẽ được sắp xếp theo mức độ ưu tiên.

Trừ khi bạn nhìn thấy một cái gì đó tôi không bạn hoàn toàn có thể bỏ qua thời lượng của mỗi sự kiện cho mục đích sắp xếp.

http://en.wikipedia.org/wiki/Category:Stable_sorts

Answer 3

Nói cách khác, bạn muốn tối ưu hóa thời gian hoạt động tổng thể khi xây dựng hai khó khăn (mạnh: Điểm đầu tiên thực hiện, yếu: ưu tiên)? Đây được gọi là constraint satisfaction problem. Có những giải pháp đặc biệt cho loại vấn đề này.

Ngẫu nhiên, giải pháp của jakber không hoạt động. Thậm chí không có thời gian, ví dụ sau đây rõ ràng là thất bại:

event a (priority = 1, start = 5) 
event b (priority = 2, start = 0) 

Trình tự sắp xếp sẽ a, b trong khi kết quả truy nã là chắc chắn b, a.

Answer 4

Có vẻ như bạn thực sự muốn có một loại dựa trên so sánh. Khóa sắp xếp của bạn là {earliestTime, priority}, theo thứ tự đó. Vì ví dụ của bạn là giả C#, tôi sẽ cung cấp cho bạn một giải pháp giả C#:

class Event : IComparable<Event>, IComparable{ 
    int priority; 
    double duration; 
    double earliestTime; 

    public int CompareTo(Event other){ 
     if(other == null) 
      return 1; /* define: non-null > null */ 

     int cmp = earliestTime.CompareTo(other.earliestTime); 
     if(cmp != 0) 
      return cmp; 

     /* earliestTimes were equal, so move on to next comparison */ 
     return priority.CompareTo(other.priority); 
    } 

    int IComparable.CompareTo(object other){ /* for compatibility with non-generic collections */ 
     if(other == null) 
      return 1; /* define: non-null > null */ 

     Event e_other = other as Event; 
     if(e_other == null) /* must have been some other type */ 
      throw new ArgumentException("Must be an Event", "other"); 

     return CompareTo(e_other); /* forward to strongly-typed implementation */ 
    } 
} 

Bây giờ danh sách của bạn sẽ sắp xếp như mong đợi của bạn.

EDIT:

giả ban đầu của tôi là sự kiện sẽ được chọn ra khỏi danh sách và đưa ra một chủ đề riêng biệt, do đó người quản lý hàng đợi có thể bắn ra những sự kiện tiếp theo đúng thời hạn, nhưng từ ý kiến ​​tôi nhận được, tôi đã có ý tưởng rằng có lẽ một cách tiếp cận đó là đơn luồng, nhưng vẫn cho phép các sự kiện có mức độ ưu tiên cao hơn để kích hoạt càng gần càng tốt thời gian bắt đầu của họ là mong muốn hơn. Trong trường hợp đó, chức năng CompareTo sẽ thay đổi như sau:

public int CompareTo(Event other){ 
    if(other == null) 
     return 1; /* define: non-null > null */ 

    int cmp = priority.CompareTo(other.priority); 

    if(cmp == 0) 
     /* 
     * calculate and compare the time each event will be late 
     * if the other one were to start first. This time may be 
     * negative if starting one will not make the other one late 
     */ 
     return (earliestTime + duration - other.earliestTime).CompareTo(
      other.earliestTime + other.duration - earliestTime); 

    /* 
    * they're different priorities. if the lower-priority event 
    * (presume that greater priority index means lower priority, 
    * e.g. priority 4 is "lower" priority than priority 1), would 
    * would make the higher-priority event late, then order the 
    * higher-priority one first. Otherwise, just order them by 
    * earliestTime. 
    */ 
    if(cmp < 0){/* this one is higher priority */ 
     if(earliestTime <= other.earliestTime) 
      /* this one must start first */ 
      return -1; 

     if(other.earliestTime + other.duration <= earliestTime) 
      /* the lower-priority event would not make this one late */ 
      return 1; 

     return -1; 
    } 

    /* this one is lower priority */ 
    if(other.earliestTime <= earliestTime) 
     /* the other one must start first */ 
     return 1; 

    if(earliestTime + duration <= other.earliestTime) 
     /* this event will not make the higher-priority one late */ 
     return -1; 

    return 1; 
} 

Thử nghiệm điều này dựa trên mọi giả định, nhưng tôi nghĩ đó là những gì chúng tôi đang tìm kiếm.

Answer 5

Nếu bạn có một nhóm giới hạn mức độ ưu tiên, bạn có thể giữ một bộ danh sách được sắp xếp theo thời gian, 1 cho mỗi cấp. Bất cứ khi nào bạn cần sự kiện tiếp theo, hãy kiểm tra phần đầu của từng danh sách theo thứ tự ưu tiên cho đến khi bạn tìm thấy một người có thời gian bắt đầu đã trôi qua.(Theo dõi thời gian bắt đầu tối thiểu trong khi bạn kiểm tra - trong trường hợp chưa có sự kiện nào, bạn biết phải đợi sự kiện nào)

Answer 6

Có vẻ như một vấn đề mà tôi đã có ngày khác, được trả lời here.
Giả sử bạn đang sử dụng C# ...

Answer 7

Tôi nghĩ:

1. Sắp xếp công việc bằng cách ưu tiên
2. nhiệm vụ Fit vào một dòng thời gian, lấy khe cắm sẵn đầu tiên sau khi earliestTime của họ, mà có một lỗ đủ lớn cho công việc.

Chuyển đổi dòng thời gian thành danh sách công việc và chờ (để biết khoảng trống).

Câu hỏi:

1. có lỗ hổng cho phép?
2. Các tác vụ có thể được chia nhỏ không?
3. Cho các nhiệm vụ như trong câu hỏi: tốt hơn là trì hoãn b để hoàn thành c, hoặc làm d sao cho b có thể bắt đầu đúng giờ?

Edit:

Os câu trả lời cho câu hỏi của tôi là:

1. Không (ish - nếu không có gì để chạy Tôi đoán chúng ta có thể có một khoảng cách là)
2. Không
3. Vẫn chưa rõ, nhưng tôi đoán ví dụ cho thấy chạy c và trì hoãn b.

Trong trường hợp này các thuật toán có thể là:

1. Sắp xếp theo ưu tiên
2. Giữ một bộ đếm cho dòng 'thời gian' bắt đầu với t = 0
3. Kiếm mặc dù danh sách được sắp xếp, cho mục ưu tiên cao nhất có thể được bắt đầu tại t.
4. Thêm mục vào thứ tự đang chạy và thêm thời lượng của nó vào t.
5. Lặp lại 3 & 4 cho đến khi danh sách hết. Nếu không có nhiệm vụ nào chạy được tại t và có các tác vụ còn lại đang chờ xử lý, hãy gắn một nhiệm vụ ngủ 1 giây vào thứ tự chạy.

Thuật toán này cũng là O (n^2).

Answer 8

Ngẫu nhiên, trong trường hợp chung nhất có thể không có giải pháp (trừ khi các khoảng trống được cho phép, như Douglas đã chỉ ra). Ví dụ:

Event a = new Event { priority = 1, duration = 1.0, earliestTime = 4.0 }; 
Event b = new Event { priority = 2, duration = 1.0, earliestTime = 4.0 }; 
Event c = new Event { priority = 3, duration = 1.0, earliestTime = 4.0 }; 
Event d = new Event { priority = 4, duration = 1.0, earliestTime = 4.0 }; 

Answer 9

Tôi không hoàn toàn chắc chắn tôi hiểu những phức tạp của vấn đề của bạn, nhưng bản năng của tôi nói với tôi bạn cần phải xác định một mối quan hệ giữa ưu tiên và thời gian bắt đầu.Ví dụ sẽ là:

Event a = new Event { priority = 1, duration = 4.0, earliestTime = 1.0 }; 
Event b = new Event { priority = 2, duration = 5.0, earliestTime = 0.0 }; 

Vì vậy, chúng ta đi trước và bắt đầu b lúc = 0, hoặc làm chúng tôi chờ đợi một đánh dấu và sau đó bắt đầu a vì nó ưu tiên cao hơn? Giả sử có nhiều sự kiện hơn với nhiều ưu tiên hơn và cân bằng thời gian lâu hơn. Tôi nghĩ rằng bạn cần một quy tắc dọc theo dòng "nếu sự kiện tiếp theo là X ưu tiên cao hơn và khoảng cách (giữa bây giờ và thời gian sớm nhất) ít hơn Y giây, hãy đợi và sau đó bắt đầu sự kiện ưu tiên cao hơn. sự kiện (do đó đẩy lùi ưu tiên cao) ".

Answer 10

Dưới đây là một số mã Python dọc theo dòng câu trả lời của Douglas. Trước tiên, chúng tôi sắp xếp theo mức độ ưu tiên, sau đó chúng tôi phù hợp với dòng thời gian theo kiểu lựa chọn:

#!/usr/bin/env python 
MIN_PRIORITY = 100 

class Event(object): 
    def __init__(self, name, priority, duration, earliestTime): 
     self.name = name 
     self.priority = priority 
     self.duration = duration 
     self.earliestTime = earliestTime 
    def __str__(self): 
     return "%-10s: P %3d D %3.1f T %3.1f" % (self.name, self.priority, self.duration, self.earliestTime) 

def sortEvents(_events): 
    def comparePriority(event1, event2): 
     if event1.priority < event2.priority: return -1 
     if event1.priority > event2.priority: return 1 
     return 0 

    # Get a copy of the events and sort by priority 
    events = [e for e in _events] 
    events.sort(cmp=comparePriority) 

    # Select one event at a time, checking for compatibility with elapsed time 
    elapsedTime = 0.0 
    sortedEvents = [] 
    while events: 
     minGap = events[0].earliestTime - elapsedTime 
     for e in events: 
      currentGap = e.earliestTime - elapsedTime 
      if currentGap < minGap: 
       minGap = currentGap 
      if currentGap <= 0.0: 
       sortedEvents.append(e) 
       elapsedTime += e.duration 
       events.remove(e) 
       break 

     # If none of the events fits, add a suitable gap 
     if minGap > 0: 
      sortedEvents.append(Event("gap", MIN_PRIORITY, minGap, elapsedTime)) 
      elapsedTime += minGap 
    return sortedEvents 

if __name__ == "__main__": 
    #e1 = Event("event1", 1, 1.0, 4.0) 
    #e2 = Event("event2", 2, 1.0, 6.0) 
    #e3 = Event("event3", 3, 1.0, 8.0) 
    #e4 = Event("event4", 4, 1.0, 10.0) 

    e1 = Event("event1", 1, 4.0, 0.0) 
    e2 = Event("event2", 2, 5.0, 6.0) 
    e3 = Event("event3", 3, 3.0, 0.0) 
    e4 = Event("event4", 4, 2.0, 0.0) 

    events = [e1, e2, e3, e4] 

    print "Before:" 
    for event in events: print event 
    sortedEvents = sortEvents(events) 
    print "\nAfter:" 
    for event in sortedEvents: print event