代码之家  ›  专栏  ›  技术社区  ›  Keith Pham

最大化给定预算的子图“价值”

  •  0
  • Keith Pham  · 技术社区  · 7 年前

    我想解决的场景是最大化问题,其中连接的无向图中的每个顶点都有一个 价值 费用

    给定起始顶点和 成本预算 价值 (包括起始顶点)?

    1 回复  |  直到 7 年前
        1
  •  0
  •   Peter de Rivaz    7 年前

    Steiner tree problem in graphs 通过将每个端子的值设置为1,每个顶点的成本为0,每个边的成本为1。当且仅当成本预算为k的算法能够从所有终端捕获值时,才存在权重为k的斯坦纳树。

    这可能有助于研究斯坦纳树的文献,以获得近似解的一些想法。