次の項目リストが与えられた録音デバイスに最適なレコード リストを生成するためのアルゴリズムを探しています。
画像リンクはこちら http://img692.imageshack.us/img692/7952/recordlist.png
現時点での制約は次のとおりです。
将来的には、より多くのオプションが追加される可能性があります。
コンテキストは次のとおりです。
また、処理時間に関係なく競合を 100% 解決できない場合に、可能な限り最適なレコード リスト (録画に送信される番組の割合が最も高い) を生成する方法があるかどうかも知りたいです。
前もって感謝します。
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
アルゴリズムは、次のドキュメントに基づいています。
First Fit DecreningとTabu Searchを使用します。
この使用例は、看護師の勤務表作成 (このビデオを参照)に非常に似ています。看護師にシフトを割り当てる代わりに、アイテムをレコーダーに割り当てます。ここで、レコーダーは [recorder1, notRecorded] のリストです。