Clasificar matriz en orden ascendente mientras se minimiza el "costo"

Question

Estoy tomando comp 2210 (Estructuras de datos) el próximo semestre y he estado haciendo la tarea para el semestre de verano que se publica en línea. Hasta ahora, no he tenido problemas para hacer las asignaciones. Eche un vistazo a la asignación 4 a continuación y vea si puede darme una pista sobre cómo abordarla. Por favor, no proporcione un algoritmo completo, solo un enfoque. ¡Gracias!

Un "tipo calculado" es un algoritmo en el cual una secuencia de valores debe organizarse en orden ascendente. El tipo es llevado a cabo intercambiando la posición de dos valores uno por uno hasta que la secuencia esté en el orden correcto. Cada intercambio incurre en un costo, que se calcula como la suma de los dos valores involucrados en el intercambio. El costo total de del género es la suma del costo de los intercambios.

Por ejemplo, supongamos que la secuencia de inicio fuera {3, 2, 1}. Una posible serie de intercambios es

Interchange 1: {3, 1, 2} interchange cost = 0 
Interchange 2: {1, 3, 2} interchange cost = 4 
Interchange 3: {1, 2, 3} interchange cost = 5, 
given a total cost of 9 

Usted debe escribir un programa que determina el costo mínimo para organizar una secuencia específica de números.

Editar: El profesor no permite la fuerza bruta.

Answer 1

Si quiere sorprender a su profesor, puede usar Simulated Annealing. Por otra parte, si logras eso, probablemente puedas omitir algunos cursos :). Tenga en cuenta que este algoritmo solo dará una respuesta aproximada.

De lo contrario: intente con un algoritmo Backtracking o Branch and Bound. Ambos encontrarán la respuesta óptima.

Answer 2

¿Has aprendido árboles? Podría crear un árbol con todos los cambios posibles que conduzcan al resultado deseado. El truco, por supuesto, es evitar crear todo el árbol, particularmente cuando una parte de él obviamente no es la mejor solución, ¿verdad?

Answer 3

Pruebe diferentes algoritmos de clasificación en los mismos datos de entrada e imprima el mínimo.

Answer 4

Creo que el enfoque adecuado es pensar detenidamente sobre qué propiedades definitorias tiene un tipo mínimo de "costo". Luego calcula el costo simulando este tipo ideal. El elemento clave aquí es que no tiene que implementar un algoritmo de clasificación de costo mínimo general.

Por ejemplo, digamos que la propiedad de definición de un tipo de costo mínimo es que cada intercambio pone al menos uno de los elementos intercambiados en su posición ordenada (no sé si esto es cierto). A cada tipo de intercambio le encantaría poder tener esta propiedad, pero no es fácil (¿es posible?) En el caso general. Sin embargo, puede crear fácilmente un programa que toma una matriz no ordenada, toma la versión ordenada (que a su vez puede ser generada por un algoritmo no óptimo) y luego usar esta información decide el costo mínimo para lograr la matriz ordenada de la matriz no ordenada.

Answer 5

¿A qué te refieres con "fuerza bruta"? ¿Quiere decir "probar todas las combinaciones posibles y seleccionar la más barata?" Solo revisando.

Creo que "sucursal y encuadernado" es lo que está buscando - consulte cualquier fuente en los algoritmos. Es "como" la fuerza bruta, excepto cuando intentas una secuencia de movimientos, tan pronto como esa secuencia de movimientos es menos óptima que cualquier otra secuencia de movimientos probados hasta el momento, puedes abandonar la secuencia que te llevó a ese punto: el costo. Este es un sabor del "retroceso" mencionado anteriormente.

Mi idioma preferido para hacer esto sería Prolog pero soy raro.

Simulated Annealing es un algoritmo PROBABLISTIC: si el espacio de solución tiene mínimos locales, entonces puede quedar atrapado en uno y obtener lo que cree que es la respuesta correcta pero no lo es. Hay formas de evitarlo y se puede encontrar toda la literatura, pero no estoy de acuerdo en que sea la herramienta que desee.

Puede intentar los algoritmos genéticos relacionados también si esa es la forma en que desea ir.

Answer 6

Descripción

Creo que la forma más barata de hacer esto es el elemento de intercambio fuera de lugar más barato con el elemento que pertenece en su lugar. Creo que esto reduce el costo al mover las cosas más caras solo una vez. Si hay n-elementos que están fuera de lugar, habrá como máximo n-1 swaps para ponerlos en su lugar, a un costo de n-1 * costo de menos artículo + costo de todos los demás fuera de lugar.

Si el elemento globalmente más barato no se extravía y la distribución entre esta más barata y la más barata es suficiente, puede ser más barato cambiar la más barata en el lugar correcto por la más barata. El costo es entonces n-1 * más económico + el costo de todos fuera de lugar + el costo del más barato fuera de lugar.

Ejemplo

Para [4,1,2,3], este intercambio de algoritmo (1,2) para producir:

[4,2,1,3] 

y luego intercambia (3,1) para producir :

[4,2,3,1] 

y luego intercambia (4,1) para producir:

[1,2,3,4] 

Observe que cada elemento extraviado en [2,3,4] se mueve una sola vez y se intercambia con el artículo de menor costo.

Código

Lamentablemente: "Por favor, no proporcionar un algoritmo completo, sólo una aproximación." Eliminó mi código.

Answer 7

En un esfuerzo por hacerlo funcionar, esto puede no tener mucho sentido.

Determine todos los movimientos posibles y el costo de cada movimiento y almacénelos de alguna manera, realice el movimiento menos costoso, luego determine los movimientos que se pueden realizar desde esta variación, almacenándolos con el resto de sus movimientos almacenados, realice el menos costoso, etc. hasta que la matriz esté ordenada.

Me encanta resolver cosas como esta.

Answer 8

Este problema también se conoce como el problema Silly Sort en algunos concursos de ACM. Eche un vistazo a this solution usando Dividir & Conquer.