如何确定给定范围内优化间隔计数？ [英] How to determine optimal interval count in a given range?
问题描述
我试图确定这种棘手的问题的最佳解决方案。我有一个长（比方说11）。所以这是一个一维空间0-10。现在，我已经得到了这些区间是同一个的长度（假设2在这个例子中）。现在，他们随机分布的（重叠的，或者不是）。让我画一个例子：
情况：
| 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | ＆LT; - 空间（长度= 11）
| ----- |
| ----- |
| ----- |
| ----- |
| ----- |
| ----- | ＆LT; - 长单时间间隔= 2
现在该解决方案需要找到间隔可以容纳一次没有重叠的最大数量。
解决的办法是：4个间隔
有4个间隔三个结果：
| 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 |
| ----- | | ----- | ----- | | ----- | ＆LT; - 结果1
| ----- | | ----- | | ----- | | ----- | ＆LT; - 结果2
| ----- | | ----- | ----- | | ----- | ＆LT; - 结果3
但也有两个制约因素以及。
-
如果有更多的结果（最好的解决方案，在这种情况下= 4），则所述一个具有最少数量的间隙。
-
如果有更多的结果还是一个与它的所有空间的最高最小长度。例如一个与空间2及（的长度）; 3具有空间= 2最小长度，即比1和更好; 4，其中的空间中的最小长度只有1
所以，结果2有4个持续大块，另外两个只有3所以细化为：
| 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 |
| ----- | | ----------- | | ----- | ＆LT; - 结果1
| ----- | | ----------- | | ----- | ＆LT; - 结果3
这两个得到了它们之间的相同的空间分布，因此让我们第一次。
结果为输入设置为：
间隔数：4
最佳的解决方案：| ----- | | ----------- | | ----- |
该算法具有普遍适用于所有的空间长度（不仅是11），所有的间隔长度（区间长度总是＆LT; =空间长度）和任意数量的间隔。
更新：
有问题的情况：
| 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 |
| ----- |
| ----- |
| ----- |
| ----- |
| ----- |
这是一个简单的动态规划问题。
让总长度为 N 和任务的长度是→。
让 F（T）是可以从子区间来选择任务最大数量（T，N），系统则在每单位时间T，有3种可能性：
- 在没有任务，在T.启动
- 还有就是在T开头的任务，但我们不包括在结果集中。
- 还有就是在T开头的任务，我们也包括它在结果集。
第1种情况很简单，我们只需要 F（T）= F（T + 1）。
在2/3的情况下，注意选择启动任务的 T 意味着我们必须拒绝接受这个任务运行时，也就是在<$ C开头的所有任务$ C> T 和 T + L 。所以，我们得到 F（T）= MAX（F（T + 1），F（T + 1）+ 1）。
最后， F（N）= 0 。所以，你刚刚从<$ C $ C>启动F（N）和你的工作方式回到 F（0）。
编辑：这会给你时间间隔的最大数量，但不是说满足您2约束集。您的约束解释，我不清楚，所以我不知道如何帮助你。特别是，我不能告诉约束1表示，因为所有的解决方案，以你的例子集显然平等的。
编辑2：一些进一步的解释，要求：
考虑您张贴的例子，我们有 N = 11 和 L = 2 。有迹象表明，在启动T = 0，3，4，5，6，9 任务。从 F开始（11）= 0 和工作倒退：
-
F（11）= 0 -
F（10）= F（11）= 0（由于没有任务开始于T = 10） -
F（9）= MAX（F（10），F（11）+ 1）= 1 - ...
最后，我们得到 F（0）= 4 ：
T | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 |
F（T）| 4 | 3 | 3 | 3 | 3 | 2 | 2 | 1 | 1 | 1 | 0 |
修改3：好吧我很好奇这一点，我写了一个解决方案，因此不妨将它张贴。这会给你拥有的首要任务，用最少的多项空白，最小的最小间隙设定。在讨论的实施例的输出是：
-
（0,2） - ＆GT; （4,6） - ＆GT; （6,8） - ＆GT; （9,11） -
（0,2） - ＆GT; （4,6） - ＆GT; （8,10）
很显然，我做不保证正确性！ ：）
私有类任务 { 公众诠释启动{获得;组; } 公众诠释长度{获得;组; } 公众诠释结束{{返回起始+长度; }}
公共重写字符串的ToString（）
{
返回的String.Format（（{0：D}，{1：D}），开始，结束）;
}
}
私有类CacheEntry：IComparable的
{
公众诠释任务{获得;组; }
公众诠释差距{获得;组; }
公众诠释MinGap {获得;组; }
公共任务任务{获得;组; }
公共任务NextTask {获得;组; }
公众诠释的CompareTo（obj对象）
{
VAR其他= OBJ为CacheEntry;
如果（任务！= other.Tasks）
返回任务 - other.Tasks; //更多的任务比较好
如果（差距！= other.Gaps）
返回other.Gaps =差距; //少差距比较好
返回MinGap - other.MinGap; //更大最小间隙是更好
}
}
私有静态的IList＆LT;任务＆GT; F（IList的＆LT;任务＆GT;任务）
{
VAR结束= tasks.Max（X =＆GT; x.End）;
VAR tasksByTime = tasks.ToLookup（X =＆GT; x.Start）;
VAR缓存=新的名单，其中，CacheEntry＆GT; [月底+ 1];
缓存[结束] =新的名单，其中，CacheEntry＆GT; {新CacheEntry {任务= 0，差距= 0，MinGap =结束+ 1}};
对于（INT T =结束 - 1; T＆GT; = 0; T--）
{
如果（！tasksByTime.Contains（t））的
{
缓存[T] =缓存[T + 1];
继续;
}
的foreach（在tasksByTime VAR任务[T]）
{
VAR oldCEs =缓存[T + task.Length]。
变种firstOldCE = oldCEs.First（）;
变种lastOldCE = oldCEs.Last（）;
VAR newCE =新CacheEntry
{
任务= firstOldCE.Tasks + 1，
任务=的任务，
差距= firstOldCE.Gaps，
MinGap = firstOldCE.MinGap
};
//如果有，在时间T + L启动一个任务，然后，将永远
//对我们最好的选择，因为这将有比别人一个缝隙少
如果（firstOldCE.Task == NULL || firstOldCE.Task.Start == task.End）
{
newCE.NextTask = firstOldCE.Task;
}
//否则，我们想要的最大化MinGap。
其他
{
VAR CE = oldCEs.OrderBy（X =＆GT; Math.Min（x.Task.Start - newCE.Task.End，x.MinGap））最近（）。
newCE.NextTask = ce.Task;
newCE.Gaps ++;
newCE.MinGap = Math.Min（ce.MinGap，ce.Task.Start - task.End）;
}
VAR toComp =缓存[T]？缓存[T + 1];
如果（newCE.CompareTo（toComp.First（））℃，）
{
缓存[T] = toComp;
}
其他
{
VAR ceList =新的名单，其中，CacheEntry＆GT; {newCE};
//我们需要保持跟踪开始在区间[T，T + 1]的所有上下解的X的
//具有相同数量的任务和差距，但可能是一个小MinGap。这是
//因为较早的任务可能有一个更小的差距，这一任务。
INT IDX = newCE.Task.Start + 1;
而（IDX＆LT; newCE.Task.End）
{
toComp =缓存[IDX]
如果
（
newCE.Tasks == toComp.First（）任务和放大器;＆安培;
newCE.Gaps == toComp.First（）差距与放大器;＆安培;
newCE.MinGap＆GT; = toComp.First（）MinGap。
）
{
ceList.AddRange（toComp）;
。IDX + = toComp.First（）Task.End;
}
其他
IDX ++;
}
缓存[T] = ceList;
}
}
}
VAR RV =新的名单，其中，任务＆GT;（）;
VAR CURR =缓存[0]。首先（）;
而（真）
{
rv.Add（curr.Task）;
如果（curr.NextTask == NULL）破;
CURR =缓存[curr.NextTask.Start]。首先（）;
}
返回rv;
}
公共静态无效的主要（）
{
IList的＆LT;任务＆GT;任务，溶胶;
任务=新的名单，其中，任务＆GT;
{
新任务【开始= 0，长度= 2}，
新任务【开始= 3，长度= 2}，
新任务【开始= 4，长度= 2}，
新任务【开始= 5，长度= 2}，
新任务【开始= 6，长度= 2}，
新任务【开始= 9，长度= 2}，
};
溶胶= F（任务）;
的foreach（溶胶VAR任务）
Console.Out.WriteLine（任务）;
Console.Out.WriteLine（）;
任务=新的名单，其中，任务＆GT;
{
新任务【开始= 0，长度= 2}，
新任务【开始= 3，长度= 2}，
新任务【开始= 4，长度= 2}，
新任务【开始= 8，长度= 2}，
};
溶胶= F（任务）;
的foreach（溶胶VAR任务）
Console.Out.WriteLine（任务）;
Console.Out.WriteLine（）;
任务=新的名单，其中，任务＆GT;
{
新任务【开始= 0，长度= 5}，
新任务【开始= 6，长度= 5}，
新任务【开始= 7，长度= 3}，
新任务【开始= 8，长度= 9}，
新任务【开始= 19，长度= 1}，
};
溶胶= F（任务）;
的foreach（溶胶VAR任务）
Console.Out.WriteLine（任务）;
Console.Out.WriteLine（）;
Console.In.ReadLine（）;
}
I'm trying to determine the optimal solution for this tough problem. I've got a length (let's say 11). So it's a one dimensional space 0-10. Now I've got these intervals with same length (let's assume 2 in this example). Now they're randomly distributed (overlapping, or not). Let me draw an example:
Situation:
|00|01|02|03|04|05|06|07|08|09|10| <- Space (length = 11)
|-----|
|-----|
|-----|
|-----|
|-----|
|-----| <- single interval of length = 2
Now the solution needs to find the maximal number of intervals that can fit at once without overlap.
The solution is: 4 intervals
There are three results of 4 intervals:
|00|01|02|03|04|05|06|07|08|09|10|
|-----| |-----|-----| |-----| <- result 1
|-----| |-----| |-----| |-----| <- result 2
|-----| |-----|-----| |-----| <- result 3
But there are also two more constraints as well.
If there are more results (of best solution, in this case = 4), then the one with the least number of gaps.
If there are more results still the one with the highest minimal length of all its spaces. For example the one with spaces (of length) 2 & 3 has minimal length of space = 2, that is better than 1 & 4 where the minimal length of space is only 1.
So the result 2 has 4 "continual" chunks, the other two have only 3 so the refinement is:
|00|01|02|03|04|05|06|07|08|09|10|
|-----| |-----------| |-----| <- result 1
|-----| |-----------| |-----| <- result 3
Those two got same space distributions between them, so let's take first one.
The result for the input set is:
Interval count : 4
Optimal solution: |-----| |-----------| |-----|
The algorithm has to work universally for all the space length (not only 11), all interval lengths (interval length is always <= space length) and any number of intervals.
Update:
Problematic scenario:
|00|01|02|03|04|05|06|07|08|09|
|-----|
|-----|
|-----|
|-----|
|-----|
This is a simple dynamic programming problem.
Let the total length be N and the length of a task be L.
Let F(T) be maximum number of tasks that can be selected from the sub interval (T, N), then at each unit time T, there are 3 possibilities:
- There is no task that starts at T.
- There is a task that starts at T, but we do not include it in the result set.
- There is a task that starts at T, and we do include it in the result set.
Case 1 is simple, we just have F(T) = F(T + 1).
In case 2/3, notice that selecting a task that start a T means we must reject all tasks that start while this task is running, i.e. between T and T + L. So we get F(T) = max(F(T + 1), F(T + L) + 1).
Finally, F(N) = 0. So you just start from F(N) and work your way back to F(0).
EDIT: This will give you the maximum number of intervals, but not the set that fulfils your 2 constraints. Your explanation of the constraints is unclear to me, so I'm not sure how to help you there. In particular, I can't tell what constraint 1 means since all the solutions to your example set are apparently equal.
EDIT 2: Some further explanation as requested:
Consider your posted example, we have N = 11 and L = 2. There are tasks that start at T = 0, 3, 4, 5, 6, 9. Starting from F(11) = 0 and working backwards:
F(11) = 0F(10) = F(11) = 0(Since no task starts atT = 10)F(9) = max(F(10), F(11) + 1) = 1- ...
Eventually we get to F(0) = 4:
T |00|01|02|03|04|05|06|07|08|09|10|
F(T)| 4| 3| 3| 3| 3| 2| 2| 1| 1| 1| 0|
EDIT 3: Well I was curious enough about this that I wrote a solution, so may as well post it. This will give you the set that has the most tasks, with the least number of gaps, and the smallest minimum gap. The output for the examples in the question is:
(0, 2) -> (4, 6) -> (6, 8) -> (9, 11)(0, 2) -> (4, 6) -> (8, 10)
Obviously, I make no guarantees about correctness! :)
private class Task { public int Start { get; set; } public int Length { get; set; } public int End { get { return Start + Length; } }
public override string ToString()
{
return string.Format("({0:d}, {1:d})", Start, End);
}
}
private class CacheEntry : IComparable
{
public int Tasks { get; set; }
public int Gaps { get; set; }
public int MinGap { get; set; }
public Task Task { get; set; }
public Task NextTask { get; set; }
public int CompareTo(object obj)
{
var other = obj as CacheEntry;
if (Tasks != other.Tasks)
return Tasks - other.Tasks; // More tasks is better
if (Gaps != other.Gaps)
return other.Gaps = Gaps; // Less gaps is better
return MinGap - other.MinGap; // Larger minimum gap is better
}
}
private static IList<Task> F(IList<Task> tasks)
{
var end = tasks.Max(x => x.End);
var tasksByTime = tasks.ToLookup(x => x.Start);
var cache = new List<CacheEntry>[end + 1];
cache[end] = new List<CacheEntry> { new CacheEntry { Tasks = 0, Gaps = 0, MinGap = end + 1 } };
for (int t = end - 1; t >= 0; t--)
{
if (!tasksByTime.Contains(t))
{
cache[t] = cache[t + 1];
continue;
}
foreach (var task in tasksByTime[t])
{
var oldCEs = cache[t + task.Length];
var firstOldCE = oldCEs.First();
var lastOldCE = oldCEs.Last();
var newCE = new CacheEntry
{
Tasks = firstOldCE.Tasks + 1,
Task = task,
Gaps = firstOldCE.Gaps,
MinGap = firstOldCE.MinGap
};
// If there is a task that starts at time T + L, then that will always
// be the best option for us, as it will have one less Gap than the others
if (firstOldCE.Task == null || firstOldCE.Task.Start == task.End)
{
newCE.NextTask = firstOldCE.Task;
}
// Otherwise we want the one that maximises MinGap.
else
{
var ce = oldCEs.OrderBy(x => Math.Min(x.Task.Start - newCE.Task.End, x.MinGap)).Last();
newCE.NextTask = ce.Task;
newCE.Gaps++;
newCE.MinGap = Math.Min(ce.MinGap, ce.Task.Start - task.End);
}
var toComp = cache[t] ?? cache[t + 1];
if (newCE.CompareTo(toComp.First()) < 0)
{
cache[t] = toComp;
}
else
{
var ceList = new List<CacheEntry> { newCE };
// We need to keep track of all subsolutions X that start on the interval [T, T+L] that
// have an equal number of tasks and gaps, but a possibly a smaller MinGap. This is
// because an earlier task may have an even smaller gap to this task.
int idx = newCE.Task.Start + 1;
while (idx < newCE.Task.End)
{
toComp = cache[idx];
if
(
newCE.Tasks == toComp.First().Tasks &&
newCE.Gaps == toComp.First().Gaps &&
newCE.MinGap >= toComp.First().MinGap
)
{
ceList.AddRange(toComp);
idx += toComp.First().Task.End;
}
else
idx++;
}
cache[t] = ceList;
}
}
}
var rv = new List<Task>();
var curr = cache[0].First();
while (true)
{
rv.Add(curr.Task);
if (curr.NextTask == null) break;
curr = cache[curr.NextTask.Start].First();
}
return rv;
}
public static void Main()
{
IList<Task> tasks, sol;
tasks = new List<Task>
{
new Task { Start = 0, Length = 2 },
new Task { Start = 3, Length = 2 },
new Task { Start = 4, Length = 2 },
new Task { Start = 5, Length = 2 },
new Task { Start = 6, Length = 2 },
new Task { Start = 9, Length = 2 },
};
sol = F(tasks);
foreach (var task in sol)
Console.Out.WriteLine(task);
Console.Out.WriteLine();
tasks = new List<Task>
{
new Task { Start = 0, Length = 2 },
new Task { Start = 3, Length = 2 },
new Task { Start = 4, Length = 2 },
new Task { Start = 8, Length = 2 },
};
sol = F(tasks);
foreach (var task in sol)
Console.Out.WriteLine(task);
Console.Out.WriteLine();
tasks = new List<Task>
{
new Task { Start = 0, Length = 5 },
new Task { Start = 6, Length = 5 },
new Task { Start = 7, Length = 3 },
new Task { Start = 8, Length = 9 },
new Task { Start = 19, Length = 1 },
};
sol = F(tasks);
foreach (var task in sol)
Console.Out.WriteLine(task);
Console.Out.WriteLine();
Console.In.ReadLine();
}
这篇关于如何确定给定范围内优化间隔计数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
