Нахождение самого тяжелого пути с ограниченной длиной во взвешенном двоичном дереве

ОБНОВЛЕНИЕ

Я разработал алгоритм, который, как мне кажется, работает за O (n * k) времени работы. Ниже приведен псевдокод:

routine heaviestKPath( T, k )

    // create 2D matrix with n rows and k columns with each element = -∞
    // we make it size k+1 because the 0th column must be all 0s for a later 
    // function to work properly and simplicity in our algorithm
    matrix = new array[ T.getVertexCount() ][ k + 1 ] (-∞);

    // set all elements in the first column of this matrix = 0
    matrix[ n ][ 0 ] = 0;

    // fill our matrix by traversing the tree
    traverseToFillMatrix( T.root, k );

    // consider a path that would arc over a node
    globalMaxWeight = -∞;
    findArcs( T.root, k );

    return globalMaxWeight
end routine


// node = the current node; k = the path length; node.lc = node’s left child; 
// node.rc = node’s right child; node.idx = node’s index (row) in the matrix; 
// node.lc.wt/node.rc.wt = weight of the edge to left/right child;
routine traverseToFillMatrix( node, k )

   if (node == null) return;

   traverseToFillMatrix(node.lc, k ); // recurse left
   traverseToFillMatrix(node.rc, k ); // recurse right

   // in the case that a left/right child doesn’t exist, or both,
   // let’s assume the code is smart enough to handle these cases
   matrix[ node.idx ][ 1 ] = max( node.lc.wt, node.rc.wt );


   for i = 2 to k {
       // max returns the heavier of the 2 paths
       matrix[node.idx][i] = max( matrix[node.lc.idx][i-1] + node.lc.wt, 
                                  matrix[node.rc.idx][i-1] + node.rc.wt);
   }

end routine



// node = the current node, k = the path length
routine findArcs( node, k ) 

    if (node == null) return;

    nodeMax = matrix[node.idx][k];
    longPath = path[node.idx][k];

    i = 1;
    j = k-1;
    while ( i+j == k AND i < k ) {

        left = node.lc.wt + matrix[node.lc.idx][i-1];
        right = node.rc.wt + matrix[node.rc.idx][j-1];

        if ( left + right > nodeMax ) {
            nodeMax = left + right;
        }
        i++; j--;
    }

    // if this node’s max weight is larger than the global max weight, update
    if ( globalMaxWeight < nodeMax ) {
        globalMaxWeight = nodeMax;
    }

    findArcs( node.lc, k ); // recurse left
    findArcs( node.rc, k ); // recurse right

end routine

Дайте мне знать, что вы думаете. Обратная связь приветствуется.

---

Я думаю, что придумал два наивных алгоритма, которые находят самый тяжелый путь с ограниченной длиной во взвешенном двоичном дереве. Во-первых, описание алгоритма выглядит следующим образом: для двоичного дерева с n вершинами с взвешенными ребрами и некоторого значения k найдите самый тяжелый путь длиной k.

Для обоих алгоритмов мне понадобится ссылка на все вершины поэтому я просто сделаю простой обход Дерева, чтобы иметь ссылку на все вершины, причем каждая вершина имеет ссылку на ее левый, правый и родительский узлы в дереве.

Алгоритм 1

ОБНОВЛЕНИЕ

Я разработал алгоритм, который, как мне кажется, работает за O (n * k) времени. Ниже приведен псевдокод:

routine heaviestKPath( T, k )

    // create 2D matrix with n rows and k columns with each element = -∞
    // we make it size k+1 because the 0th column must be all 0s for a later 
    // function to work properly and simplicity in our algorithm
    matrix = new array[ T.getVertexCount() ][ k + 1 ] (-∞);

    // set all elements in the first column of this matrix = 0
    matrix[ n ][ 0 ] = 0;

    // fill our matrix by traversing the tree
    traverseToFillMatrix( T.root, k );

    // consider a path that would arc over a node
    globalMaxWeight = -∞;
    findArcs( T.root, k );

    return globalMaxWeight
end routine


// node = the current node; k = the path length; node.lc = node’s left child; 
// node.rc = node’s right child; node.idx = node’s index (row) in the matrix; 
// node.lc.wt/node.rc.wt = weight of the edge to left/right child;
routine traverseToFillMatrix( node, k )

   if (node == null) return;

   traverseToFillMatrix(node.lc, k ); // recurse left
   traverseToFillMatrix(node.rc, k ); // recurse right

   // in the case that a left/right child doesn’t exist, or both,
   // let’s assume the code is smart enough to handle these cases
   matrix[ node.idx ][ 1 ] = max( node.lc.wt, node.rc.wt );


   for i = 2 to k {
       // max returns the heavier of the 2 paths
       matrix[node.idx][i] = max( matrix[node.lc.idx][i-1] + node.lc.wt, 
                                  matrix[node.rc.idx][i-1] + node.rc.wt);
   }

end routine



// node = the current node, k = the path length
routine findArcs( node, k ) 

    if (node == null) return;

    nodeMax = matrix[node.idx][k];
    longPath = path[node.idx][k];

    i = 1;
    j = k-1;
    while ( i+j == k AND i < k ) {

        left = node.lc.wt + matrix[node.lc.idx][i-1];
        right = node.rc.wt + matrix[node.rc.idx][j-1];

        if ( left + right > nodeMax ) {
            nodeMax = left + right;
        }
        i++; j--;
    }

    // if this node’s max weight is larger than the global max weight, update
    if ( globalMaxWeight < nodeMax ) {
        globalMaxWeight = nodeMax;
    }

    findArcs( node.lc, k ); // recurse left
    findArcs( node.rc, k ); // recurse right

end routine

Дайте мне знать, что вы думаете. Обратная связь приветствуется.

Я думаю, что придумал два наивных алгоритма, которые находят самый тяжелый путь с ограниченной длиной во взвешенном двоичном дереве. Во-первых, описание алгоритма выглядит следующим образом: для двоичного дерева с n вершинами с взвешенными ребрами и некоторого значения k найдите самый тяжелый путь длиной k.

Для обоих алгоритмов мне понадобится ссылка на все вершины поэтому я просто сделаю простой обход Дерева, чтобы иметь ссылку на все вершины, причем каждая вершина имеет ссылку на ее левый, правый и родительский узлы в дереве.

Алгоритм 1

ОБНОВЛЕНИЕ

Я разработал алгоритм, который, как мне кажется, работает за O (n * k) времени. Ниже приведен псевдокод:

routine heaviestKPath( T, k )

    // create 2D matrix with n rows and k columns with each element = -∞
    // we make it size k+1 because the 0th column must be all 0s for a later 
    // function to work properly and simplicity in our algorithm
    matrix = new array[ T.getVertexCount() ][ k + 1 ] (-∞);

    // set all elements in the first column of this matrix = 0
    matrix[ n ][ 0 ] = 0;

    // fill our matrix by traversing the tree
    traverseToFillMatrix( T.root, k );

    // consider a path that would arc over a node
    globalMaxWeight = -∞;
    findArcs( T.root, k );

    return globalMaxWeight
end routine


// node = the current node; k = the path length; node.lc = node’s left child; 
// node.rc = node’s right child; node.idx = node’s index (row) in the matrix; 
// node.lc.wt/node.rc.wt = weight of the edge to left/right child;
routine traverseToFillMatrix( node, k )

   if (node == null) return;

   traverseToFillMatrix(node.lc, k ); // recurse left
   traverseToFillMatrix(node.rc, k ); // recurse right

   // in the case that a left/right child doesn’t exist, or both,
   // let’s assume the code is smart enough to handle these cases
   matrix[ node.idx ][ 1 ] = max( node.lc.wt, node.rc.wt );


   for i = 2 to k {
       // max returns the heavier of the 2 paths
       matrix[node.idx][i] = max( matrix[node.lc.idx][i-1] + node.lc.wt, 
                                  matrix[node.rc.idx][i-1] + node.rc.wt);
   }

end routine



// node = the current node, k = the path length
routine findArcs( node, k ) 

    if (node == null) return;

    nodeMax = matrix[node.idx][k];
    longPath = path[node.idx][k];

    i = 1;
    j = k-1;
    while ( i+j == k AND i < k ) {

        left = node.lc.wt + matrix[node.lc.idx][i-1];
        right = node.rc.wt + matrix[node.rc.idx][j-1];

        if ( left + right > nodeMax ) {
            nodeMax = left + right;
        }
        i++; j--;
    }

    // if this node’s max weight is larger than the global max weight, update
    if ( globalMaxWeight < nodeMax ) {
        globalMaxWeight = nodeMax;
    }

    findArcs( node.lc, k ); // recurse left
    findArcs( node.rc, k ); // recurse right

end routine

Дайте мне знать, что вы думаете. Обратная связь приветствуется.

Я думаю, что придумал два наивных алгоритма, которые находят самый тяжелый путь с ограниченной длиной во взвешенном двоичном дереве. Во-первых, описание алгоритма выглядит следующим образом: для двоичного дерева с n вершинами с взвешенными ребрами и некоторого значения k найдите самый тяжелый путь длиной k.

Для обоих алгоритмов мне понадобится ссылка на все вершины поэтому я просто сделаю простой обход Дерева, чтобы иметь ссылку на все вершины, причем каждая вершина имеет ссылку на ее левый, правый и родительский узлы в дереве.

Алгоритм 1

routine heaviestKPath( T, k )

    // create 2D matrix with n rows and k columns with each element = -∞
    // we make it size k+1 because the 0th column must be all 0s for a later 
    // function to work properly and simplicity in our algorithm
    matrix = new array[ T.getVertexCount() ][ k + 1 ] (-∞);

    // set all elements in the first column of this matrix = 0
    matrix[ n ][ 0 ] = 0;

    // fill our matrix by traversing the tree
    traverseToFillMatrix( T.root, k );

    // consider a path that would arc over a node
    globalMaxWeight = -∞;
    findArcs( T.root, k );

    return globalMaxWeight
end routine


// node = the current node; k = the path length; node.lc = node’s left child; 
// node.rc = node’s right child; node.idx = node’s index (row) in the matrix; 
// node.lc.wt/node.rc.wt = weight of the edge to left/right child;
routine traverseToFillMatrix( node, k )

   if (node == null) return;

   traverseToFillMatrix(node.lc, k ); // recurse left
   traverseToFillMatrix(node.rc, k ); // recurse right

   // in the case that a left/right child doesn’t exist, or both,
   // let’s assume the code is smart enough to handle these cases
   matrix[ node.idx ][ 1 ] = max( node.lc.wt, node.rc.wt );


   for i = 2 to k {
       // max returns the heavier of the 2 paths
       matrix[node.idx][i] = max( matrix[node.lc.idx][i-1] + node.lc.wt, 
                                  matrix[node.rc.idx][i-1] + node.rc.wt);
   }

end routine



// node = the current node, k = the path length
routine findArcs( node, k ) 

    if (node == null) return;

    nodeMax = matrix[node.idx][k];
    longPath = path[node.idx][k];

    i = 1;
    j = k-1;
    while ( i+j == k AND i < k ) {

        left = node.lc.wt + matrix[node.lc.idx][i-1];
        right = node.rc.wt + matrix[node.rc.idx][j-1];

        if ( left + right > nodeMax ) {
            nodeMax = left + right;
        }
        i++; j--;
    }

    // if this node’s max weight is larger than the global max weight, update
    if ( globalMaxWeight < nodeMax ) {
        globalMaxWeight = nodeMax;
    }

    findArcs( node.lc, k ); // recurse left
    findArcs( node.rc, k ); // recurse right

end routine

Дайте мне знать, что вы думаете. Обратная связь приветствуется.

Я думаю, что придумал два наивных алгоритма, которые находят самый тяжелый путь с ограниченной длиной во взвешенном двоичном дереве. Во-первых, описание алгоритма выглядит следующим образом: для двоичного дерева с n вершинами с взвешенными ребрами и некоторого значения k найдите самый тяжелый путь длиной k.

Для обоих алгоритмов мне понадобится ссылка на все вершины поэтому я просто сделаю простой обход Дерева, чтобы иметь ссылку на все вершины, причем каждая вершина имеет ссылку на ее левый, правый и родительский узлы в дереве.

Алгоритм 1

routine heaviestKPath( T, k )

    // create 2D matrix with n rows and k columns with each element = -∞
    // we make it size k+1 because the 0th column must be all 0s for a later 
    // function to work properly and simplicity in our algorithm
    matrix = new array[ T.getVertexCount() ][ k + 1 ] (-∞);

    // set all elements in the first column of this matrix = 0
    matrix[ n ][ 0 ] = 0;

    // fill our matrix by traversing the tree
    traverseToFillMatrix( T.root, k );

    // consider a path that would arc over a node
    globalMaxWeight = -∞;
    findArcs( T.root, k );

    return globalMaxWeight
end routine


// node = the current node; k = the path length; node.lc = node’s left child; 
// node.rc = node’s right child; node.idx = node’s index (row) in the matrix; 
// node.lc.wt/node.rc.wt = weight of the edge to left/right child;
routine traverseToFillMatrix( node, k )

   if (node == null) return;

   traverseToFillMatrix(node.lc, k ); // recurse left
   traverseToFillMatrix(node.rc, k ); // recurse right

   // in the case that a left/right child doesn’t exist, or both,
   // let’s assume the code is smart enough to handle these cases
   matrix[ node.idx ][ 1 ] = max( node.lc.wt, node.rc.wt );


   for i = 2 to k {
       // max returns the heavier of the 2 paths
       matrix[node.idx][i] = max( matrix[node.lc.idx][i-1] + node.lc.wt, 
                                  matrix[node.rc.idx][i-1] + node.rc.wt);
   }

end routine



// node = the current node, k = the path length
routine findArcs( node, k ) 

    if (node == null) return;

    nodeMax = matrix[node.idx][k];
    longPath = path[node.idx][k];

    i = 1;
    j = k-1;
    while ( i+j == k AND i < k ) {

        left = node.lc.wt + matrix[node.lc.idx][i-1];
        right = node.rc.wt + matrix[node.rc.idx][j-1];

        if ( left + right > nodeMax ) {
            nodeMax = left + right;
        }
        i++; j--;
    }

    // if this node’s max weight is larger than the global max weight, update
    if ( globalMaxWeight < nodeMax ) {
        globalMaxWeight = nodeMax;
    }

    findArcs( node.lc, k ); // recurse left
    findArcs( node.rc, k ); // recurse right

end routine

Дайте мне знать, что вы думаете. Обратная связь приветствуется.

Я думаю, что придумал два наивных алгоритма, которые находят самый тяжелый путь с ограниченной длиной во взвешенном двоичном дереве. Во-первых, описание алгоритма выглядит следующим образом: для двоичного дерева с n вершинами и взвешенных ребер и некоторого значения k найдите самый тяжелый путь длиной k.

Для обоих алгоритмов мне понадобится ссылка на все вершины поэтому я просто сделаю простой обход Дерева, чтобы иметь ссылку на все вершины, причем каждая вершина имеет ссылку на ее левый, правый и родительский узлы в дереве.

Алгоритм 1 Для этого алгоритма я в основном планирую запускать DFS из каждого узла в дереве с учетом фиксированной длины пути. Кроме того, поскольку путь, который я ищу, потенциально может идти от левого поддерева к корневому поддереву к правому поддереву, мне придется рассмотреть 3 варианта на каждом узле. Но это приведет к алгоритму O (n * 3 ^ k), и мне это не нравится.

Алгоритм 2 По сути, я подумываю об использовании модифицированной версии алгоритма Дейкстры , чтобы учесть фиксированную длину пути. Поскольку я ищу самые тяжелые, а алгоритм Дейкстры находит самые легкие, я планирую отменить все веса ребер, прежде чем начинать обход. На самом деле ... это не имеет смысла, так как мне пришлось бы запускать Dijkstra на каждом узле, и это не кажется очень эффективным, намного лучше, чем вышеупомянутый алгоритм.

Итак, я предполагаю, что моих основных вопросов несколько. Во-первых, решают ли описанные выше алгоритмы поставленную задачу? Я не совсем уверен, что версия Дейкстры будет работать, поскольку версия Дейкстры предназначена для положительных значений фронта.

Теперь я уверен, что для этого существуют более умные / эффективные алгоритмы ... какой алгоритм лучше? Я' Мы читали про «Использование декомпозиции позвоночника для эффективного решения проблемы с самым тяжелым путём с ограниченной длиной для деревьев», но это действительно сложно, и я этого совсем не понимаю. Существуют ли другие алгоритмы, которые решают эту проблему, возможно, не так эффективно, как декомпозиция позвоночника, но более легкие для понимания?