我需要为每个时间表分配频道。可以存在与分配给客户的信道数量一样多的并发事件。也就是说,如果客户被分配了3个信道,那么他可以有3个并发事件。如果将通道分配给事件,则不能将相同的通道分配给属于相同时间的另一个事件,但如果时间不同,则可以将相同的通道分配给另一个事件。
通道表
ID Name
1 Name1
2 Name2
3 Name3
事件表
ID EventName StartTime EndTime ChannelID
1 Event1 11:30AM 12PM 1
2 Event2 11:30AM 11:40AM 2
3 Event3 11:40AM 12PM 2
4 Event4 12PM 12:30PM 1 0r 2
5 Event5 11:30AM 12:30PM 3
以上是预期的输出。
我尝试了嵌套的foreachloop,一个用于channel,另一个用于evets,但无法实现,而且复杂性非常高。如何实现这一逻辑?
伪代码:
for each channel
{
foreach existing events
{
if(sametime && same channel)
{
go for next channel
}
break;
}
assign current channel to new event
}
当我尝试创建第三个事件时,这会失败。
发布于 2011-04-05 18:20:29
你可以通过循环事件来为事件分配通道,请查看下面的伪代码:
foreach events
{
foreach channels
{
if currentChannel is assigned
{
foreach assignedEvents
{
if assignedTime = currentEventTime
go to next Channel (continue)
}
currentEvent.Channel = currentChannel
break;
}
else
{
currentEvent.Channel = currentChannel
break;
}
}
}
发布于 2011-04-05 17:59:34
你必须生成所有的可能性,并选择最好的。
这是一个NP完全问题,所以没有办法既快速又正确--要么你通过一些启发式快速完成它,但然后你不知道它是否真的做得最好,或者你做得很慢,我的意思是慢,但你确定结果是最优的。
取决于数据的大小。
EDIT:示例演示,仅将事件分配给第一个空闲频道并不总是有效的。
我们有3个频道: Ch1,Ch2,Ch3
我们要安排6个事件:
E1-2 - starts at 1:00 ends at 2:59
E1-3 - starts at 1:00 ends at 3:59
E1-3 - starts at 1:00 ends at 3:59
E4 - starts at 4:00 ends at 4:59
E4 - starts at 4:00 ends at 4:59
E3-4 - starts at 3:00 ends at 4:59
如果你只是分配给第一个空闲的地方,你最终会得到:
Ch1: E1-2, E4
Ch2: E1-3, E4
Ch3: E1-3
and no place for E3-4
如果你以不同的顺序分配它们,你会得到
Ch1: E1-2, E3-4
Ch2: E1-3, E4
Ch3: E1-3, E4
所有的事件都会符合。
所以你必须以某种方式回溯。
发布于 2011-04-05 18:13:47
在我看来,这有点类似于车辆路径问题。通道与车辆相同,事件就像有向无环图中的节点,当且仅当第一个事件比第二个事件开始更早结束时,才会有从一个事件到另一个事件的边。
您应该能够找到解决此问题的公开可用的算法。
https://stackoverflow.com/questions/5550066
复制相似问题