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 に達するまでこれを繰り返します。

2 番目のアプローチは良さそうに見えますが、ナップザックの問題を少し思い出します。

私の質問は次のとおりです。これに対するより良いアプローチはありますか? この問題は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 に答える