Problema dinámico (algoritmos)

En informática , los problemas dinámicos son aquellos que se plantean en términos de datos de entrada cambiantes. En su forma más general, un problema de esta categoría se suele plantear de la siguiente manera:

Dada una estructura compuesta por objetos, encuentre algoritmos y estructuras de datos eficientes para responder a ciertas consultas sobre la estructura, al tiempo que se admiten de forma eficiente operaciones de actualización como la inserción, eliminación o modificación de objetos en la estructura.

Los problemas de esta clase tienen las siguientes medidas de complejidad:

Espacio : la cantidad de espacio de memoria necesario para almacenar la estructura de datos;
Tiempo de inicialización : tiempo necesario para la construcción inicial de la estructura de datos;
Tiempo de inserción : tiempo necesario para actualizar la estructura de datos cuando se agrega un elemento de entrada más;
Tiempo de eliminación : tiempo necesario para actualizar la estructura de datos cuando se elimina un elemento de entrada;
Tiempo de consulta : tiempo necesario para responder a una consulta;
Otras operaciones específicas del problema en cuestión.

El conjunto general de cálculos para un problema dinámico se denomina algoritmo dinámico .

Muchos problemas algorítmicos planteados en términos de datos de entrada fijos (denominados problemas estáticos en este contexto y resueltos mediante algoritmos estáticos ) tienen versiones dinámicas significativas.

Casos especiales

Los algoritmos incrementales , o algoritmos en línea , son algoritmos en los que solo se permiten adiciones de elementos, posiblemente partiendo de datos de entrada vacíos o triviales.

Los algoritmos decrementales son aquellos en los que solo se permite la eliminación de elementos, comenzando con la inicialización de una estructura de datos completa.

Si se permiten tanto adiciones como eliminaciones, el algoritmo a veces se denomina totalmente dinámico .

Ejemplos

Elemento máximo

Problema estático: Para un conjunto de N números, encuentra el máximo.

El problema puede resolverse en tiempo O( N ).

Problema dinámico: Para un conjunto inicial de N números, mantenga dinámicamente el número máximo cuando se permitan inserciones y eliminaciones.

Este es solo el problema de mantenimiento de la cola de prioridad que permite inserciones y eliminaciones; se puede resolver, por ejemplo, utilizando un montón binario en $O(\log N)$ es hora de una actualización y $O(1)$ tiempo para una consulta, con $O(N)$ Tiempo de configuración (es decir, el procesamiento inicial de los datos). Tenga en cuenta que el valor de N puede cambiar durante la vida útil de la estructura.

Gráficos

Dado un grafo, mantener sus parámetros, como conectividad, grado máximo, caminos más cortos, etc., cuando se permite la inserción y eliminación de sus aristas. ^{[ 1 ]}

Ejemplos:

Existe un algoritmo que mantiene el bosque de expansión mínima de un grafo no dirigido ponderado, sujeto a eliminaciones e inserciones de aristas, en $O(n^{1/2})$ tiempo por actualización. ^{[ 2 ]}
Existe un algoritmo que mantiene el bosque de expansión mínima de un grafo no dirigido ponderado, sujeto a eliminaciones e inserciones de aristas, en $O(n^{1/3}\log n)$ tiempo amortizado por actualización. ^{[ 3 ]}

Véase también

Referencias

↑ D. Eppstein , Z. Galil y GF Italiano . «Algoritmos de grafos dinámicos». En CRC Handbook of Algorithms and Theory of Computation , Capítulo 22. CRC Press, 1997.
↑ Eppstein, David; Italiano, Giuseppe; Nissenzweig, Amnon (1997). "Esparsificación: una técnica para acelerar los algoritmos de grafos dinámicos". Journal of the ACM . 44 (5): 669– 696. doi : 10.1145/265910.265914 .
↑ Henzinger, Monika; King, Valerie (2001). "Mantenimiento de bosques de expansión mínima en grafos dinámicos" . SIAM Journal on Computing . 31 (2): 364– 374. doi : 10.1137/S0097539797327209 .

[1] D. Eppstein , Z. Galil y GF Italiano . «Algoritmos de grafos dinámicos». En CRC Handbook of Algorithms and Theory of Computation , Capítulo 22. CRC Press, 1997.

[sparsification-2] Eppstein, David; Italiano, Giuseppe; Nissenzweig, Amnon (1997). "Esparsificación: una técnica para acelerar los algoritmos de grafos dinámicos". Journal of the ACM . 44 (5): 669– 696. doi : 10.1145/265910.265914 .

[HK2001-3] Henzinger, Monika; King, Valerie (2001). "Mantenimiento de bosques de expansión mínima en grafos dinámicos" . SIAM Journal on Computing . 31 (2): 364– 374. doi : 10.1137/S0097539797327209 .

[ 1 ]

[ 2 ]

[ 3 ]