ОБНОВЛЕНИЕ
Я разработал алгоритм, который, я думаю, работает за время 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 Для этого алгоритма я в основном планирую запускать DFS из каждого узла дерева с учетом фиксированной длины пути.Кроме того, поскольку путь, который я ищу, потенциально может перейти от левого поддерева к корневому поддереву к правому поддереву, мне придется рассмотреть 3 варианта на каждом узле.Но это приведет к алгоритму O (n * 3 ^ k), и мне это не нравится.
Алгоритм 2 По сути, я думаю об использовании модифицированной версии Алгоритм Дейкстры для рассмотрения фиксированной длины пути.Поскольку я ищу самые тяжелые, а алгоритм Дейкстры находит самые легкие, я планирую свести на нет все веса ребер, прежде чем начинать обход.На самом деле ... это не имеет смысла, так как мне пришлось бы запускать Dijkstra на каждом узле, и это не выглядит намного эффективнее, чем приведенный выше алгоритм.
Так что я думаю, что у меня есть несколько основных вопросов.,Во-первых, описанные выше алгоритмы решают проблему под рукой?Я не совсем уверен, что версия Дейкстры будет работать, так как версия Дейкстры предназначена для положительных краевых значений.
Теперь я уверен, что существуют более умные / эффективные алгоритмы для этого ... Какой алгоритм лучше?Я читал о «Использование разложений позвоночника для эффективного решения проблемы тяжёлого пути с ограниченными длинами деревьев», но это действительно сложно, и я совсем не понимаю этого.Существуют ли другие алгоритмы, которые решают эту проблему, возможно, не так эффективно, как разложение позвоночника, но легче для понимания?