Problema de actualización de la lista

El problema de actualización o acceso a listas es un modelo simple utilizado en el estudio del análisis competitivo de algoritmos en línea . Dado un conjunto de elementos en una lista donde el costo de acceso a un elemento es proporcional a su distancia desde el inicio de la lista (por ejemplo, una lista enlazada) , y una secuencia de solicitudes de acceso, el problema consiste en idear una estrategia para reordenar la lista de manera que se minimice el costo total de los accesos. El reordenamiento puede realizarse en cualquier momento, pero conlleva un costo. El modelo estándar incluye dos acciones de reordenamiento:

• Una transposición libre del elemento al que se accede en cualquier lugar anterior a su posición actual;
• Una transposición pagada de un costo unitario por intercambiar dos elementos adyacentes cualesquiera en la lista.

El rendimiento de los algoritmos depende de la construcción de secuencias de solicitudes por parte de los adversarios bajo diversos modelos de adversarios.

Un algoritmo en línea para este problema tiene que reordenar los elementos y atender las solicitudes basándose únicamente en el conocimiento de los elementos solicitados previamente, por lo que su estrategia puede no tener el coste óptimo en comparación con un algoritmo fuera de línea que puede ver toda la secuencia de solicitudes y diseñar una estrategia completa antes de atender la primera solicitud.

Además de sus usos originales, se ha sugerido que este problema guarda una gran similitud con los problemas de mejora del contexto global y la compresibilidad tras una transformación de Burrows-Wheeler . Tras esta transformación, los archivos suelen presentar grandes regiones con frecuencias localmente elevadas, y la eficiencia de la compresión mejora notablemente con técnicas que tienden a desplazar los caracteres más frecuentes hacia el principio de la lista. Por ello, los métodos y variantes de Move-to-Front y el conteo de frecuencias suelen seguir al algoritmo BWT para mejorar la compresibilidad.

Un adversario es una entidad que elige la secuencia de solicitud.${\displaystyle \sigma }$para un algoritmo ALG . Dependiendo de si${\displaystyle \sigma }$Se puede modificar en función de la estrategia de ALG , a los adversarios se les otorgan diversos poderes y el rendimiento de ALG se mide frente a estos adversarios.

Un adversario desprevenido tiene que construir toda la secuencia de solicitud.${\displaystyle \sigma }$antes de ejecutar ALG y paga el precio óptimo fuera de línea,${\displaystyle OPT(\sigma )}$que se compara con${\displaystyle ALG(\sigma )}$

Un adversario en línea adaptativo puede realizar la siguiente solicitud basándose en los resultados previos del algoritmo en línea, pero paga por la solicitud de forma óptima y en línea.

Un adversario adaptativo fuera de línea puede realizar la siguiente solicitud basándose en los resultados previos del algoritmo en línea, pero pagando el costo óptimo fuera de línea.

Se realizó un análisis competitivo para muchos problemas de actualización de listas sin ningún conocimiento específico de la naturaleza exacta del algoritmo fuera de línea óptimo (OPT). Existe un algoritmo que se ejecuta en tiempo O( ^n²m ( m - 1)!) y espacio O( m !) , donde n es la longitud de la secuencia de solicitud y m es la longitud de la lista. ^{[ 1 ]} El mejor algoritmo fuera de línea óptimo conocido, que depende de la longitud de la secuencia de solicitud, se ejecuta en tiempo O(m²(m-1)!n), según afirmó el Dr. Srikrishnan Divakaran en 2014. ^{[ 2 ]}

Las transposiciones de pago son, en general, necesarias para los algoritmos óptimos. Consideremos una lista ( a , b , c ) donde a está al principio y una secuencia de solicitudes c , b , c , b . Un algoritmo óptimo fuera de línea que utilice únicamente intercambios gratuitos costaría 9 (3+3+2+1), mientras que un algoritmo óptimo fuera de línea que utilice únicamente intercambios de pago costaría 8. Por lo tanto, no podemos prescindir de las transposiciones gratuitas para el algoritmo óptimo fuera de línea.

Se demostró que el problema de actualización óptima de la lista es NP-difícil por ( Ambühl 2000 ) .

Un algoritmo en línea ALG tiene una razón competitiva c si para cualquier entrada se desempeña al menos tan bien como c veces peor que OPT. Es decir, si existe un${\displaystyle \alpha \geq 0}$de tal manera que para todas las secuencias de solicitud de longitud finita${\displaystyle \sigma }$,${\displaystyle ALG(\sigma )-c.OPT(\sigma )\leq \alpha }$Los algoritmos en línea pueden ser deterministas o aleatorios, y resulta que la aleatorización en este caso puede ser de gran ayuda contra adversarios desprevenidos.

El problema de actualización de listas donde se pueden insertar y eliminar elementos se llama problema de actualización dinámica de listas, a diferencia del problema de actualización estática de listas donde solo se permite el acceso a los elementos de la lista. El límite inferior de${\displaystyle 2-{\frac {2}{l+1}}}$Esto también se aplica al modelo dinámico.

También existen diferentes modelos de costos. En el modelo de costo total habitual, el acceso a un elemento ubicado en la posición i cuesta i , pero la última comparación es inevitable para cualquier algoritmo, es decir, hay i-1 elementos que se interponen en el camino de i . En el modelo de costo parcial, estos costos de comparación final, que suman el número de elementos en la secuencia de solicitud, se ignoran. Para los costos de transposiciones pagadas distintas de la unidad, se utilizan modelos P ^{d .}

• Algoritmo en línea
• Análisis competitivo
• Algoritmos de caché

• Sleator, D .; Tarjan, R. (1985), "Eficiencia amortizada de las reglas de actualización y paginación de listas", Communications of the ACM , 28 (2): 202–208 , CiteSeerX 10.1.1.367.6317 , doi : 10.1145/2786.2793 , S2CID 2494305  .
• Borodin, A.; El-Yaniv, R. (1998). Computación en línea y análisis competitivo . Cambridge University Press. ISBN 978-0-521-56392-5.

• Ambühl, C. (2000), La actualización de listas sin conexión es NP-difícil , Springer, págs. 42–51