算法调度最佳记录列表

进出口寻找一种算法，用于产生给定下列项目列表的记录装置的最佳记录列表：算法调度最佳记录列表

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

的算法是基于本文件：