0

我正在寻找一种算法来为给定以下项目列表的记录设备生成最佳记录列表:

图片链接在这里 http://img692.imageshack.us/img692/7952/recordlist.png

目前的限制是:

  • 不得存在重叠。
  • 在计算速度和解决的冲突之间妥协。

将来可能会添加更多选项:

  • 用户可以拥有多个录音设备。
  • 用户可以为他/她喜欢的节目建立录制优先级(1 最高 - 3 最低)。

上下文如下:

  • 项目列表最长为 1 周。(当前时间 - 当前时间 + 1 周)
  • 平均项目列表大小为 100 个项目,最大为 300 个。

另外我想知道是否有一种方法可以生成最优化的记录列表(发送到记录的程序的最高百分比),以防我们无法解决 100% 的冲突,而不管处理时间如何。

提前致谢。

4

2 回答 2

1
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

算法基于此文档:

于 2012-09-03T23:11:30.053 回答
0

使用首次拟合递减禁忌搜索

此用例与护士排班非常相似(请参阅此视频):您不是将轮班分配给护士,而是将项目分配给记录器,其中记录器是 [recorder1, notRecorded] 的列表。

于 2012-09-25T11:47:47.820 回答