Minimizando la variación total de una secuencia de elecciones discretas

8

Mi configuración es algo como esto: tengo una secuencia de conjuntos de enteros Ci(1in), con |Ci| relativamente pequeño - del orden de cuatro o cinco artículos para todos i. Quiero elegir una secuenciaxi(1in) con cada xiCi tal que la variación total (ya sea 1 o 2es decir i=1n1|xixi+1| o i=1n1(xixi+1)2) está minimizado. Si bien parece ser la elección para cadaxi es 'local', el problema es que las elecciones pueden propagarse y tener efectos no locales, por lo que el problema parece inherentemente de naturaleza global.

Mi principal preocupación es un algoritmo práctico para el problema; en este momento estoy usando métodos de recocido basados ​​en mutaciones de subsecuencias cortas, y aunque deberían estar bien, parece que debería poder hacerlo mejor. Pero también estoy interesado en la complejidad abstracta: mi presentimiento sería que la versión de consulta estándar ('¿hay una solución de variación total?k? ') sería NP-completo a través de una reducción de algún problema de restricción como 3-SAT, pero no puedo ver la reducción. Cualquier sugerencia para un estudio anterior sería bienvenida: parece un problema tan natural que no puedo creer que no se haya analizado antes, pero mis búsquedas hasta ahora no han resultado ser algo así.

Steven Stadnicki
fuente
¡Buena pregunta! Solo una pregunta aclaratoria: la duración dexi es n, pero debes elegir algún elemento de cada Ci? ¿O está bien tener algún número de conjuntos de los que no elijas?
Juho
@mrm Debe haber un elemento de cada Ci - la xs se indexan directamente desde 1n así como el Cs son.
Steven Stadnicki

Respuestas:

4

Aquí hay un programa dinámico. Asumir queCi={Ci1,,Cim} para todos i[n]por el bien de la claridad; lo siguiente se puede adaptar para trabajar si elCitienen diferentes cardinalidades. DejarCost(i,j) ser el costo mínimo de una secuencia durante el primer i conjuntos, terminando con Cij. La siguiente recursividad describeCost:

Cost(1,j)=0,1jmCost(i,j)=mink=1m(Cost(i1,k)+|C(i1)kCij|) ,2in,1jm.

El costo mínimo general es ; La secuencia real de opciones se puede determinar examinando los argumentos en el camino. El tiempo de ejecución es .minj=1mCost(n,j)O(nm)

cuenta
fuente
Traté de mejorar la claridad de su respuesta tanto en formato como en presentación; Por favor, compruebe que no me equivoqué Sería bueno si incluyeras un argumento de por qué lo que propones es correcto.
Raphael
Teniendo en cuenta la respuesta de Nicholas , esto es similar al algoritmo Bellman-Ford, adaptado al problema en cuestión.
Raphael
Ambas respuestas son realmente excelentes (y como señala Raphael, muy similares), pero aunque me gusta la amplia aplicabilidad de la otra, realmente prefiero esta para su aplicación directa a mi pregunta particular. ¡Gracias!
Steven Stadnicki
4

Parece que esto se puede resolver simplemente calculando una ruta más corta en un gráfico acíclico dirigido. El razonamiento es que su función objetivo minimiza la distancia total entre los "vecinos" seleccionados en sus conjuntos .C={C1,,Cn}

Construya un gráfico de etapas donde cada corresponde a un elemento único . Para cada , agregue un borde dirigido costo sea la o .nG=(i=1nVi,E)vVixCiuVi,vVi+1(u,v)12

Ahora agregue un vértice de origen con bordes de costo 0 a y un vértice de sumidero con bordes de costo 0 de . Dado que es un DAG y ambas funciones de distancia obligan a los costos de borde a ser no negativos, puede calcular la ruta más corta en con ordenación topológica y programación dinámica (similar a la descripción aquí ).sV1tVnGO(V+E)

Nicholas Mancuso
fuente