Una distinción de caso en programación dinámica: ¡ejemplo necesario!

He estado trabajando en programación dinámica por algún tiempo. La forma canónica de evaluar una recursión de programación dinámica es creando una tabla de todos los valores necesarios y llenándola fila por fila. Ver por ejemplo Cormen, Leiserson et al: "Introducción a los algoritmos" para una introducción.

Me concentro en el esquema de cálculo basado en tablas en dos dimensiones (relleno fila por fila) e investigo la estructura de las dependencias de las celdas, es decir, qué celdas deben hacerse antes de que se pueda calcular otra. Denotamos con el conjunto de índices de celdas de las que depende la celda . Tenga en cuenta que necesita estar libre de ciclos.i$\Gamma(\mathbf{i})$$\mathbf{i}$$\Gamma$

Extracto de la función real que se calcula y me concentro en su estructura recursiva. Formalmente, considero que una recurrencia es programación dinámica si tiene la forma$d$

$\qquad d(\mathbf{i}) = f(\mathbf{i}, \widetilde{\Gamma}_d(\mathbf{i}))$

con , y alguna función (computable) que no utiliza que no sea a través de .˜ Γ d ( i ) = { ( j , d ( j ) ) ∣ j ∈ Γ d ( i ) } f d ˜ Γ$\mathbf{i} \in [0\dots m] \times [0\dots n]$$\widetilde{\Gamma}_d(\mathbf{i}) = \{(\mathbf{j},d(\mathbf{j})) \mid \mathbf{j} \in \Gamma_d(\mathbf{i}) \}$$f$$d$$\widetilde{\Gamma}_d$

Al restringir la granularidad de a áreas rugosas (a la izquierda, arriba a la izquierda, arriba, arriba a la derecha, ... de la celda actual) se observa que existen esencialmente tres casos (hasta simetrías y rotación) de validez Recurrencias de programación dinámica que informan cómo se puede llenar la tabla:$\Gamma_d$

Las áreas rojas denotan (sobre aproximaciones de) . Los casos uno y dos admiten subconjuntos, el caso tres es el peor de los casos (hasta la transformación del índice). Tenga en cuenta que no es estrictamente necesario que todas las áreas rojas estén cubiertas por ; Algunas celdas en cada parte roja de la tabla son suficientes para pintarla de rojo. Se requiere explícitamente que las áreas blancas no contengan ninguna celda requerida.$\Gamma$$\Gamma$

Ejemplos para el caso uno son la distancia de edición y la subsecuencia común más larga , el caso dos se aplica a Bellman & Ford y CYK . Entre los ejemplos menos obvios se incluyen los que funcionan en las diagonales en lugar de las filas (o columnas), ya que pueden rotarse para ajustarse a los casos propuestos; Vea la respuesta de Joe como ejemplo.

¡Sin embargo, no tengo un ejemplo (natural) para el caso tres! Entonces mi pregunta es: ¿Cuáles son los ejemplos para el caso tres de recurrencias / problemas de programación dinámica?

Hay muchos otros ejemplos de algoritmos de programación dinámica que no se ajustan a su patrón en absoluto.

• El problema de subsecuencia creciente más largo requiere solo una tabla unidimensional.

• Existen varios algoritmos de programación dinámica natural cuyas tablas requieren tres o incluso más dimensiones. Por ejemplo: Encuentre el rectángulo blanco de área máxima en un mapa de bits. El algoritmo de programación dinámica natural utiliza una tabla tridimensional.

• Pero lo más importante, la programación dinámica no se trata de tablas ; Se trata de desenrollar la recursión. Hay muchos algoritmos de programación dinámica natural en los que la estructura de datos utilizada para almacenar resultados intermedios no es una matriz, porque la recurrencia que se desenrolla no está en un rango de enteros. Dos ejemplos fáciles son encontrar el mayor conjunto independiente de vértices en un árbol y encontrar el subárbol común más grande de dos árboles. Un ejemplo más complejo es el algoritmo de aproximación para el problema del vendedor ambulante euclidiano de Arora y Mitchell.$(1+\epsilon)$

Calcular la función de Ackermann está en este espíritu. Para calcular necesita saber y para algunas grandes . O la segunda coordenada disminuye, o la primera disminuye, y la segunda potencialmente aumenta.A ( m , n - 1 ) A ( m - 1 , k ) $A(m,n)$$A(m,n-1)$$A(m-1,k)$$k$

Idealmente, esto no se ajusta a los requisitos, ya que el número de columnas es infinito, y el cálculo generalmente se realiza de arriba a abajo con la memorización, pero creo que vale la pena mencionarlo.

Esto no encaja exactamente en el caso 3, pero no sé si alguno de sus casos captura un problema muy común utilizado para enseñar programación dinámica: Multiplicación de cadena de matriz . Para resolver este problema, (y muchos otros, este es solo el canónico) llenamos la matriz diagonal por diagonal en lugar de fila por fila.

Entonces la regla es algo como esto:

Sé que es un ejemplo tonto, pero creo que un problema iterativo simple como

Encuentra la suma de los números en una matriz cuadrada

Podría calificar. El tradicional "para cada fila para cada columna" se parece a su caso 3.

Este no es exactamente el espacio de búsqueda que está buscando, pero tengo una idea de la parte superior de mi cabeza que podría ser de ayuda.

Problema:

Dada una matriz , digamos, con enteros distintos en los que las entradas de cada fila (de izquierda a derecha) y cada columna (de arriba a abajo) se ordenan en orden creciente y las entradas en cada columna están en orden creciente . Dé un algoritmo eficiente para encontrar la posición de un entero en (o digamos que el entero no está presente en la matriz).M x $n × n$$M$$x$$M$

Responder

Esto se puede resolver de la siguiente manera recursiva:

Tenemos una matriz n × n. Deje . Ahora compare con . Si podemos descartar cualquier elemento para y , es decir, el espacio de búsqueda se reduce en . De manera similar, cuando , el espacio de búsqueda se reduce en . Entonces, después de la primera iteración, el tamaño del espacio de búsqueda se convierte en . Puede hacer esto de manera recursiva de la siguiente manera: hacemos 3 comparaciones:xmk,kx<mk,kmi,jk≤i≤nk≤j≤n1/4x>mk,k1/4$k = \lceil{\frac{1+n}{2}}\rceil$$x$$m_{k,k}$$x<m_{k,k}$$m_{i,j}$$k\leq i\leq n$$k\leq j\leq n$$1/4$$x>m_{k,k}$$1/4$x($\frac{3}{4} n^2$$x$con el elemento central en cada uno de los tres cuadrantes restantes, y el tamaño del espacio de búsqueda restante se convierte en y así sucesivamente.$\left(\frac{3}{4}\right)^3 n^2$