Given a binary tree with transition weights.
It is necessary to get the maximum value for N transitions starting from the zero node. In this case, the path must be continuous, with free returns to the parent node.

My current algorithm is:

  1. Find the last available node (in which the number of moves is 0, or there are no children).
  2. Write to the array the current value and the number of available moves (including descendants).
  3. Go to the parent node, copy both arrays (if 2 children), or 1 array (1 child).
  4. Repeat step 2-3 to return to the root node.
  5. Based on the array in the root node (which contains all possible combinations of values ​​+ moves) find the maximum value.

Main questions:

  1. Is there a better algorithm?
  2. Is it possible to optimize this algorithm? works too long and requires too much memory?
  • specify, find a path from the center down (N + 1 vertex) with the maximum sum on the edges? - pavel
  • Yes, but with free return to the parent node (which is the main problem of the task) and the path should be continuous. - Ihor Kyrychok
  • calculate the dynamics (for example, F [u] [l] is the optimal sum of l from the vertex u). And then use and maintain some maximum on the way down for each parameter. This can most likely be done with N * S (S is the size of the tree). - pavel
  • @pavel If I correctly understood the algorithm as follows: for a tree with a height of N, find the maximum for each level. Write these values ​​into an array. Then in an array in a loop to N / 2 (the first with the last, etc.) add these values ​​and select of them maximal. Everything correctly understood? - Ihor Kyrychok
  • No, I wrote the answer. - pavel

2 answers 2

The solution is for N*S memory, N*S*S or N*S*log S time. S - размер дерева .

Dynamics F[vert][size] is the optimal answer if we take size elements in the vertex subtree.

For any element F[u][0] = 0 For a sheet that's all.

For vertex pseudocode. (r - the right child, l - left).

 for (int i=0;i<min(N,l.size());i++) F[u][i+1] = F[l][i] + D[u][l]; for (int i=0;i<min(N,r.size());i++) F[u][i+1] = max(F[u][i+1],F[r][i] + D[u][l]); for (int i=0;i<min(N-1,l.size());i++) for (int j=0; j < min(Ni-1,r.size()); j++) F[u][i+j+2] = max(F[u][i+j+2], D[u][l] + D[u][r] + F[l][i] + F[r][j]);

Something like this. We either take only 1 subtree items. Or we take with 2, then we sort out how much we take on the left and how many on the right.

The answer is the value in F[root][N] . For acceleration instead of a double cycle use the Быстрое преобразование Фурье (FFT) .

  • Please correct if I misunderstand something: In each node, we store an array of a pair of values ​​consisting of the optimal (maximum) response value and the corresponding transition value. The number of elements in the array is equal to the number of children + 1. For each node with M transitions we find the optimal value for each M-1 transition and, if the value of M-1 transition is greater than the current one recorded for M-1, we write to the array at the corresponding position. As a result, it comes out an optimized algorithm written by me at the beginning, since Only optimal values ​​for each node are stored, but not all possible ones? - Ihor Kyrychok
  • Something like this, only size carefully. There the size of the entire subtree (and not the number of children). The value of the transition I keep separately and it is so by condition. If you need to restore the answer, it is better to use the reverse step and not to keep the transition. Actually, the algorithm may look like optimized but this is a comparison of non-limiting brute force and dynamics. - pavel
  • It is possible a question about specific implementation on With? The pastebin.com/nK8UpMeF code itself (left only the node structure and the function it deleted is unnecessary). Now, the maximum straight path (that is, the transition from parent to child) is correct, but there is no return to the parent node. Presumably due to the lack of a double cycle because I do not know how to implement it on these nodes. I tried to do it recursively, but it did not work out. In the node constructor, the left node always adds the first node (ie, left! = NULL && right == NULL means a node with 1 descendant and ancestor). - Ihor Kyrychok
  • Well, actually yes. And what exactly did not work out? The code as a whole is working right in the answer. In your designation instead of F[u][X] ---> curr->res[X] или curr->letf->res[X] and I don’t understand where your ребра weight is stored ... - pavel
  • It's easier to show in the picture - imgur.com/OGrjHUg . Now I get the blue path instead of the green one . The blue path is wrong because not the maximum and does not use all transitions (only 7 instead of 10). As a result, I get a direct path, instead of a path with turns (I don’t know how to explain it better). The edge weight is stored in value. Res is an array of optimal values ​​for N + 1 values ​​(turns is the number of transitions) .. - Ihor Kyrychok

Actually the answer may be useful to someone: In the tree, I always add the left node first, then the right node (see if (left! = NULL & right == NULL).

 void getMax(Node *curr,int turns) { int i,j; if(curr->left!=NULL && turns!=0) getMax(curr->left,turns-1); if(curr->right!=NULL && turns!=0) getMax(curr->right,turns-1); curr->res=new int[turns+1](); curr->res[0]=0; if(curr->left==NULL && curr->right==NULL || turns==0) { for(i=1;i<turns+1;i++) curr->res[i]=0; return; } else { if(curr->left!=NULL && curr->right==NULL) { Node*next=curr->left; for(i=0;i<turns;i++) { curr->res[i+1]=next->res[i]+next->value; } } else { Node *left=curr->left; Node *right=curr->right; for(i=0;i<turns+1;i++)//left { for(j=0;j<turns+1-i;j++)//right { if(i==0 && j==0) { curr->res[0]=0; } if(i==0 && j>=1) { curr->res[j]=max(curr->res[j],right->value+right->res[j-1]); } if(i>=1 && j==0) { curr->res[i]=max(curr->res[i],left->value+left->res[i-1]); } if(i>=1 && j>=1) { curr->res[i+j]=max(curr->res[i+j],left->value+right->value+left->res[i-1]+right->res[j-1]); } } } } } }

and the class itself

 class Node { public: Node *parent; Node *left; Node *right; int id; int value; int *res;};