最佳选择 Action 来执行任务的算法

Question

有两种数据类型:任务和操作。一个 Action 需要一定的时间才能完成，而这个 Action 由一组任务组成。一个任务有一组 Action ，我们的工作是选择其中一个。所以:

class Task { Set<Action> choices; }
class Action { float time; Set<Task> dependencies; }

例如，主要任务可以是“买房子”。此任务可能采取的行动:“买房子”或“建房子”。 “盖房子”这个 Action 耗时 10 小时，并具有“获取砖 block ”(可能耗时 6 小时)和“获取水泥”(耗时 9 小时)等依赖项。

总时间 是执行所需操作的所有时间的总和(在本例中为 10+6+9 小时)。我们希望选择总时间最短的操作。

请注意，依赖项可以是菱形的。例如，“Get bricks”可能需要“Get a car”(运输砖 block )，“Get cement”也需要汽车。即使你做“拿砖头”和“拿水泥”，你也只需要计算得到一辆车所花费的时间一次。

另请注意，依赖关系可以是循环的。例如“钱”->“工作”->“汽车”->“钱”。这对我们来说没有问题，我们只需选择所有“Money”、“Job”和“Car”。总时间就是这 3 件事的时间总和。

数学描述:

让 actions 成为选择的 Action 。

valid(task) = ∃action ∈ task.choices. (action ∈ actions ∧ ∀tasks ∈ action.dependencies. valid(task))
time = sum {action.time | action ∈ actions}
minimize time subject to valid(primaryTask)

我对最优解很感兴趣，但对近似解也很感兴趣。也许某种动态规划可以帮助那里？如果问题是树结构的，那么动态规划可以在多项式时间内给出最优解，但菱形结构似乎使问题变得更加困难。如果你有一个算法，但如果有循环它就不起作用，请发布它!我可能仍然可以从中学到很多东西。

方框代表任务，圆圈代表 Action (执行 Action 的时间在圆圈内)。如果该任务是该操作的依赖项，则该操作与任务有一条线。这里再次用图片来描述问题:如果选择了一个矩形(=task)，那么必须选择里面的一个圆圈(=actions)。如果选择了一个圆，则必须选择所有 相连的矩形。目标是最小化所选圆圈中的数字总和。

在这种情况下，最佳解决方案是在顶部任务中选择时间为 2 的 Action ，在底部任务中选择时间为 1 的 Action 。总时间为2+1+1=4。在这种情况下，有 2 个最佳解决方案。第二种解决方案是在顶部任务中选择时间为 3 的 Action ，在右下方任务中选择时间为 1 的 Action 。总时间又是3+1=4。如果我们在顶部任务中选择时间为 3 的 Action ，则不必执行左下任务，因为时间为 3 的 Action 与左下任务之间没有界限。

对于糟糕的绘图，我深表歉意；)还有两个示例(每个示例的最佳解决方案已用蓝色表示，主要任务已用灰色表示):

Answer 1

您可以将其建模为图表并使用 shortest path algorithm找到解决方案。每个任务都是一个节点，而操作则是图中的边。

事实上，将节点表示为状态和边可能会更容易，因为在状态之间转换所需的 Action 表示为边。

如果您将任务视为简单的操作集合，并将节点建模为状态，将操作建模为这些操作之间的转换。与其将“获得房子”视为首要任务，不如将“开始”和“拥有房子”视为 2 个节点，将“获得房子”视为它们之间的过渡。 “找房子”转换 Action 可以分解为表示中间状态和 Action (即节点和边)的图。您应该能够尽可能地分解问题，并根据生成的图形计算出最短路径。