找到一个贪婪的算法来平衡成功率和成本

Question

​

​

嗨!我正在试着解决这样的问题。一个任务包含多个备用节点。它们将并行执行。每个节点都有一个成功率和成本。在多个设备上执行此任务可以提高成功率(至少有一个设备获得结果的成功率将增加1-(1-S)^N)。

该任务的目标是从这些节点中的任何一个获得结果。一旦一个节点成功执行，其他节点将停止。问题是，如何定义一个算法来满足总体成功率阈值，即至少有一个节点成功并具有最低成本。

我认为这应该是一个有3个变量的贪婪算法:设备数量，成功率和成本。我不知道如何比较成功率和成本的比率。有谁能帮帮我吗？我们可以假设总体成功率的阈值是90%。

Answer 1

您希望使用类似于分数背包的算法，但有一点不同：

首先，将任何成功率高于边界的节点的成功率临时设置为边界的值。例如，如果边界为90%，节点C为(100%，$5)，则节点C将变为(90%成功率，$5)。

这是因为您正在寻找满足边界的最小成本。例如，如果您的边界是50%，您仍然希望选择具有(50%成功率，$5)的节点，而不是具有(100%成功率，$6)的节点。因此，100%成功率节点也可能是50%的成功率

然后，按成功率/成本升序对节点进行排序。

算法的每一步都是将成功率/成本最低的节点添加到节点的解决方案列表中，直到节点的总成功率达到边界。但是，添加的步骤是，如果添加的节点创建的总成功率大于边界，则必须从最大的成功率/成本到最低的节点查看节点的解决方案列表，并查看删除该节点是否仍能保持达到百分比边界。您将继续删除可能的节点，直到不能删除任何节点，并且仍然满足边界。

例如:如果您的列表包含按顺序添加的节点：

(20%，$2)，(30%，$1)，(40%，.5$)，边界是70%，

目前总的百分比是90%，超过了70%。由于节点(40%，.5$)是刚刚添加的，您查看节点(30%，$1)后才发现它不能被删除，因为这样边界将是小于边界的60%。然后查看下一个节点(20%，$2)，它可以删除，因为剩余的总百分比将是70%，满足所需的边界。你会一直往下走，但在这个例子中，新修改的(30%，$1)，(40%，.5$)将是有效的解决方案。