algorithm - saaty - metodo de comparacion por pares
Ordenar una matriz con un número mínimo de comparaciones (6)
Necesito ayuda con mi tarea de CS. Necesito escribir una rutina de clasificación que ordene una matriz de longitud 5 usando 7 comparaciones en el peor de los casos (he demostrado que se necesitarán 7, debido a la altura del árbol de decisión).
Consideré usar el árbol de decisión ''codificado'', pero eso significa que el algoritmo es realmente complicado y mi tutor ha insinuado que no es la forma en que se supone que debe hacerse.
He comprobado que la ordenación rápida, el tipo de fusión, el tipo de ordenamiento dinámico, el tipo de ordenamiento dinámico, el ordenamiento de inserción, el ordenamiento de selección, no responden al requisito, lo que me lleva a pensar que es necesario un algoritmo específico para arreglos de longitud 5.
Realmente me gustaría obtener algunas pistas en la dirección correcta.
7 suena como si también pudiera ser tipo shell .
Eche un vistazo al tipo de cubo.
La clasificación del cubo se puede implementar como un algoritmo de comparación de la siguiente manera:
Toma un elemento.
Compáralo con todos los cubos.
Colócala en el cubo que coincida. <- Comparación necesaria.
Si no se encuentra el cubo, crea un nuevo cubo.
Por lo tanto, es un algoritmo dinámico de clasificación de cubeta que acabo de describir.
Ya inventé / describí esto en un grupo de noticias en el pasado.
No creo que la solución codificada deba ser tan complicada:
- Compare (elementos) 2 y 3, y cambie si es necesario
- Compare 3 y 4, y cambie si es necesario
- Compare 1 y 3, si 1 es menor, luego compare 1 y 2, de lo contrario compare 1 y 4. Coloque 1 en la ranura correcta.
- Repita el paso 3, excepto con los elementos 3 y 5.
Eso siempre usará 7 comparaciones.
EDITAR:
No creo que esto vaya a funcionar: el paso 4 está roto, y podría requerir una octava comparación. Considerar:
Index | 1 | 2 | 3 | 4 | 5 |
Value | 2 | 3 | 4 | 5 | 1 |
Etapa 4:
- Compara 3 y 5 == 4 vs 1 == elemento 5 menos que el elemento 3
- Compara 2 y 5 == 3 vs 1 == elemento 5 menos que el elemento 2
- ??? Necesita comparar 1 y 5 para saber dónde poner el elemento 5.
Sí, está en Knuth vol 3 página 185 (sección 5.3.1). ¡Esto fue documentado por primera vez en una tesis de doctorado, por lo que su profesor está siendo muy duro con usted! No hay un método elegante realmente simple; tienes que rastrearlo como un árbol parcialmente ordenado.
Aquí está en lisp. Probado OK (SBCL en Linux)
(defun small-sort (a)
"Sort a vector A of length 5"
(if (> (aref a 0) (aref a 1))
(rotatef (aref a 0) (aref a 1)))
(if (> (aref a 2) (aref a 3))
(rotatef (aref a 2) (aref a 3)))
(if (> (aref a 0) (aref a 2))
(progn
(rotatef (aref a 0) (aref a 2))
(rotatef (aref a 1) (aref a 3))))
(if (> (aref a 4) (aref a 2))
(if (> (aref a 4) (aref a 3))
(progn)
(rotatef (aref a 3) (aref a 4)))
(if (> (aref a 4) (aref a 0))
(rotatef (aref a 2) (aref a 4) (aref a 3))
(rotatef (aref a 0) (aref a 4) (aref a 3) (aref a 2))))
(if (> (aref a 1) (aref a 3))
(if (> (aref a 1) (aref a 4))
(rotatef (aref a 1) (aref a 2) (aref a 3) (aref a 4))
(rotatef (aref a 1) (aref a 2) (aref a 3)))
(if (> (aref a 1) (aref a 2))
(rotatef (aref a 1) (aref a 2))
(progn)))
a)
(defun check-sorted (a)
(do ((i 0 (1+ i)))
((>= i (1- (array-dimension a 0))))
;;(format t "~S ~S~%" (aref a i) (aref a (+ 1 i)))
(assert (<= (aref a i) (aref a (+ 1 i))))))
(defun rr ()
(dotimes (i 100000)
(let ((a (make-array 5 :initial-contents (list (random 1.0) (random 1.0) (random 1.0) (random 1.0) (random 1.0) ))))
;;(format t "A=~S~%" a)
(let ((res (small-sort a)))
(check-sorted res)
;;(format t "Res=~S~%" res)
))))
El arte de la programación de computadoras de Donald Knuth, volumen 3 tiene una sección sobre exactamente este tema. No tengo los libros aquí conmigo, pero estoy bastante seguro de que Knuth presenta el algoritmo para 5 elementos. Como sospecha, no existe un algoritmo general que proporcione el número mínimo de comparaciones para muchos tamaños, pero hay una serie de trucos comunes que se utilizan en dichos algoritmos.
A partir de recuerdos vagos, reconstruí el algoritmo para 5 elementos, y se puede hacer en 7 comparaciones. Primero, toma dos pares separados, compara los que están dentro de ellos y compara los más pequeños de cada par. Luego, compara el restante con el más grande de estos. Esto ahora se divide en dos casos según si el elemento restante fue más pequeño o más grande, pero en todos los casos es posible finalizar en las tres comparaciones disponibles.
Recomiendo hacer dibujos para ayudarte. Las fotos de Knuth son algo como esto:
o---o / o---o
que muestra los resultados después de las tres primeras comparaciones (y por lo que recuerdo, este tipo de imagen aparece en muchos géneros de comparación mínima). Una línea conecta dos elementos cuyo orden conocemos. Tener tales imágenes lo ayuda a determinar con qué elementos comparar, ya que quiere hacer una comparación que le proporcione la cantidad máxima de información.
Adición: Dado que hay una respuesta aceptada con código real, creo que no hay nada malo en terminar estos diagramas, y podrían ser una adición útil a la respuesta. Por lo tanto, comience con el anterior y compare el elemento que falta con el de la esquina superior izquierda. Si es más grande, esto llevará a
/--o o / /--o o /--o
Ahora, compara los dos elementos grandes en la parte superior derecha y terminamos con
o---o---o / o---o
Ahora, comparando el elemento inferior derecho primero contra el medio en la parte superior y luego contra el lado al que pertenece, lo colocamos correctamente utilizando las dos comparaciones restantes.
Si la comparación inicial resultó en que el resto del elemento es más pequeño, el diagrama se vuelve
o---o---o / o---o
Ahora, compara los dos que aún no tienen nada más pequeño que ellos. Una opción es el último diagrama anterior, que se puede resolver con las dos comparaciones restantes. El otro caso es
o---o / o---o---o
Y aquí de nuevo, el que aún no está en secuencia con los demás se puede colocar correctamente con dos comparaciones.