El problema List Update o List Access 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 acceder a un elemento es proporcional a su distancia del encabezado de la lista, por ejemplo, una lista enlazada , y una secuencia de solicitud de accesos, el problema es idear una estrategia de reorden la lista para que se minimice el coste total de accesos. El reordenamiento se puede realizar en cualquier momento pero tiene un coste. El modelo estándar incluye dos acciones de reordenamiento:
- Una transposición libre del elemento al que se accede en cualquier lugar antes de su posición actual;
- Una transposición pagada de un costo unitario por intercambiar dos elementos adyacentes en la lista. El rendimiento de los algoritmos depende de la construcción de secuencias de solicitudes por parte de los adversarios en varios modelos de adversario.
Un algoritmo en línea para este problema tiene que reordenar los elementos y atender las solicitudes basándose solo en el conocimiento de los elementos solicitados previamente y, por lo tanto, su estrategia puede no tener el costo óptimo en comparación con un algoritmo fuera de línea que puede ver la secuencia completa de la solicitud y diseñar una completar la estrategia antes de atender la primera solicitud.
Junto con sus usos originales, se ha sugerido que este problema tiene una fuerte similitud con los problemas de mejorar el contexto global y la compresibilidad después de una Transformada de Burrows-Wheeler . Después de esta transformación, los archivos tienden a tener regiones grandes con frecuencias localmente altas, y la eficiencia de la compresión mejora en gran medida mediante técnicas que tienden a mover los caracteres frecuentes hacia cero, o al principio de la "lista". Debido a esto, los métodos y variantes de Move-to-Front y los recuentos de frecuencia a menudo siguen el algoritmo BWT para mejorar la compresibilidad.
Modelos adversarios
Un adversario es una entidad que elige la secuencia de solicitud. para un algoritmo ALG . Dependiendo de sipuede cambiarse en función de la estrategia de ALG , los adversarios reciben varios poderes y el desempeño de ALG se mide frente a estos adversarios.
Un adversario ajeno tiene que construir toda la secuencia de solicitud.antes de ejecutar ALG y paga el precio óptimo sin conexión, que se compara con
Un adversario en línea adaptable puede realizar la siguiente solicitud en función de los resultados anteriores del algoritmo en línea, pero paga la solicitud de manera óptima y en línea.
Un adversario adaptativo fuera de línea puede realizar la siguiente solicitud en función de los resultados anteriores del algoritmo en línea, pero paga el costo fuera de línea óptimo.
Algoritmos sin conexión
Se llevaron a cabo análisis competitivos para muchos problemas de actualización de listas sin ningún conocimiento específico de la naturaleza exacta del algoritmo óptimo fuera de línea (OPT). Existen ejecuciones de algoritmos en O ( n 2 l ( l -1)!) Tiempo y O ( l !) Espacio donde n es la longitud de la secuencia de solicitud y l es la longitud de la lista. [1] El algoritmo sin conexión óptimo más conocido que depende de la longitud de la secuencia de solicitud se ejecuta en O (l ^ 2 (l − 1)! N) tiempo publicado por el Dr. Srikrishnan Divakaran en 2014. [2]
Las transposiciones pagadas son, en general, necesarias para unos algoritmos óptimos. Considere una lista ( a , b , c ) donde a está al principio de la lista y una secuencia de solicitud c , b , c , b . Un algoritmo fuera de línea óptimo que usa solo intercambios gratuitos costaría 9 (3 + 3 + 2 + 1), mientras que un algoritmo fuera de línea óptimo que usa solo intercambios pagos costaría 8. Por lo tanto, no podemos salirse con la nuestra con solo usar transposiciones gratuitas para el algoritmo fuera de línea óptimo .
( Ambühl 2000 ) demostró que el problema de actualización de la lista óptima era NP-hard . .
Algoritmo en línea
Un algoritmo en línea ALG tiene una relación competitiva c si para cualquier entrada funciona al menos tan bien como c veces peor que OPT. es decir, si existe un tal que para todas las secuencias de solicitud de longitud finita , . Los algoritmos en línea pueden ser deterministas o aleatorizados y resulta que la aleatorización en este caso realmente puede ayudar contra adversarios ajenos.
Determinista
La mayoría de los algoritmos deterministas son variantes de estos tres algoritmos:
- MTF (Mover al frente)
- Después de acceder a un elemento, muévalo al principio de la lista sin cambiar el orden de otros elementos
- TRANS (Transponer)
- Después de acceder a un elemento, transpóngalo con el elemento inmediatamente anterior.
- FC (recuento de frecuencia)
- Para cada elemento, mantenga un recuento de frecuencia del número de accesos al mismo; cuando se accede a un elemento, aumente su recuento de frecuencia y reordene la lista en orden decreciente de frecuencias.
Observe que todos estos usan solo transposiciones libres. Resulta que tanto TRANS como FC no son competitivos. En un resultado clásico utilizando el análisis del método de potencial ( Sleator y Tarjan 1985 ) se demostró que MTF es 2-competitivo. La demostración no requiere el conocimiento explícito de OPT, sino que cuenta el número de inversiones, es decir, elementos que ocurren en orden opuesto en las listas de MTF y OPT.
Cualquier algoritmo determinista tiene un límite inferior de para una lista de longitud l , y MTF es en realidad el algoritmo de actualización de lista determinista óptimo. El tipo de adversario no importa en el caso de los algoritmos deterministas, porque el adversario puede ejecutar una copia del algoritmo determinista por sí mismo para calcular previamente la secuencia más desastrosa.
Aleatorizado
Considere el siguiente algoritmo aleatorio simple:
- UN POCO
- Para cada elemento de la lista, mantenga un poco. Inicialice todos los bits de manera uniforme y aleatoria a 0 o 1. Cuando se acceda a un elemento, gire el bit y, si es 1, muévalo al frente, de lo contrario, no lo haga.
Este algoritmo es apenas aleatorio: hace todas sus elecciones aleatorias al principio y no durante la ejecución. Resulta que BIT rompe el límite determinista: es mejor que MTF contra adversarios ajenos. Es 7/4 competitivo. Hay otros algoritmos aleatorios, como COMB, que funcionan mejor que BIT. Boris Teia demostró un límite inferior de 1,5 para cualquier algoritmo de actualización de listas aleatorias. [3]
Problemas relacionados
El problema de actualización de la lista donde los elementos pueden insertarse y eliminarse se denomina problema de actualización de la lista dinámica, a diferencia del problema de actualización de la lista estática donde solo se permite acceder a los elementos de la lista. El límite superior de también se aplica al modelo dinámico.
También existen diferentes modelos de costos. En el modelo habitual de costo total, un acceso a un elemento ubicado en una posición i cuesta i , pero la última comparación es inevitable para cualquier algoritmo, es decir, hay elementos i-1 que se interponen en el camino de i . En el modelo de costo parcial, se ignoran estos costos de comparación final que suman el número de elementos en la secuencia de solicitud. Para los costos de transposiciones pagadas distintas de la unidad, se utilizan modelos P d .
Ver también
Notas
- ^ N. Reingold y J. Westbrook. Algoritmos óptimos sin conexión para la actualización de la lista y las reglas de paginación. Informe técnico YALE / DcS / TR-805, Universidad de Yale, New Haven, Connecticut, agosto de 1990
- ↑ Divakaran, Srikrishnan (30 de abril de 2014). "Un algoritmo sin conexión óptimo para la actualización de la lista". arXiv : 1404,7638 [ cs.DS ].
- ^ Teia, Boris, Un límite inferior para algoritmos de actualización de listas aleatorias, Inf. Proceso. Letón. (1993), págs. 5-9
Referencias
- Sleator, D .; Tarjan, R. (1985), "Eficiencia amortizada de las reglas de paginación y actualización de listas", Comunicaciones del ACM , 28 (2): 202-208, CiteSeerX 10.1.1.367.6317 , doi : 10.1145 / 2786.2793.
- Borodin, A .; El-Yaniv, R. (1998). Computación en línea y análisis competitivo . Prensa de la Universidad de Cambridge. ISBN 978-0-521-56392-5.
- Ambühl, C. (2000), La actualización de la lista sin conexión es np-hard , Springer, págs. 42–51