¿Cómo usar un algoritmo codicioso para encontrar la secuencia no decreciente más cercana a la dada?

20

Te dan n enteros todos entre y . Debajo de cada número entero , debe escribir un número entero entre y con el requisito de que los formen una secuencia no decreciente. Defina la desviación de dicha secuencia como . Diseñe un algoritmo que encuentre las b_i 's con la desviación mínima en tiempo de ejecución O (n \ sqrt [4] {l}) . 0a1,,an0laibi0lbimax(|a1b1|,,|anbn|)biO(nl4)

Sinceramente, no tengo ni idea de cómo comenzar a resolver esta pregunta. A mí me parece una pregunta de programación dinámica, pero el profesor dijo que esto debería resolverse utilizando un algoritmo codicioso. Sería muy apreciado si alguien me puede señalar en la dirección correcta dando una pequeña pista.

Aden Dong
fuente

Respuestas:

9

Comencemos con la siguiente observación:

Deje que max denote el máximo de la secuencia a1,...,an , y deje que min denote su mínimo. Si a1=max , entonces elegir b1=b2=...=bn=(max+min)/2 es óptimo.

¿Por qué es este el caso? Bueno, dado que la secuencia comienza con el máximo, elegimos grande y sufrimos una gran desviación del mínimo de la secuencia (ya que cualquier posterior debe ser mayor o igual a ), o elegimos pequeño y sufrimos desviación al . El promedio minimiza la desviación máxima.b1bib1b1max

Ahora podemos tratar de generalizar esta observación para usarla en secuencias generales . Por ejemplo, podemos dividir cualquier secuencia en subsecuencias, de modo que cada una comience con el máximo de la subsecuencia respectiva.a1,...,an

Ejemplo: se divide en , y .(2,6,4,1,5,2,8,7,5,1)(2)(6,4,1,5,2)(8,7,5,1)

Dada esta partición, ahora podemos resolver cada una de estas subsecuencias por separado, y obtener una asignación de los 's, que sin embargo podrían violar la condición no decreciente. Esto se puede solucionar sin perder la optimización.bi

Observe que la última subsecuencia siempre contiene el máximo de toda la secuencia (de lo contrario, habría otra subsecuencia después de ella). Sean los valores que asignamos a las subsecuencias. Ahora, para lograr una no disminución en , comenzamos desde atrás en y hacia el frente. Si es mayor que , simplemente establecemos . Si es más pequeño, lo guardamos. Luego, procedemos a comparar con y así sucesivamente. Tenga en cuenta que reducir al valor demaxw1,w2,...,wkkw1,...,wkwkwk1wkwk1:=wkwk2wk1wiwi+1nunca aumenta la desviación, ya que el valor máximo en la subsecuencia asignada con es siempre menor que el máximo en la subsecuencia asignada con .wiwi+1

Este algoritmo debería ser correcto, creo. Con respecto al tiempo de ejecución, el paso clave es calcular los máximos crecientes para las subsecuencias, que es posible en ? No sabe dónde contribuye.O(n)l

Syzygy
fuente
2

Voy a pensar en voz alta aquí solo trabajando en las pistas que me has dado. Vayamos a la pista original de decir que es lo que debes probar primero. Puedo pensar en un algoritmo codicioso que tiene ese tiempo.O(nl)

La parte de la complejidad del tiempo significa que puede mantener una lista del recuento de cada ocurrencia de cada valor . Eso es solo crear un conjunto que rastrea el recuento de cada en el conjunto. Puede crear la lista de inicialización escaneando la secuencia de entrada una vez.l0..lCount=C0,,Cll

Puede escanear esta lista en para obtener el valor máximo y mínimo. Si tuviera que llenar la lista completa de con este punto medio, su varianza sería simplemente la diferencia de este valor y el máximo / mínimo. Este es básicamente el peor de los casos, vamos a llamarlo .O(l)bbw

Así que trabaje hasta desde la izquierda. Ambos pueden descartar este elemento de y obtener el mínimo / máximo de en . Ahora podemos ser codiciosos. No elegimos ya que eso obliga a la lista completa restante hacia arriba (para cumplir con el requisito no decreciente) y, por lo tanto, aumenta la varianza. El valor mínimo que podemos elegir es . Si está en el rango aceptable, lo seleccionamos, si está por debajo del rango, use el mínimo. Esto minimiza la varianza en dadas las restricciones conocidas.biCountb[i+1]b[n]O(l)bi>bwb[i1]aibi

Esto es solo una idea, tal vez tengo suerte y te señala en la dirección correcta. Es posible que este algoritmo no funcione (lo hace para mis pocas pruebas simples), pero coincide con las sugerencias dadas, por lo que quizás sea útil. Si es correcto, es fácil ver que la parte se puede soltar con seguridad a , más aún, no estoy seguro.O(l)O(logl)

edA-qa mort-ora-y
fuente
2

Aquí está la solución del profesor, que él llama "reducción": para cada de a , intente construir una solución si sabemos que la desviación es menor o igual que . La primera para la que se puede encontrar una solución es la desviación mínima. Podemos encontrar una solución dada la desviación en el tiempo . Entonces el tiempo de ejecución es . Luego, en lugar de usar la búsqueda lineal, podemos usar la búsqueda binaria para determinar la desviación más pequeña para la cual es posible una solución. Esto reduce el tiempo de ejecución a , que satisface el requisito de .i0liiO(n)O(nl)O(nlogl)O(nl4)

Aden Dong
fuente
44
Entonces el fue un truco ... Pero estoy más intrigado por el "Podemos encontrar una solución dada la desviación en el tiempo O (n)" ... ¿cómo es que no es el parte interesante? O(nl4)
jmad
@jmad Dado , para cada , tome como el valor más bajo que es al menos tan grande como todos los anteriores , y que no es más que lejos de . Si no podemos encontrar ese valor, ¿qué significa? Significa que un anterior es más grande que mayor que . Entonces, un anterior es más de más grande que . Entonces ese valor de no era posible. Si supera los valores de sin atascarse así, ha encontrado una solución paraijbjbkiajbtiajat2iajinisin retroceso, en el tiempo . O(n)
jwg
O (n log l) habría sido una fuerte pista de que necesita hacer una búsqueda binaria en el rango de 0 a l.
gnasher729
0

Creo que esto debería ser factible en O (n).

Tome el problema similar: dado , 1 ≤ i ≤ n, y d ≥ 0, encuentre en orden no descendente tal que para todo i, o demuestre que no es posible. Esto se puede hacer en O (n), y utilizando la búsqueda binaria, el problema original se resuelve en O (n log l).b i | a i - b i | daibi|aibi|d

Ahora si hay i ≤ j tal que a_i - a_j> 2d, entonces no hay solución (porque ).biaid,bjaj+d<ai2d+d=aidbi

Pero si a_i - a_j ≤ 2d para todo i ≤ j, entonces creo que siempre se encontrará una solución. Entonces, todo lo que tenemos que hacer es encontrar m = max (a_i - a_j) para todo i ≤ j, y elegir d = floor ((m + 1) / 2). Ese máximo se puede encontrar en O (n).

gnasher729
fuente
¡Idea intrigante! Puedo creer que algo como esto podría funcionar, pero parece que hay un gran vacío al final de su respuesta y me está costando completar los detalles. ¿Tiene una prueba de que si para todo entonces siempre existe una solución? Más importante aún, ¿cómo lo encontramos? La pregunta original dice que debemos encontrar los 's. Incluso si suponemos que existe una solución, tengo dificultades para ver cómo encontrar las correspondientes . Puedes profundizar sobre eso? i j b i b iaiaj2dijbibi
DW