Lo que se sabe sobre la complejidad del siguiente problema:
- Dado: números racionales .
- Salida: enteros .
- Objetivo: minimizar donde
Es decir, nos gustaría redondear los números racionales a enteros para minimizar la suma de errores en distancias por pares. Para cada par nos gustaría tener la distancia redondeada más cerca posible de la distancia verdadera .y j - y i x j - x i
Motivación: un aburrido viaje en metro y un póster que muestra las "ubicaciones" de las estaciones con la resolución de un minuto de tiempo de viaje. Aquí estamos minimizando el error que cometen las personas si usan el póster para buscar el tiempo de viaje entre las estaciones y , promediando sobre todos los pares .j i < j
Por ejemplo, aquí podemos leer las siguientes aproximaciones de las distancias por pares entre las cuatro estaciones (usando A, B, C, D por brevedad):
- A – B ≈ 1 minuto, B – C ≈ 2 minutos, C – D ≈ 2 minutos
- A – C ≈ 3 minutos, B – D ≈ 4 minutos
- A – D ≈ 5 minutos
¿Es esta la mejor aproximación posible? Si conociera los tiempos reales de viaje, ¿podría encontrar una mejor solución?
Al principio, esto sonaba como un simple ejercicio de programación dinámica, pero ahora parece que se requiere una cierta cantidad de pensamiento real.
¿Alguien reconoce este problema? ¿O ves un algoritmo inteligente para resolverlo?
Editar: Hay algunas variantes naturales de la pregunta que se han mencionado en los comentarios; vamos a darles algunos nombres:
versión de piso / techo : se requiere que para todo .i
versión entera : es suficiente que para todo . i
versión monotónica : se requiere que .
versión no monotónica : podemos tener para . i < j
La pregunta original considera la versión entera monotónica, pero las respuestas relacionadas con cualquiera de estas versiones son bienvenidas.
fuente
Respuestas:
OKAY. El algoritmo DP parece ser innecesariamente complicado. Después de leer los comentarios, creo que esto podría resolver la versión monotónica del problema (pero no he verificado todos los detalles).
Primero, suponga que cada , donde ⌊ x i ⌋ es la parte integral, { x i } es la parte fraccionaria. Supongamos que x i se redondea a ⌊ x i ⌋ + v i , donde v i es un número entero no negativo (por supuesto, en general v i puede ser negativo, pero siempre podemos cambiar para que v i sea 0).xi=⌊xi⌋+{xi} ⌊xi⌋ {xi} xi ⌊xi⌋+vi vi vi vi
Ahora, considere el costo de un par , x j al hacer este redondeo. El costo debe serxi xj
La expresión es complicada debido a los valores absolutos. Sin embargo, tenga en cuenta que tenemos monotonicidad, por lo que las cosas dentro de los dos valores absolutos internos deben tener el mismo signo. Como tenemos un valor absoluto externo, realmente no importa cuál sea ese signo, la expresión simplemente se simplifica a
De ahora en adelante no asumimos que la solución es monotónica, sino que cambiamos el objetivo de minimizar la suma del término anterior para todos los pares. Si la solución a este problema resulta ser monótona, entonces, por supuesto, también es la solución óptima para la versión monotónica. (Piense en esto como: el problema original tiene una penalización infinita cuando la solución no es monotónica, el nuevo problema tiene una penalización menor, si una solución monotónica gana incluso en la nueva versión, debe ser la solución a la versión monotónica)
Ahora nos gustaría probar, si , en la solución óptima debemos tener v i ≥ v j .{xi}>{xj} vi≥vj
Suponga que esto no es cierto, que tenemos un par pero v i < v j . Mostraremos que si intercambiamos v i v j la solución mejora estrictamente.{xi}>{xj} vi<vj vi vj
Primero comparamos el término entre y j , aquí está realmente claro que el intercambio es estrictamente mejor porque en la versión sin intercambio, v i - v j y { x j } - { x i } tiene el mismo signo, el absoluto El valor será la suma de los dos valores absolutos.i j vi−vj {xj}−{xi}
Ahora para cualquier , comparamos la suma de pares ( i , k ) y ( j , k ) . Es decir, tenemos que comparark (i,k) (j,k)
y | v j - v k - ( { x i } - { x k } ) | + ||vi−vk−({xi}−{xk})|+|vj−vk−({xj}−{xk})| .|vj−vk−({xi}−{xk})|+|vi−vk−({xj}−{xk})|
Uso , B , C , D para denotar los cuatro términos en el interior del valor absoluto, está claro que A + B = C + D . También está claro que | A - B | ≥ | C - D | . Por convexidad del valor absoluto, sabemos | A | + | B | ≥ | C | + | D | . Toma la suma sobre todo x kA B C D A+B=C+D |A−B|≥|C−D| |A|+|B|≥|C|+|D| xk Sabemos que el intercambio solo puede ser mejor.
Tenga en cuenta que ahora ya tenemos una solución para la versión monotónica de piso / techo: debe haber un umbral, cuando es más grande siempre redondeado, cuando es más pequeño siempre redondeado hacia abajo, cuando es igual redondear hacia arriba abajo, mientras que la calidad de la solución solo depende del número. Enumeramos todas estas soluciones y elegimos la que tiene la función objetivo más pequeña. (Todas estas soluciones son necesariamente monótonas).{xi}
Finalmente, nos gustaría ir a la versión entera monotónica del problema. De hecho, podemos demostrar que la solución óptima es la misma que la versión monotónica de piso / techo.
Ahora demostraremos que el promedio de en el grupo es al menos el promedio de en el grupo más . Si esto no es cierto, simplemente deje para todos , el cálculo nuevamente muestra que la función objetivo mejora.k + 1 { x i } k 1 / 2 v i = v i - 1 v i > k{xi} k+1 {xi} k 1/2 vi=vi−1 vi>k
Dado que el promedio de está en el rango , realmente hay a lo sumo dos grupos, que corresponde a la versión de piso / techo.[ 0 , 1 ){xi} [0,1)
fuente
Solo un comentario extendido ... (quizás trivial y / o incorrecto :)
Si y es el mínimo común múltiplo de s, entonces podemos deshacernos de los racionales: . M b i x ′ i = M ∗ x ixi=ai/bi M bi x′i=M∗xi
Si (piso, restricción de techo) entonces podemos usar variables binarias para expresar usando su distancia de ( o ):v i y ′ i x ′yi∈{⌈xi⌉,⌊xi⌋} vi y′i Li=x ′ i -M∗⌊xi⌋Ri=x ′ i -M∗⌈xi⌉x′i Li=x′i−M∗⌊xi⌋ Ri=x′i−M∗⌈xi⌉
Y el problema original debería ser (?!?) Equivalente a encontrar el que minimiza:vi
convi∈{0,1},Di∈Z
fuente
Otro comentario extendido ... Podría estar equivocado.
También estoy considerando el caso de las restricciones de piso / techo, y estoy tratando de resolverlo usando programación dinámica (no puedo, pero tal vez funciona cuando el divisor común es pequeño).
Sea la parte fraccionaria de , consideramos las cosas desde la más pequeña hasta la más grande. Supongamos que el más grande es , y debido a que estamos haciendo programación dinámica, ya sabemos "algo" (explicaré qué es este algo) sobre la solución óptima para todo lo demás, excepto .{xi} xi {xi} {xk} xk
Ahora considere la diferencia en la función objetivo cuando redondeamos hacia arriba o hacia abajo. Si originalmente algo de se redondea, entonces la diferencia es simplemente 1 (realmente no se ha verificado con mucho cuidado, pero parece que este es el caso, es realmente importante que no importa si está a la izquierda o derecha de , la diferencia es siempre lo mismo); si originalmente algo de se redondea hacia abajo, entonces la diferencia es . Entonces: sabemos qué decisión debemos tomar si se conocen las siguientes tres cantidades:xk xi xi xk xi 2{xk}−2{xi}−1
OK, 1 y 2 son esencialmente lo mismo, podemos dejar que f [N, Ndown, Sdown] sea la solución óptima para los primeros N puntos (cuando los puntos se ordenan en orden ascendente de ), el número de abajo redondeada 's es Ndown, y la suma de para los que están abajo es redondeada Sdown. Entonces no es difícil escribir cómo pasar de f [N-1] a f [N].{xi} xi {xi}
El problema es, por supuesto, Sdown puede tener exponencialmente muchos valores. Pero funciona cuando el divisor común es pequeño o podemos redondear todo a un punto de cuadrícula primero y obtener un FPTAS (si el programa dinámico anterior es correcto ...)
fuente