algorithm - segunda - estrategia de reemplazo sistemas operativos

Algoritmo óptimo de clasificación de burbujas para una matriz de matrices de números

Question

Corrige enteros positivos n k .

Deje A ser una matriz de longitud n con A[i] una matriz de longitud k donde cada entrada es ni . Por ejemplo, con n=5 k=1 , esto es solo

[ [5] , [4] , [3] , [2] , [1] ]

y para n=5 k=2 , esto es

[ [5,5] , [4,4] , [3,3] , [2,2] , [1,1] ]

El objetivo es clasificar las burbujas de este conjunto de matrices intercambiando números en matrices adyacentes (por ejemplo, cambiar A[i][j1] por A[i+1][j2] ) hasta que cada entrada de A[i] sea i+1 para cada i .

La pregunta es: ¿cuántos swaps son necesarios y qué es un algoritmo óptimo ?

NOTA: hay muchos, muchos mejores algoritmos de clasificación para usar. Sin embargo, para esta pregunta, solo estoy interesado en aplicar una clasificación de burbuja como se describe anteriormente. Solo puedo intercambiar entradas de matrices adyacentes, y solo estoy interesado en el número mínimo de intercambios necesarios. Aprecio todas las sugerencias para otros algoritmos de clasificación, pero este es el problema que intento comprender.

EJEMPLOS:

Para k=1 , esto es bien conocido. El número de swaps es el número de inversión de A considerado como una permutación, por lo que el número mínimo de swaps es el coeficiente binomial (n choose 2) = n(n-1)/2 y esto se puede lograr intercambiando cualquiera de par de orden: A[i] > A[j] . Para el primer ejemplo, aquí hay una clase de burbuja óptima:

[ [5] , [4] , [3] , [2] , [1] ]
[ [4] , [5] , [3] , [2] , [1] ]
[ [4] , [5] , [2] , [3] , [1] ]
[ [4] , [2] , [5] , [3] , [1] ]
[ [4] , [2] , [5] , [1] , [3] ]
[ [4] , [2] , [1] , [5] , [3] ]
[ [4] , [1] , [2] , [5] , [3] ]
[ [1] , [4] , [2] , [5] , [3] ]
[ [1] , [4] , [2] , [3] , [5] ]
[ [1] , [2] , [4] , [3] , [5] ]
[ [1] , [2] , [3] , [4] , [5] ]

Para k=2 , usar la misma estrategia daría un límite de 2 (n choose 2) canjes necesarios. Para el ejemplo anterior, eso significa 20 intercambios. Pero hay una solución que usa solo 15 intercambios:

[ [5,5] , [4,4] , [3,3] , [2,2] , [1,1] ]
[ [5,4] , [5,4] , [3,3] , [2,2] , [1,1] ]
[ [5,4] , [3,4] , [5,3] , [2,2] , [1,1] ]
[ [5,4] , [3,4] , [2,3] , [5,2] , [1,1] ]
[ [5,4] , [3,4] , [2,3] , [1,2] , [5,1] ]
[ [5,4] , [3,4] , [2,1] , [3,2] , [5,1] ]
[ [5,4] , [3,1] , [2,4] , [3,2] , [5,1] ]
[ [1,4] , [3,5] , [2,4] , [3,2] , [5,1] ]
[ [1,4] , [3,2] , [5,4] , [3,2] , [5,1] ]
[ [1,4] , [3,2] , [2,4] , [3,5] , [5,1] ]
[ [1,4] , [3,2] , [2,4] , [3,1] , [5,5] ]
[ [1,4] , [3,2] , [2,1] , [3,4] , [5,5] ]
[ [1,4] , [1,2] , [2,3] , [3,4] , [5,5] ]
[ [1,1] , [4,2] , [2,3] , [3,4] , [5,5] ]
[ [1,1] , [2,2] , [4,3] , [3,4] , [5,5] ]
[ [1,1] , [2,2] , [3,3] , [4,4] , [5,5] ]

Esta solución es óptima para n=5 k=2 (prueba por fuerza bruta para encontrar todas las soluciones). Para n=6 , la mejor solución requiere 22 intercambios, pero la solución no se ve tan bien como la de n=5 (siga los 5 derechos, luego la izquierda, luego los 5 derechos, etc.), así que todavía No conozco una estrategia óptima, mucho menos una fórmula o mejor para el número de intercambios.

He estado pensando en esto por un par de días y no he encontrado nada esclarecedor. Si alguien tiene alguna idea sobre este problema, por favor compártalos. Estaría encantado de saber más sobre el caso k=2 . Aún mejor para cualquier idea sobre el caso general.

EDIT: me disculpo si no puedo motivar este problema a su gusto, pero aquí hay un intento: el número de tipos de burbujas necesarios para ordenar una permutación es una estadística muy importante en combinatoria y teoría de números, llamada número de inversión de la permutación. Puede ordenar una permutación fuera de servicio utilizando algoritmos mucho mejores, pero esta es la que le da el significado algebraico. Si eso no ayuda, quizás esta publicación SO relacionada pueda: ¿Para qué sirve una burbuja?

ACTUALIZACIÓN : La respuesta más antigua a continuación da un límite inferior (y superior) para el número de intercambios. La segunda respuesta más antigua proporciona un algoritmo que se acerca mucho a este límite inferior (a menudo lo alcanza). Sería fantástico si alguien pudiera mejorar el límite o, mejor aún, probar que el algoritmo que se proporciona a continuación es óptimo.

Answer 1

Aquí hay un algoritmo intuitivo en el que pensé. Da una prueba constructiva de la solución óptima, creo.

Aquí está el algoritmo:

Lo intenté por n = 4 5 6 7 9 y dio los mismos resultados que el de badawi:

La idea es la siguiente:

1: elige un valor extremo que no está en su lugar final (1 o n para comenzar)

2: encuentre el valor extremo que es el más cercano a su posición final (marcado con una flecha en mi ejemplo a continuación)

3: si está entre el elemento más grande,

luego moverlo al otro lado y desplazar todo el elemento más pequeño del par hacia la izquierda

de otra manera

muévelo al otro lado y desplace todo el elemento más grande de cada par hacia la derecha.

Nota: el desplazamiento es equivalente a "burbujear" este valor con el elemento más pequeño (resp más grande) de cada par.

4: regrese al paso 2, pero si elige uno de los grandes, tome uno de los pequeños y viceversa.

Es bastante intuitivo y parece funcionar:

Ejemplo n = 5:

11 22 33 44 55
^
|
12 23 34 45 51 (4 moves) // shifted all larger numbers to the left
^
|
52 13 24 43 51 (3 moves) // shifted all smaller numbers to the right
^
|
52 34 24 35 11 (3 moves) // shifted all larger numbers to the left
^
|
55 24 34 32 11 (3 moves) // smaller to the right
^
|
55 44 33 22 11 (2 moves) // larger to left

Total 15 movimientos.

segundo ejemplo n = 7:

11 22 33 44 55 66 77 // 6 moves
^
12 23 34 45 56 67 71 //5 moves
^
72 13 24 35 46 56 71 //5 moves
^
72 34 25 36 46 57 11 // 4 moves
^
77 24 35 26 36 45 11 //4 moves
^
77 45 36 26 35 42 11 //1 move
^
77 65 34 26 35 42 11 //2 moves
^
77 65 34 56 34 22 11 //2 moves
^
77 66 54 53 34 22 11 //1 move
^
77 66 54 45 33 22 11 //1 move
^
77 66 55 44 33 22 11

total: 31

No dude en hacerme preguntas si no estoy seguro.

Es bastante fácil hacerlo a mano. Puede probarlo usted mismo con 6 o 7 o escribir un algoritmo.

Lo intenté con 6 dio 23., con 7 dio 31 y con 9 dio 53, se tarda un minuto en calcularlo a mano sin calcular nada

Por qué esta solución es óptima:

Cada vez que mueves un elemento grande hacia el lado opuesto, mueves el más pequeño del par hacia la izquierda.

Así que mover todo el elemento grande no hará que pierdas ningún movimiento para mover el más pequeño.

Siempre mueves tu elemento en "la dirección correcta"

Además, para mover los elementos extremos, realiza la cantidad mínima de movimientos. (Esto se debe a que el algoritmo toma el valor extremo más cercano a su última posición que no se pierde ningún movimiento)

El razonamiento es el mismo para el elemento pequeño.

Este algoritmo te da movimientos óptimos ya que no hace ningún movimiento innecesario.

Espero no haber cometido ningún error.

Demuestra que los resultados de badawi fueron óptimos como esperaba.

Answer 2

Esta no es una respuesta óptima, pero me gustaría compartir mi intento ya que alguien puede mejorarlo. No pensé en encontrar una fórmula para calcular el número mínimo de intercambios, sino más bien en el algoritmo óptimo. El algoritmo se basa en k = 2.

La idea básica se basa en la ganancia de información. Supongamos que A = {[i, j]: 1 <= i <= n, 1 <= j <= n} representa una configuración . En cada paso, tenemos 4 * (n-1) posible intercambio para pasar de una configuración a otra configuración. Por ejemplo, si n = 2 (es decir, A = [{2,2}, {1,1}]), entonces tenemos 4 posibles intercambios A [0] [0] <-> A [1] [0], A [0] [0] <-> A [1] [1], A [0] [1] <-> A [1] [0], y A [0] [1] <-> A [1] [1] Por lo tanto, nuestro objetivo es seleccionar el intercambio que tenga alta ganancia de información cuando necesitemos pasar de una configuración a otra.

La parte difícil será "cómo calcular la ganancia de información". En mi solución (a continuación), la ganancia de información se basa en la distancia de un valor desde su posición correcta. Déjame mostrarte mi código (escrito en C ++) para entender lo que estoy tratando de decir:

const int n = 5;
const int k = 2;
int gain(int item, int from, int to)
{
if (to > from)
return item - to;
else
return to - item ;
}
void swap(int &x, int &y)
{
int temp = x;
x = y;
y = temp;
}
void print_config (int A[][k])
{
cout << "[";
for (int i=0; i<n; i++) {
cout << " [";
for (int j=0; j<k; j++) {
cout << A[i][j] << ", ";
}
cout << "/b/b], ";
}
cout << "/b/b ]" << endl;
}
void compute (int A[][k], int G[][4])
{
for (int i=0; i<n-1; i++)
{
G[i][0] = gain(A[i][0], i+1, i+2) + gain(A[i+1][0], i+2, i+1);
G[i][1] = gain(A[i][0], i+1, i+2) + gain(A[i+1][1], i+2, i+1);
G[i][2] = gain(A[i][1], i+1, i+2) + gain(A[i+1][0], i+2, i+1);
G[i][3] = gain(A[i][1], i+1, i+2) + gain(A[i+1][1], i+2, i+1);
}
}
int main()
{
int A[n][k];
int G[n-1][k*k];
// construct initial configuration
for (int i=0; i<n; i++)
for (int j=0; j<k; j++)
A[i][j] = n-i;
print_config(A);
int num_swaps = 0;
int r, c;
int max_gain;
do {
compute (A, G);
// which swap has high info gain
max_gain = -1;
for (int i=0; i<n-1; i++)
for (int j=0; j<k*k; j++)
if (G[i][j] > max_gain) {
r = i;
c = j;
max_gain = G[i][j];
}
// Did we gain more information. If not terminate
if (max_gain < 0) break;
switch (c)
{
case 0: swap(A[r][0], A[r+1][0]); break;
case 1: swap(A[r][0], A[r+1][1]); break;
case 2: swap(A[r][1], A[r+1][0]); break;
case 3: swap(A[r][1], A[r+1][1]); break;
}
print_config(A);
num_swaps++;
} while (1);
cout << "Number of swaps is " << num_swaps << endl;
}

Ejecuté el código anterior para los casos n = 1,2, ... y 7. Aquí están las respuestas (cantidad de intercambios) respectivamente: 0, 2, 5, 10, 15, 23 (muy cerca) y 31. I piense que la función gain () no funciona bien cuando n es par. Puede confirmarlo validando el número de swaps cuando n = 7. El límite inferior de su ecuación es 31, por lo que este es el número óptimo de swaps cuando n = 7.

Estoy imprimiendo aquí la salida cuando n = 5 (ya que está buscando un patrón):

[ [5, 5], [4, 4], [3, 3], [2, 2], [1, 1] ]
[ [4, 5], [5, 4], [3, 3], [2, 2], [1, 1] ]
[ [4, 5], [3, 4], [5, 3], [2, 2], [1, 1] ]
[ [4, 5], [3, 4], [2, 3], [5, 2], [1, 1] ]
[ [4, 5], [3, 4], [2, 3], [1, 2], [5, 1] ]
[ [4, 3], [5, 4], [2, 3], [1, 2], [5, 1] ]
[ [4, 3], [2, 4], [5, 3], [1, 2], [5, 1] ]
[ [4, 3], [2, 4], [1, 3], [5, 2], [5, 1] ]
[ [4, 3], [2, 4], [1, 3], [1, 2], [5, 5] ]
[ [4, 3], [2, 1], [4, 3], [1, 2], [5, 5] ]
[ [1, 3], [2, 4], [4, 3], [1, 2], [5, 5] ]
[ [1, 3], [2, 4], [1, 3], [4, 2], [5, 5] ]
[ [1, 3], [2, 1], [4, 3], [4, 2], [5, 5] ]
[ [1, 1], [2, 3], [4, 3], [4, 2], [5, 5] ]
[ [1, 1], [2, 3], [2, 3], [4, 4], [5, 5] ]
[ [1, 1], [2, 2], [3, 3], [4, 4], [5, 5] ]

Answer 3

Sé que es bastante hortera responder a la propia pregunta, pero lo he descubierto y está más cerca de una respuesta que de una parte de la pregunta. Sin embargo, esta no es una respuesta completa y no será aceptado, así que por favor publique sus pensamientos si alguien puede mejorar esto.

El número mínimo de swaps, digamos m , para k=2 está limitado por:

2 * (n choose 2) >= m >= (2n choose 2) / 3

¿Por qué funciona esto?

El límite superior viene haciendo una clasificación de burbuja en los primeros elementos de las matrices, seguido de una ordenación de burbuja en los segundos elementos de las matrices. Esa parte no es tan complicada.

El límite inferior es un poco complicado, pero así es como llegué. Vamos a contar el número de pases , donde ocurre un pase cuando un número mayor se mueve desde la izquierda de un número más pequeño a la derecha de ese número. Esto puede suceder en 1 intercambio de b , con a más grande y en el conjunto a la izquierda de b . También puede tomar 2 intercambios si a se mueve a la matriz con b en un intercambio y luego se mueve en un intercambio posterior. Para realizar un seguimiento de las cosas correctamente, cuente los pases en mitades en este caso. Para facilitar el conteo, también cuenta como un pase cuando dos del mismo número se dividen y luego se recombinan.

La matriz está completamente ordenada después de (2n choose 2) pases, por lo que la única pregunta es cuántos pases pueden suceder con un intercambio. Aquí hay un ejemplo simple donde a y c se intercambian:

... [a,b] , [c,d] ...
... [c,b] , [a,d] ...

Ahora contamos el número máximo de pases que pueden haber pasado:

• Desde a > c , definitivamente obtenemos 1 pase completo.
• Si a > b , obtenemos 1/2 pase porque debe haberse dejado a b en algún punto.
• Si a > d , entonces obtenemos 1/2 pase porque a será correcto de d en algún punto.
• Si c < d , entonces obtenemos 1/2 pase porque d debe haberse quedado de c en algún punto.
• Si c < b , obtenemos 1/2 pase porque b estará a la derecha de c en algún punto.

Por lo tanto, lo mejor que puedes hacer en un intercambio es obtener 3 pases (1 completo y 4 mitades).

¿Por qué esta no es una respuesta completa?

¡No tengo idea si el límite inferior siempre es alcanzable! No creo que sea así, y, a pesar de varios intentos fallidos, no puedo codificar un algoritmo que lo logre.