2

所以一个问题如下：给你一个图，它是一棵树和你可以使用的边数。从 v1 开始，您选择超出您已经访问过的任何顶点的边。

一个例子：图形

在此示例中，最佳方法是：

for k==1 AC -> 5
for k==2 AB BH -> 11
for k==3 AC AB BH -> 16

起初我虽然找到从 A 开始的长度为 k 的最大路径是一个问题，这将是微不足道的，但关键是你总是可以选择不同的方式，所以这种方法不起作用。

到目前为止我的想法：

  1. 在 k 处砍树，并暴力破解所有可能。

  2. 计算所有边到边的成本。成本将包括我们试图去的边缘之前的所有边缘的总和除以为了到达该边缘而需要添加的边缘数量。从那里为所有边选择最大值，更新成本，然后再做一次，直到达到 k。

第二种方法看起来不错，但它让我想起了背包问题。

所以我的问题是：有没有更好的方法呢？这个问题是NP吗？

编辑：修剪答案的反例：

在此处输入图像描述

4

1 回答 1

2

此代码说明了一种基于从以某个节点为根的树计算最大权重的子问题的记忆方法。

我认为复杂性将是 O(kE)，其中 E 是图中的边数（对于树，E=n-1）。

edges={}
edges['A']=('B',1),('C',5)
edges['B']=('G',3),('H',10)
edges['C']=('D',2),('E',1),('F',3)

cache={}
def max_weight_subgraph(node,k,used=0):
    """Compute the max weight from a subgraph rooted at node.
    Can use up to k edges.
    Not allowed to use the first used connections from the node."""
    if k==0:
        return 0
    key = node,k,used
    if key in cache:
        return cache[key]
    if node not in edges:
        return 0
    E=edges[node]
    best=0
    if used<len(E):
        child,weight = E[used]
        # Choose the amount r of edges to get from the subgraph at child
        for r in xrange(k):
            # We have k-1-r edges remaining to be used by the rest of the children
            best=max(best,weight+
                     max_weight_subgraph(node,k-1-r,used+1)+
                     max_weight_subgraph(child,r,0))
        # Also consider not using this child at all
        best=max(best,max_weight_subgraph(node,k,used+1))
    cache[key]=best
    return best

for k in range(1,4):
    print k,max_weight_subgraph('A',k)
于 2013-05-24T15:06:23.873 回答