用于最佳地选择执行任务的动作的算法
Jul*_*les 7 algorithm math optimization computer-science
有两种数据类型:任务和操作.一个动作需要花费一定的时间来完成,这个动作包含一组任务.任务有一系列操作,我们的工作是选择其中一个.所以:
class Task { Set<Action> choices; }
class Action { float time; Set<Task> dependencies; }
例如,主要任务可能是"获得房子".这项任务可能采取的行动:"买房子"或"盖房子"."建造一栋房子"的行动需要花费10个小时,并且具有依赖性"获取砖块"(可能花费6个小时)和"获得水泥"(花费9个小时)等等.
的总时间是来执行所需的操作的所有时间(在此情况下10 + 6 + 9小时)的总和.我们希望选择总时间最短的行动.
请注意,依赖关系可以是菱形的.例如,"获取砖块"可能需要"获取汽车"(运输砖块)和"获取水泥"也需要汽车.即使你做的"获取砖头"和"获取水泥"你只需要计算才能得到一辆汽车的时间一次.
另请注意,依赖项可以是循环的.例如"Money" - >"Job" - >"Car" - >"Money".这对我们来说没问题,我们只选择所有"钱","工作"和"汽车".总时间只是这三件事的时间总和.
数学描述:
让我们actions选择行动.
valid(task) = ?action ? task.choices. (action ? actions ? ?tasks ? action.dependencies. valid(task))
time = sum {action.time | action ? actions}
minimize time subject to valid(primaryTask)
我对最佳解决方案感兴趣,但也对近似解决方案感兴趣.也许某种动态编程可以帮到那里？如果问题是树形结构,那么动态编程可以在多项式时间内给出最优解,但是钻石结构似乎使问题更加困难.如果你有一个算法,但是如果有循环则不起作用,请发布它!我可能仍然可以从中学到很多东西.
框表示任务,圆圈表示动作(执行动作的时间在圆圈中).如果该任务是该操作的依赖项,则该操作对任务具有一行.以下是关于图片的问题描述:如果选择了矩形(=任务),则必须选择其中一个圆(=动作).如果选择了圆,则必须选择所有连接的矩形.目标是最小化所选圈子中的数字总和.
在这种情况下,最佳解决方案是在顶部任务中选择时间2的操作,在底部任务中选择时间1的操作.总时间为2 + 1 + 1 = 4.在这种情况下,有2个最佳解决方案.第二种解决方案是在顶部任务中选择时间为3的操作,在右下角任务中选择时间为1的操作.总时间再次为3 + 1 = 4.如果我们在顶部任务中选择时间3的动作,则不必执行左下角任务,因为动作与时间3和左下角任务之间没有线.
我为糟糕的绘画道歉;)还有两个例子(每个例子的最佳解决方案用蓝色表示,主要任务用灰色表示):
