Mi configuración es algo como esto: tengo una secuencia de conjuntos de enteros , con relativamente pequeño - del orden de cuatro o cinco artículos para todos . Quiero elegir una secuencia con cada tal que la variación total (ya sea o es decir o ) está minimizado. Si bien parece ser la elección para cada 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?? ') 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í.
fuente
Respuestas:
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 elCi tienen 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 :
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 .minmj=1Cost(n,j) O(nm)
fuente
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 .n G=(⋃ni=1Vi,E) v∈Vi x∈Ci u∈Vi,v∈Vi+1 (u,v) ℓ1 ℓ2
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í ).s V1 t Vn G O(V+E)
fuente