- Построить граф решений, добавить к нему начальную вершину. Каждая вершина содержит «уровень обрезки», то есть значение, до которого следует уменьшить все значения массива слева от текущего узла. «Уровень обрезки» начальной вершины равен бесконечности. Каждое ребро графа имеет значение, соответствующее стоимости решения.
- Для каждого элемента массива, начиная с самого правого, выполните шаги 3 .. 5.
- Для каждой листовой вершины выполните шаги 4 .. 5.
- Создайте до 2 исходящих ребер, (1) со стоимостью удаления элемента массива и (2) со стоимостью обрезки всех элементов влево (в точности стоимость уменьшения «уровня обрезки»).
- Соедините эти ребра с вновь созданными вершинами, по одной вершине для каждого элемента массива и каждому «уровню обрезки».
- Найти кратчайший путь от начальной вершины до одной из вершин, соответствующих крайнему левому элементу массива. Длина этого пути равна стоимости решения.
- Уменьшение и удаление элементов массива в соответствии с графиком решений.
Этот алгоритм может рассматриваться как оптимизация метода грубой силы. Для поиска методом грубой силы, начиная с самого правого элемента массива, создайте двоичное дерево решений. Каждая вершина имеет 2 исходящих ребра, одно для решения «удалить», другое для «обрезки». Стоимость решения связана с каждым ребром. «Уровень обрезки» связан с каждой вершиной. Оптимальное решение определяется кратчайшим путем в этом дереве.
Удалите все пути, которые, очевидно, неоптимальны. Например, если самый большой элемент является последним в массиве, решение «обрезать» имеет нулевую стоимость, а решение «удалить» не является оптимальным. Удалить путь, начиная с этого решения «удалить». После этой оптимизации дерево решений становится более разреженным: у некоторых вершин есть 2 исходящих ребра, у некоторых - только один.
На каждом уровне глубины дерево решений может иметь несколько вершин с одинаковым «уровнем обрезки». Поддеревья, начиная с этих вершин, идентичны друг другу. Это хорошая причина объединить все эти вершины в одну вершину. Это преобразует дерево в граф, имеющий не более n 2 / 2 вершин.
Сложность
Простейшей реализацией этого алгоритма является O (n 3 ), потому что для каждой из O (n 2 ) вершин он вычисляет стоимость обрезки итеративно, за O (n) времени .
Повторные расчеты стоимости обрезки не нужны, если имеется достаточно памяти для хранения всех частичных результатов стоимости обрезки. Это может потребовать O (n 2 ) или даже O (n) пробел.
При такой оптимизации этот алгоритм равен O (n 2 ). Из-за простой структуры графа поиск по кратчайшему пути имеет сложность O (n 2 ), а не O (n 2 * log (n)).
Реализация C ++ 11 (сложность пространства и времени равна O (n 2 )):
//g++ -std=c++0x
#include <iostream>
#include <vector>
#include <algorithm>
typedef unsigned val_t;
typedef unsigned long long acc_t; // to avoid overflows
typedef unsigned ind_t;
typedef std::vector<val_t> arr_t;
struct Node
{
acc_t trimCost;
acc_t cost;
ind_t link;
bool used;
Node()
: trimCost(0)
, used(false)
{}
};
class Matrix
{
std::vector<Node> m;
ind_t columns;
public:
Matrix(ind_t rows, ind_t cols)
: m(rows * cols)
, columns(cols)
{}
Node& operator () (ind_t row, ind_t column)
{
return m[columns * row + column];
}
};
void fillTrimCosts(const arr_t& array, const arr_t& levels, Matrix& matrix)
{
for (ind_t row = 0; row != array.size(); ++row)
{
for (ind_t column = 0; column != levels.size(); ++column)
{
Node& node = matrix(row + 1, column);
node.trimCost = matrix(row, column).trimCost;
if (array[row] > levels[column])
{
node.trimCost += array[row] - levels[column];
}
}
}
}
void updateNode(Node& node, acc_t cost, ind_t column)
{
if (!node.used || node.cost > cost)
{
node.cost = cost;
node.link = column;
}
}
acc_t transform(arr_t& array)
{
const ind_t size = array.size();
// Sorted array of trim levels
arr_t levels = array;
std::sort(levels.begin(), levels.end());
levels.erase(
std::unique(levels.begin(), levels.end()),
levels.end());
// Initialize matrix
Matrix matrix(size + 1, levels.size());
fillTrimCosts(array, levels, matrix);
Node& startNode = matrix(size, levels.size() - 1);
startNode.used = true;
startNode.cost = 0;
// For each array element, starting from the last one
for (ind_t row = size; row != 0; --row)
{
// Determine trim level for this array element
auto iter = std::lower_bound(levels.begin(), levels.end(), array[row - 1]);
const ind_t newLevel = iter - levels.begin();
// For each trim level
for (ind_t column = 0; column != levels.size(); ++column)
{
const Node& node = matrix(row, column);
if (!node.used)
continue;
// Determine cost of trimming to current array element's level
const acc_t oldCost = node.trimCost;
const acc_t newCost = matrix(row, newLevel).trimCost;
const acc_t trimCost = (newCost > oldCost)? newCost - oldCost: 0;
// Nodes for "trim" and "delete" decisions
Node& trimNode = matrix(row - 1, newLevel);
Node& nextNode = matrix(row - 1, column);
if (trimCost)
{
// Decision needed, update both nodes
updateNode(trimNode, trimCost + node.cost, column);
updateNode(nextNode, array[row - 1] + node.cost, column);
trimNode.used = true;
}
else
{
// No decision needed, pass current state to the next row's node
updateNode(nextNode, node.cost, column);
}
nextNode.used = true;
}
}
// Find optimal cost and starting trim level for it
acc_t bestCost = size * levels.size();
ind_t bestLevel = levels.size();
for (ind_t column = 0; column != levels.size(); ++column)
{
const Node& node = matrix(0, column);
if (node.used && node.cost < bestCost)
{
bestCost = node.cost;
bestLevel = column;
}
}
// Trace the path of minimum cost
for (ind_t row = 0; row != size; ++row)
{
const Node& node = matrix(row, bestLevel);
const ind_t next = node.link;
if (next == bestLevel && node.cost != matrix(row + 1, next).cost)
{
array[row] = 0;
}
else if (array[row] > levels[bestLevel])
{
array[row] = levels[bestLevel];
}
bestLevel = next;
}
return bestCost;
}
void printArray(const arr_t& array)
{
for (val_t val: array)
if (val)
std::cout << val << ' ';
else
std::cout << "* ";
std::cout << std::endl;
}
int main()
{
arr_t array({9,8,7,6,5,4,3,2,1});
printArray(array);
acc_t cost = transform(array);
printArray(array);
std::cout << "Cost=" << cost << std::endl;
return 0;
}