给定预算最大化子图 "value"

Question

我想解决的手头场景是一个最大化问题，其中连接的无向图中的每个顶点都有一个 值。但是，每条边和顶点也有一个 cost.

给定起始顶点和成本预算，是否有推荐的算法或方法来找到最大化顶点值[=19=的连通子图] （包括起始顶点）?

Answer 1

这是 NP-hard，因为您可以为此使用一种算法来解决 Steiner tree problem in graphs，方法是将每个终端的值设置为 1，每个顶点的成本为 0，以及每条边都为 1。当且仅当您的成本预算为 k 的算法能够从所有终端捕获价值时，才会有一个权重为 k 的斯坦纳树。

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