트리의 서브 그래프 인 주어진 수의 모서리를 가진 최대 트리 서브 그래프 찾기

Question

문제는 다음과 같습니다. 트리와 사용 가능한 모서리 수를 그래프로 표시합니다. v1에서 시작하여 이미 방문한 vertifications에서 벗어나는 가장자리를 선택합니다.

예이 예에서

최적의 방법은 : 우선

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

I 이것은부터 길이 k의 최대 경로를 찾는 문제 일 것이다 비록 하찮은 일이지만, 요점은 언제나 다른 방식으로 갈 수 있다는 것입니다. 그래서 접근 방식은 효과가 없습니다.

내가 뭘 지금까지의 생각 :

1. 잘라 k에 나무와 무력 모든 possibilites.

2. 모든 가장자리의 가장자리로가는 비용을 계산하십시오. 비용은 우리가 가고자하는 가장자리가 그 가장자리로 가기 위해 추가해야하는 가장자리의 양으로 나눠지기 전에 모든 가장자리의 합계를 포함합니다. 거기에서 최대를 선택하고 모든 가장자리에 대해 비용을 업데이트 한 다음 k에 도달 할 때까지 다시 수행하십시오.

두 번째 방법은 좋지만 나 배낭 문제를 상기시킵니다.

제 질문은 이렇습니다. 더 좋은 방법이 있습니까? 이 문제는 NP입니까?

EDIT : 트리밍 답변 이의 예 :

Answer 1

이 코드는 특정 노드를 루트 트리의 최대 가중치를 계산하는 하위 문제에 기초 메모이 제이션 방법을 도시한다.

복잡도는 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)