找到总成本最少的子图数<= given threshold

Question

我有以下问题：

给定一个有 N 个节点的（有向无环）图，每个节点都有一个已知的正“成本”，建议一种算法将图划分为最少数量的连续子图，这样每个子图的总成本为 no超过给定参数 subgraph_max_cost.

这里是连续子图的定义：

a->b->c->d->e a->b->c 和 d->e 是两个连续的子图

但是 a->d 和 b->c->e 不是。

以上是NP难问题吗？我想一个天真的方法是找到 DAG 中的所有子图并保留总权重为 <= the given threshold. Is there a better way to approach this?

的子图

我们希望算法能够很好地扩展。

Answer 1

贪心算法：

• LOOP1 直到所有节点都被选中
• 选择最便宜的未选中节点
• 循环2
  • 选择连接最便宜但未选中的节点
  • 如果超过限制
    • 打破循环 2
  • 添加最便宜的节点

在你最快的代码中实现它。检查性能是否满足您的要求。 （对于任何多达几千个节点的图形，这应该会非常快。您应该将性能要求添加到您的问题中：最大图形大小，最大运行时间）