算法調度最佳記錄列表

進出口尋找一種算法，用於產生給定下列項目列表的記錄裝置的最佳記錄列表：算法調度最佳記錄列表

Image link here http://img692.imageshack.us/img692/7952/recordlist.png

目前的約束是：

無重疊必須存在。
在計算速度和解決衝突之間妥協。

在將來有可能更多的選擇將被添加：

可能性用戶有幾個錄音設備。
用戶可以爲他/她的收藏夾程序建立錄製優先級（1個最高--3個最低）。

上下文如下：

項目列表在1周爲最大值（當前時間 - 當前時間+ 1周）
平均項列表尺寸是100項和300最大。

此外，我想知道是否有產生的情況下，最佳的可記錄列表（發送到記錄的節目比例最高）我們不可能解決衝突的100％的方式不管處理時間。

在此先感謝。

來源

2012-09-03 user1642390

你如何定義最優性，目標是什麼？ – Qnan

如果您想要一個優雅而有趣的方式來解決這個問題，請使用遺傳算法。如果您只想快速完成並繼續前進，請使用貪婪。我不確定這是否是NP完整的。另請描述輸入和輸出的格式。 – Superbest

class Recording 
{ 
    public int ProgrammeId { get; set; } 
    public string ProgrammeTitle { get; set; } 
    public DateTime StartTime { get; set; } 
    public DateTime EndTime { get; set; } 
    public int ChannelId { get; set; } 
    public string ChannelName { get; set; } 
    public int Weight { get { return 1; } } // Constant weight 
}

貪婪的做法是按照增加start_time的順序考慮程序。如果程序是與先前選定的程序兼容，選擇它：

public static IEnumerable<Recording> GreedySelection(IList<Recording> data) 
{ 
    data = data 
     .OrderBy(r => r.StartTime) 
     .ThenBy(r => r.EndTime) 
     .ToList(); 

    DateTime? lastEnd = null; 
    foreach (var rec in data) 
    { 
     if (lastEnd == null || rec.StartTime >= lastEnd.Value) 
     { 
      yield return rec; 
      lastEnd = rec.EndTime; 
     } 
    } 
}

得到最優加權的解決方案，你可以使用動態規劃：

public static IEnumerable<Recording> WeightedSelection(IList<Recording> data) 
{ 
    data = data 
     .OrderBy(r => r.EndTime) 
     .ThenBy(r => r.StartTime) 
     .ToList(); 

    int count = data.Count; 
    var lastCompatible = new int?[count]; 

    // Compute the closest program before in time, that is compatible. 
    // This nested loop might be optimizable in some way. 
    for (int i = 0; i < count; i++) 
    { 
     for (int j = i - 1; j >= 0; j--) 
     { 
      if (data[j].EndTime <= data[i].StartTime) 
      { 
       lastCompatible[i] = j; 
       break; // inner loop 
      } 
     } 
    } 

    // Dynamic programming to calculate the best path 
    var optimalWeight = new int[count]; 
    var cameFrom = new int?[count]; 
    for (int i = 0; i < count; i++) 
    { 
     int weightWithItem = data[i].Weight; 
     if (lastCompatible[i] != null) 
     { 
      weightWithItem += optimalWeight[lastCompatible[i].Value]; 
     } 

     int weightWithoutItem = 0; 
     if (i > 0) weightWithoutItem = optimalWeight[i-1]; 

     if (weightWithItem < weightWithoutItem) 
     { 
      optimalWeight[i] = weightWithoutItem; 
      cameFrom[i] = i - 1; 
     } 
     else 
     { 
      optimalWeight[i] = weightWithItem; 
      cameFrom[i] = lastCompatible[i]; 
     } 
    } 

    // This will give the programs in reverse order. 
    for (int? i = count - 1; i != null; i = cameFrom[i.Value]) 
    { 
     yield return data[i.Value]; 
    } 
}

不是這個版本採用了重量，並嘗試以最大化權重總和。如果所有權重均設爲一（1），則兩個算法的結果大小將具有相同的大小，因爲大小等於權重。

結果的貪婪：動態的

ProgrammeTitle   StartTime   EndTime 
Star Trek    2012-09-03 02:05 2012-09-03 03:05 
Everybody Loves Raymond 2012-09-03 06:00 2012-09-03 07:00 
CSI      2012-09-03 07:00 2012-09-03 08:00 
Mythbusters    2012-09-03 08:00 2012-09-03 09:00 
CSI      2012-09-03 10:00 2012-09-03 11:00 
Mythbusters    2012-09-03 11:00 2012-09-03 12:00 
Star Trek    2012-09-04 02:05 2012-09-04 03:05 
Everybody Loves Raymond 2012-09-04 06:00 2012-09-04 07:00 
CSI      2012-09-04 07:00 2012-09-04 08:00 
Mythbusters    2012-09-04 08:00 2012-09-04 09:00 
CSI      2012-09-04 10:00 2012-09-04 11:00 
Mythbusters    2012-09-04 11:00 2012-09-04 12:00

結果（排序）：

ProgrammeTitle   StartTime   EndTime 
Everybody Loves Raymond 2012-09-03 03:00 2012-09-03 04:00 
Everybody Loves Raymond 2012-09-03 06:00 2012-09-03 07:00 
CSI      2012-09-03 07:00 2012-09-03 08:00 
CSI      2012-09-03 08:30 2012-09-03 09:30 
CSI      2012-09-03 10:00 2012-09-03 11:00 
Star Trek    2012-09-03 11:05 2012-09-03 12:05 
Everybody Loves Raymond 2012-09-04 03:00 2012-09-04 04:00 
Everybody Loves Raymond 2012-09-04 06:00 2012-09-04 07:00 
CSI      2012-09-04 07:00 2012-09-04 08:00 
CSI      2012-09-04 08:30 2012-09-04 09:30 
CSI      2012-09-04 10:00 2012-09-04 11:00 
Star Trek    2012-09-04 11:05 2012-09-04 12:05

的算法是基於本文件：