Redondeo para minimizar la suma de errores en distancias por pares

25

Lo que se sabe sobre la complejidad del siguiente problema:

  • Dado: números racionales .x1<x2<<xn
  • Salida: enteros .y1y2yn
  • Objetivo: minimizar donde
    1i<jne(i,j),
    e(i,j)=|(yjyi)(xjxi)|.

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 ii,jyjyixjxi


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 < jiji<j

mapa de ruta

(fuente)

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 .iyi{xi,xi}i

  • versión entera : es suficiente que para todo . iyiZi

  • versión monotónica : se requiere que .y1y2yn

  • versión no monotónica : podemos tener para . i < jyi>yji<j

La pregunta original considera la versión entera monotónica, pero las respuestas relacionadas con cualquiera de estas versiones son bienvenidas.

Jukka Suomela
fuente
¿El DP funciona para el caso cuando solo le interesan las mediciones adyacentes?
Suresh Venkat
1
@SureshVenkat: En realidad, en ese caso el problema se vuelve muy simple: simplemente selecciona la mejor distancia integral para cada . Es decir, puede minimizar cada independiente. i e ( i - 1 , i )yiyi1ie(i1,i)
Jukka Suomela
44
Este informe de Estie Arkin parece relacionado: ams.sunysb.edu/~estie/papers/beautification.pdf Está comprobado que minimizar el número de distancias entre puntos distintas en la salida es NP-duro. Esta no es la suma total de los cambios, como en estas preguntas, pero tal vez los dispositivos de dureza en el informe podrían sugerir una prueba de dureza para este problema.
val
2
Tengo la sensación de que este problema debería resolverse con técnicas bien conocidas. Veamos si la recompensa es suficiente para motivar a las personas a resolver esto. :)
Jukka Suomela
1
@vzn: Estoy interesado en la complejidad computacional de este problema. Si puede demostrar que existe un enfoque de búsqueda local en tiempo polinómico que garantiza encontrar el óptimo global, la recompensa es suya.
Jukka Suomela

Respuestas:

9

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}xixi+vivivivi

Ahora, considere el costo de un par , x j al hacer este redondeo. El costo debe serxixj

||vivj+xixj||{xi}{xj}+xixj||

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

|vivj({xi}{xj})|

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 iv j .{xi}>{xj}vivj

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<vjvi 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.ijvivj{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 } ) | + ||vivk({xi}{xk})|+|vjvk({xj}{xk})|.|vjvk({xi}{xk})|+|vivk({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 kABCDA+B=C+D|AB||CD||A|+|B||C|+|D|xkSabemos 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.

vixivik v i > k v i = v i - 1 | { x i } - { x j } | < 10,1,2,...,max{vi}kvi>kvi=vi1|{xi}{xj}|<1

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}k1/2vi=vi1vi>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)

Rong Ge
fuente
1

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/biMbixi=Mxi

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}viyi Li=xi -MxiRi=xi -MxixiLi=xiMxiRi=xiMxi

yi=xi+Livi+Ri(1vi)=xi+(LiRi)vi+Ri=xi+Divi+Ri

Y el problema original debería ser (?!?) Equivalente a encontrar el que minimiza:vi

1i<jn|DiviDjvj|

convi{0,1},DiZ

Marzio De Biasi
fuente
expandiendo su última suma utilizando el error fn idea anterior, ¿podría mostrarse que el óptimo es en realidad la elección donde cada variable binaria piso / techo está más cerca de ? así que solo queda el caso de cómo redondear para en la forma donde es un número entero. x n x n m n + 1e(i,j)xnxn mmn+12m
vzn
1
@vzn: Creo que este es un contraejemplo. Si redondeamos usando el criterio de redondeo obtenemos que tiene un error de , pero tiene un error de (el resultado es el mismo si eliminamos los racionales que se multiplican por el MCM). (0,1.4,8.7) ( 0 , 1 , 9 ) 1.4 ( 0 , 2 , 9 ) 1.2xi(0,1,9)1.4(0,2,9)1.2
Marzio De Biasi
ok sin embargo nueva idea. considere nuevamente. expandir el resumen. se reducirá a muchos términos con y también . pero este último es igual a ! por lo tanto, se reduce a un problema en forma de minimizar donde es un vector de fila 0/1 y es un vector de columna constante . ¿cierto? entonces eso es trivial, y simplemente seleccione la tal que sea 1 si el elemento correspondiente en es negativo y 0 si es positivo ... QED? v i v 2 ie(i,j)vivi2 X D X D X DviXDXDXD
vzn
1
@vzn: si usa el para eliminar la función de valor absoluto, obtendrá términos como ; ¿Cómo los manejas en la minimización? ((yiyj)(xixj))22DiDjvivj
Marzio De Biasi
¡Uy! respondiste antes de que tuviera la oportunidad de eliminar ese comentario después de darme cuenta de que ... de todos modos, ¿parece reducirse a algún problema de optimización de matriz casi lineal? también con un término donde es un vector de columna ...? VVTV
vzn
1

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:xkxixixkxi2{xk}2{xi}1

  1. cuantas cosas se redondean
  2. cuantas cosas se redondean
  3. ¿ es la suma de entre las redondeadas hacia abajo?{xi}xi

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 ...)

Rong Ge
fuente
Acabo de notar el comentario de @Marzio De Biasi. Es mucho más fácil pensar en esta programación dinámica usando esa función objetivo. Como esencialmente estamos ordenando de acuerdo con , cuando tratamos de considerar el último, todo el valor absoluto desaparece. El costo adicional es o . DiDivi(N1)DkDivi
Rong Ge
OK 's no tiene que ser positivo. Pero eso también se puede manejar. Solo necesitamos diferenciar entrey . Ndown es el número de anteriores que son iguales a 0, Nup es el número de anteriores iguales a 1.Di|Divi|Ndown|Dk|+NupDkDivivjvj
Rong Ge
Esto parece prometedor, pero creo que hay algunas dificultades adicionales si los valores de entrada están demasiado cerca el uno del otro. Considere, por ejemplo, y . Ahora, si pudiéramos tener redondeado hacia arriba y redondeado hacia abajo, ya no tendríamos la buena propiedad de que el error cambia exactamente 1 dependiendo de si está redondeado hacia arriba o hacia abajo. Por otro lado, si prohibimos un redondeo que cambie el orden de los puntos (como lo hice en la pregunta original), entonces parece que necesitamos hacer un seguimiento de los posibles redondeos que todavía están disponibles en el programa dinámico; ¿Podemos hacer eso? xi=1.1xk=1.9xixkxk
Jukka Suomela
1
@Jukka Suomela, después de ver tu comentario, me di cuenta de que nunca deberíamos permitir que algo con más grande se hacia abajo, mientras que algo con más pequeño se . Esto se puede probar si examina todos los casos. Entonces la respuesta al problema (con restricciones de redondeo) es clara: debe haber un umbral, por encima del umbral que debe redondear, por debajo debe redondear hacia abajo, en el umbral tal vez algunos deberían redondearse hacia arriba y otros hacia abajo, pero solo la calidad Depende del número. Estas soluciones se pueden enumerar fácilmente. {xi}{xi}
Rong Ge
1
Al examinar todos los casos que quiero decir, supongamos que , piense en otro en una de las tres regiones divididas por y , y se redondea hacia arriba o hacia abajo. En los 6 casos, redondear hacia abajo y hacia arriba nunca es peor que redondear hacia abajo y hacia arriba. { x k } { x i } { x j } { x k } x i x j x j x i{xi}<{xj}{xk}{xi}{xj}{xk}xixjxjxi
Rong Ge