algorithm - Find a maximum tree subgraph with given number of edges that is a subgraph of a tree -
so problem follows: given graph tree , number of edges can use. starting @ v1, choose edges go out of of verticies have visited.
an example:
in example optimal approach is:
for k==1 ac -> 5 k==2 ab bh -> 11 k==3 ac ab bh -> 16 at first though problem find maximum path of length k starting a, trivial, point can choose go different way, approach did not work.
what though of far:
cut tree @ k, , brute force possibilites.
calculate cost of going edge edges. cost include sum of edges before edge trying go divided amount of edges need add in order edge. there pick maximum, edges, update cost, , again until have reached k.
the second approach seems good, reminds me bit of knapsack problem.
so question is: there better approach this? problem np?
edit: counter example trimming answer:
this code illustrates memoisation approach based on subproblem of computing max weight tree rooted @ node.
i think complexity o(ke) e number of edges in graph (e=n-1 tree).
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 max weight subgraph rooted @ node. can use k edges. not allowed use first used connections 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 amount r of edges subgraph @ child r in xrange(k): # have k-1-r edges remaining used rest of children best=max(best,weight+ max_weight_subgraph(node,k-1-r,used+1)+ max_weight_subgraph(child,r,0)) # consider not using child @ best=max(best,max_weight_subgraph(node,k,used+1)) cache[key]=best return best k in range(1,4): print k,max_weight_subgraph('a',k) 
Comments
Post a Comment