Ordenando una lista de números con costo modificado

Question

Primero, este fue uno de los cuatro problemas que tuvimos que resolver en un proyecto el año pasado y no pude encontrar un algoritmo adecuado, así que manejamos en una solución de fuerza bruta.

Problema: Los números están en una lista que no está ordenada y admite solo un tipo de operación. La operación se define de la siguiente manera:

Dada una posición iy una posición j, la operación mueve el número en la posición i a la posición j sin alterar el orden relativo de los otros números. Si i> j, las posiciones de los números entre las posiciones j e i - 1 aumentan en 1; de lo contrario, si i < j, las posiciones de los números entre las posiciones i + 1 yj disminuyen en 1. Esta operación requiere pasos para encontrar un número para mover y j pasos para ubicar la posición a la que desea moverlo. Entonces, el número de pasos requeridos para mover una cantidad de posición i a la posición j es i + j.

Tenemos que diseñar un algoritmo que, dada una lista de números, determine la secuencia de movimientos óptima (en términos de costo) para reorganizar la secuencia.

intentos: parte de nuestra investigación fue de alrededor de NP-completitud, que lo convierten en un problema de decisión y tratar de encontrar una transformación adecuada para cualquiera de los problemas mencionados en el libro Garey y Johnson: Informática y Intratabilidad sin resultados . Tampoco hay referencia directa (desde nuestro punto de vista) a este tipo de variación en el libro de Donald E. Knuth: The art of Computer Programing, vol. 3 Clasificación y búsqueda. También analizamos algoritmos para ordenar las listas vinculadas, pero ninguno de ellos da una buena idea para encontrar una secuencia de movimientos óptima.

Tenga en cuenta que la idea no es encontrar un algoritmo que ordene la secuencia, sino uno que me diga la secuencia óptima de movimientos en términos de costo que organiza la secuencia, puede hacer una copia y ordenarla para analizar la final posición de los elementos, si lo desea, de hecho, podemos suponer que la lista contiene los números del 1 al n, así que sabemos dónde queremos poner cada número, solo nos preocupamos por minimizar el costo total de los pasos.

Probamos varios enfoques codiciosos pero todos ellos fallaron, dividimos y conquistamos los algoritmos de clasificación que no se pueden usar porque intercambian partes de la lista sin costo y nuestros enfoques dinámicos de programación tuvieron que considerar muchos casos.

El algoritmo recursivo de fuerza bruta toma todas las combinaciones posibles de movimientos de i a j y de nuevo todos los momentos posibles del resto del elemento, al final devuelve la secuencia con un menor costo total que ordenó la lista, como se puede imaginar, el costo de este algoritmo es brutal y lo hace impracticable para más de 8 elementos.

Nuestras observaciones:

• n movimientos no es necesariamente más barato que n + 1 movimientos (a diferencia de permutas en matrices que son O (1)).

• Básicamente, hay dos formas de mover un elemento de la posición i a j: uno es moverlo directamente y el otro es mover otros elementos alrededor de i de forma que llegue a la posición j.

• Como máximo realiza n-1 movimientos (el elemento no tocado alcanza su posición solo).

• Si es la secuencia óptima de movimientos, entonces no se movió el mismo elemento dos veces.

Answer 1

Este problema se ve como un buen candidato para un approximation algorithm pero que sólo nos daría una respuesta bastante buena. Como quiere la respuesta óptima, esto es lo que haría para mejorar el enfoque de la fuerza bruta.

En lugar de intentar a ciegas todas las permutaciones, utilizaría un enfoque backtracking que mantendría la mejor solución encontrada y podaría cualquier rama que superara el costo de nuestra mejor solución. También agregaría un transposition table para evitar rehacer las búsquedas en los estados que fueron alcanzados por las ramas anteriores usando diferentes permutaciones de movimiento.

También agregaría algunas heurísticas para explorar movimientos que tienen más probabilidades de alcanzar buenos resultados antes de cualquier otro movimiento. Por ejemplo, prefiere movimientos que tienen un costo menor primero. Tendría que experimentar antes de poder decir qué heurística funcionaría mejor, en su caso.

También trataría de encontrar el longest increasing subsequence of numbers en la matriz original. Esto nos dará una secuencia de números que no necesitan moverse, lo que debería reducir considerablemente el número de ramas que necesitamos explorar. Esto también acelera en gran medida las búsquedas en la lista que están casi ordenadas.

Espero que estas mejoras sean capaces de manejar listas que son mucho mayores que 8, pero cuando se trata de listas grandes de números aleatorios, prefiero un algoritmo de aproximación.

---

Por demanda popular (1 persona), esto es lo que haría para resolver esto con un genetic algorithm (el meta-heuristique que estoy más familiarizado).

Primero, comenzaría por calcular la subsecuencia creciente de números más larga (ver arriba). Cada artículo que no es parte de ese conjunto tiene que ser movido. Todo lo que necesitamos saber ahora es en qué orden.

Los genomas utilizados como entrada para el algoritmo genético, es simplemente una matriz en la que cada elemento representa un elemento que se va a mover. El orden en que aparecen los elementos en la matriz representa el orden en el que deben moverse. La función de aptitud sería el cálculo del costo descrito en la pregunta original.

Ahora tenemos todos los elementos necesarios para solucionar el problema en un algoritmo genético estándar. El resto solo está retocando. Montones y montones de ajustes.