Análisis competitivo (algoritmo en línea)

El análisis competitivo es un método inventado para analizar algoritmos en línea, en cual el rendimiento de un algoritmo en línea (que debe satisfacer una secuencia imprevisible de solicitudes, completando cada solicitud sin ser capaz de ver el futuro) es comparado con el rendimiento de un algoritmo autónomo óptimo que puede ver la secuencia de solicitudes de antemano. Un algoritmo es competitivo si su proporción competitiva — la proporción entre su actuación y la actuación del algoritmo autónomo — se salta. A diferencia del análisis del caso peor tradicional, donde el rendimiento de un algoritmo sólo se mide para entradas "difíciles", el análisis competitivo requiere que un algoritmo funcione bien tanto en entradas difíciles como fáciles, donde "difícil" y "fácil" son definidos por el rendimiento del algoritmo autónomo óptimo.

Para muchos algoritmos, el rendimiento es dependiente no sólo de la talla de las entradas, sino también en sus valores. Un tal ejemplo es el algoritmo quicksort, que clasifica una serie de elementos. Tales algoritmos dependientes de los datos se analizan para datos del caso peor y caso medio. El análisis competitivo es un modo de hacer el análisis del caso peor para algoritmos en línea y aleatorios, que son típicamente el dependiente de datos.

En el análisis competitivo, uno imagina a un "adversario" que deliberadamente elige datos difíciles, para maximizar la proporción del coste del algoritmo estudiado y algún algoritmo óptimo. Los adversarios se extienden en el poder del adversario inconsciente, que no tiene conocimiento de las opciones arbitrarias hechas por el algoritmo enfrentado con él, al adversario adaptable que tiene el conocimiento lleno de cómo un algoritmo trabaja y su estado interno a cualquier punto durante su ejecución. Note que esta distinción sólo es significativa para algoritmos aleatorios. Para un algoritmo determinista, el uno o el otro adversario puede calcular simplemente lo que declara que el algoritmo debe tener en cualquier momento en el futuro, y elegir datos difíciles en consecuencia.

Por ejemplo, el algoritmo quicksort elige un elemento, llamado el "pivote", es decir por término medio, no demasiado lejano del valor del centro de los datos clasificados. Quicksort entonces separa los datos en dos hemorroides, una de las cuales contiene todos los elementos con el valor menos que el valor del pivote y el otro que contiene el resto de los elementos. Si quicksort elige el pivote de alguna moda determinista (por ejemplo, siempre eligiendo el primer elemento en la lista), entonces es fácil para un adversario arreglar los datos de antemano de modo que quicksort funcione en el tiempo del caso peor. Si, sin embargo, el quicksort elige algún elemento arbitrario para ser el pivote, entonces un adversario sin el conocimiento de lo que los números arbitrarios suben no puede arreglar los datos para garantizar el tiempo de ejecución del caso peor para quicksort.

El problema en línea clásico primero analizado con el análisis competitivo es el problema de actualización de la Lista: Considerando una lista de artículos y una secuencia de peticiones de varios artículos, minimice el coste de tener acceso a la lista donde los elementos más cerca al frente de la lista cuestan menos al acceso. (Típicamente, el coste de tener acceso a un artículo es igual a su posición en la lista.) Después de un acceso, la lista se puede reajustar. La mayor parte de cambios de lugar tienen un coste. El algoritmo del movimiento al Frente simplemente mueve el artículo solicitado al frente después del acceso, gratis. El algoritmo Transportar no cambia el artículo tenido acceso con el artículo inmediatamente antes de ello, también gratis. Los métodos clásicos del análisis mostraron que esto Transporta es óptimo en ciertos contextos. En la práctica, el movimiento al Frente funcionó mucho mejor. El análisis competitivo era usado para mostrar que un adversario puede hacer Transportan funcionan arbitrariamente mal comparado con un algoritmo óptimo, mientras que el movimiento al Frente nunca se puede hacer incurrir en más que dos veces el coste de un algoritmo óptimo.

En caso de solicitudes en línea de un servidor, los algoritmos competitivos son usados para vencer incertidumbres sobre el futuro. Es decir el algoritmo "no sabe" el futuro, mientras el adversario imaginario (el "competidor") "sabe". Los algoritmos competitivos del mismo modo, se desarrollaron para sistemas distribuidos, donde el algoritmo tiene que reaccionar a una solicitud llegando a una posición, sin "saber" lo que acaba de pasar en una posición remota. Este ajuste se presentó en.

Véase también



Buscar