algorithm - numeros - Convierta la matriz en ordenada utilizando solo dos operaciones

ordenar descendente matlab

Question

Encontré esta pregunta en un foro en línea: realmente me interesa cómo se puede resolver:

Dada una matriz A de enteros positivos. Convierta a una matriz ordenada con un costo mínimo. La única operación válida es:
1) Decremento con costo = 1
2) Eliminar un elemento completamente de la matriz con costo = valor del elemento

Esta es una pregunta de entrevista para una empresa de tecnología

Answer 1

Supongo que "ordenado" significa los valores más pequeños al inicio de la matriz, dada la naturaleza de las operaciones permitidas.

El límite de rendimiento entre las dos operaciones ocurre cuando el costo de eliminar un elemento fuera de secuencia es igual al costo de disminuir todos los elementos de mayor valor hasta el delincuente inclusive, o eliminar todos los elementos de menor valor después del delincuente. Puede elegir entre disminuir elementos precedentes o eliminar elementos posteriores en función de por qué el elemento infractor está fuera de secuencia. Si es menor que el elemento anterior, considere disminuir los elementos anteriores; si es mayor que el siguiente elemento, considere eliminar elementos posteriores.

Algunos ejemplos:

10 1 2 3 4 5

Decremento 10 a 1, costo 9

1 2 3 4 10 4

Eliminar 4, costo 4.

1 2 3 4 10 5

Eliminar 5 o disminuir de 10 a 5, costo 5.

5 6 7 8 1 10

Eliminar 1, costo 1.

5 6 7 8 6 10

Decremento 7 y 8 a 6, costo 3.

2 1 1 4 2 4 4 3

Disminuye el primer 1, el primero 4 por dos, y los otros dos cuatro una vez cada uno, cuesta 5.

La implementación más simple para encontrar las soluciones se basa en tener conocimiento establecido, por lo que es muy ineficiente. Afortunadamente, la pregunta no se preocupa por eso. La idea es recorrer el conjunto y tomar la decisión de eliminar o disminuir para fijar el conjunto cuando se encuentra un elemento fuera de secuencia. Una implementación mucho más eficiente de esto sería usar totales acumulados (a diferencia de calcular métodos) y recorrer la matriz dos veces, hacia adelante y hacia atrás. He escrito una maqueta de la versión más simple, ya que creo que es más fácil de leer.

Pseudocódigo, devuelve el costo total:

if array.Length < 2 : return 0; // no sorting necessary

resultArray = array.Copy();
int cost = 0;

for i = 0 to array.Length - 1 :

if i > 0 and array[i-1] > array[i] :

if CostToDecrementPreviousItems(i, array[i]) > array[i]) :
resultArray[i] = -1;
cost += array[i];
else :
cost += DecrementItemsThroughIndexGreaterThanValue(resultArray, i, array[i]);
end if

else if i < array.Length - 1 and array[i+1] < array[i] :

if CostToRemoveLaterItems(i, array[i]) > array[i] :
resultArray[i] = -1;
cost += array[i];
else :
cost += RemoveItemsAfterIndexGreaterThanValue(resultArray, i, array[i]);
end if

end if
end for

RemoveNegativeElements(resultArray);
array = resultArray;

return cost;

Afortunadamente, las llamadas al método indefinido son auto explicativas.

Answer 2

NOTA : La respuesta original ha sido reemplazada por una en la que tengo mucha más confianza (y puedo explicarlo también). Ambas respuestas produjeron los mismos resultados en mi conjunto de casos de prueba.

Puede resolver este problema utilizando un enfoque de programación dinámica. La observación clave es que nunca tiene sentido decrementar un número a un valor que no se encuentra en la matriz original. (Prueba informal: suponga que disminuyó un número O1 a un valor X que no está en la secuencia original para evitar eliminar un número O2 > X de la secuencia resultante. Entonces puede disminuir O1 a O2 lugar, y reducir el costo por O2-X ).

Ahora la solución se vuelve fácil de entender: es un DP en dos dimensiones. Si clasificamos los elementos de los distintos elementos de la secuencia original d en una matriz ordenada s , la longitud de d convierte en la primera dimensión de la DP; la longitud de s convierte en la segunda dimensión.

Declaramos dp[d.Length,s.Length] . El valor de dp[i,j] es el costo de resolver el subproblema d[0 to i] mientras se mantiene el último elemento de la solución bajo s[j] . Nota: este costo incluye el costo de eliminar d[i] si es menor que s[j] .

La primera fila dp[0,j] se calcula como el costo de recortar d[0] a s[j] , o cero si d[0] < s[j] . El valor de dp[i,j] siguiente fila se calcula como el mínimo de dp[i-1, 0 to j] + trim , donde trim es el costo de recortar d[i] a s[j] , o d[i] si necesita ser eliminado porque s[j] es más grande que d[i] .

La respuesta se calcula como el mínimo de la última fila dp[d.Length-1, 0 to s.Length] .

Aquí hay una implementación en C #:

static int Cost(int[] d) {
    var s = d.Distinct().OrderBy(v => v).ToArray();
    var dp = new int[d.Length,s.Length];
    for (var j = 0 ; j != s.Length ; j++) {
        dp[0, j] = Math.Max(d[0] - s[j], 0);
    }
    for (var i = 1; i != d.Length; i++) {
        for (var j = 0 ; j != s.Length ; j++) {
            dp[i, j] = int.MaxValue;
            var trim = d[i] - s[j];
            if (trim < 0) {
                trim = d[i];
            }
            dp[i, j] = int.MaxValue;
            for (var k = j ; k >= 0 ; k--) {
                dp[i, j] = Math.Min(dp[i, j], dp[i - 1, k] + trim);
            }
        }
    }
    var best = int.MaxValue;
    for (var j = 0 ; j != s.Length ; j++) {
        best = Math.Min(best, dp[d.Length - 1, j]);
    }
    return best;
}

Esta implementación directa tiene una complejidad espacial de O(N^2) . Puede reducirlo a O(N) al observar que solo se utilizan dos últimas filas al mismo tiempo.

Answer 3

1. Construya el gráfico de decisión, agregue el vértice de inicio a él. Cada vértice contiene "nivel de recorte", es decir, el valor al que se deben disminuir todos los valores de matriz a la izquierda del nodo actual. El "nivel de ajuste" del vértice de inicio es infinito. Cada borde del gráfico tiene un valor, que corresponde al costo de la decisión.
2. Para cada elemento de la matriz, comenzando desde la derecha, realice los pasos 3 .. 5.
3. Para cada vértice de hoja, realice los pasos 4 .. 5.
4. Cree hasta 2 bordes salientes, (1) con el costo de eliminar el elemento de la matriz y (2) con el costo de recortar todos los elementos a la izquierda (exactamente, el costo de disminuir el "nivel de recorte").
5. Conecte estos bordes a los vértices recién creados, un vértice para cada elemento de la matriz y cada "nivel de recorte".
6. Encuentre la ruta más corta desde el vértice de inicio hasta uno de los vértices, que corresponde al elemento de la matriz más a la izquierda. La longitud de esta ruta es igual al costo de la solución.
7. Disminuir y eliminar elementos de la matriz según el gráfico de decisión.

Este algoritmo se puede tratar como una optimización del enfoque de fuerza bruta. Para la búsqueda de fuerza bruta, comenzando desde el elemento de la matriz más a la derecha, construye el árbol de decisión binario. Cada vértice tiene 2 bordes de salida, uno para la decisión de "eliminar", otra decisión de "recorte". El costo de la decisión está asociado con cada borde. El "nivel de recorte" está asociado a cada vértice. La solución óptima está determinada por el camino más corto en este árbol.

Elimine cada ruta, que obviamente no es óptima. Por ejemplo, si el elemento más grande es el último en la matriz, la decisión de "recortar" ha costado cero, y la decisión de "eliminar" no es óptima. Eliminar ruta, a partir de esta decisión de "eliminar". Después de esta optimización, el árbol de decisión es más disperso: algunos vértices tienen 2 bordes salientes, algunos, solo uno.

En cada nivel de profundidad, el árbol de decisión puede tener varios vértices con el mismo "nivel de recorte". Los subárboles, a partir de estos vértices, son idénticos entre sí. Esa es una buena razón para unir todos estos vértices a un vértice. Esto transforma el árbol en un gráfico que tiene a lo sumo n 2/2 vértices.

Complejidad

La implementación más simple de este algoritmo es O (n ³ ), porque para cada uno de los vértices O (n ² ) calcula el costo de recorte iterativamente, en el tiempo O (n).

No es necesario realizar cálculos de costos de recorte repetidos si hay suficiente memoria para almacenar todos los resultados del costo de recorte parcial. Esto puede requerir O (n ² ) o incluso O (n) espacio.

Con tal optimización, este algoritmo es O (n ² ). Debido a la estructura simple del gráfico, la búsqueda de ruta más corta tiene complejidad O (n ² ), no O (n ² * log (n)).

Implementación de C ++ 11 (la complejidad del espacio y el tiempo es O (n ² )):

//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;
}