Algoritmos de Pseudoordenación

El artículo de hoy es un poco especial porque pretende dar a conocer una idea que lleva tiempo rondando en mi cabeza y que, hasta donde llega mi investigación al respecto, no ha sido explotada académicamente hasta el momento: Los algoritmos de Pseudoordenación.

Se trata, en cierto sentido, de la imagen especular de los Algoritmos de Ordenación Adaptativos y tienen más aplicaciones de las que se pueden apreciar a priori.

Introducción

Tengo que reconocer que los otros 4 artículos que se han publicado esta semana en este blog son una mera excusa para contextualizar éste. Así pues ya podéis suponer la importancia que le doy a este concepto. Repasemos lo dicho hasta ahora:

  • Primero vimos qué es un algoritmo y cómo se mide su eficiencia.
  • Más tarde aprendimos qué es un algoritmo de ordenación y comprendimos que hay un límite teórico para la eficiencia de un algoritmo que ordene completamente cualquier secuencia de N elementos: O(N·log(N)) pasos.
  • Pero hay aplicaciones que requieren mucha eficiencia y quisimos traspasar ese límite. Para ello eliminamos una de las premisas teóricas: Nos conformamos con que ordenase muy rápido algunas secuencias. Así nacieron los conocidos y estudiados Algoritmos de Ordenación Adaptativos.
  • Sin embargo, hay otra premisa que podemos eliminar para ganar eficiencia: ¿Que tal si consideramos aquellos algoritmos que toman una secuencia cualquiera de N elementos y, en tiempo O(N), la devuelven (tan sólo) un poco más ordenada?

Yo los llamo Algoritmos de Pseudoordenación y, hasta el momento, no he encontrado mucha documentación sobre ellos.

Algoritmos de Pseudoordenación

Un algoritmo de Pseudoordenación es un algoritmo que en tiempo O(N) es capaz de ordenar un poco una secuencia de N elementos (comparables 2 a 2). En concreto, dada una medida del desorden D, un algoritmo de Pseudoordenación es aquel que después de una ejecución es capaz de transformar una permutación P de N elementos en otra permutación P’ tal que D(P’) < D(P).

En consecuencia, los algoritmos de Pseudoordenación se clasifican en función de la medida del desorden que minimizan en cada paso.

Ejemplos

Si bien el concepto no es muy conocido (agradeceré referencias) es relativamente fácil comprobar que algunos de los algoritmos de ordenación que ya conocemos pueden interpretarse como la aplicación iterativa de un algoritmo de pseudoordenación.

En la iteración i del Selectionsort podemos asegurar que habrá, como mcuho, N-i elementos fuera de su lugar definitivo. Por lo tanto, si usamos como medida del desorden dicha cantidad, el Selectionsort consiste en aplicar N veces un algoritmo de Pseudoordenación.

De manera similar, una ligera modificación del Quicksort que escoja como pivote el elemento medio en cada caso (se puede hacer en tiempo O(N)) nos garantiza que en la iteración i cada elemento está, como mucho, a distancia N/(2^i) de su posición final. Por lo tanto el Quicksort así modificado consiste en aplicar en repetidas ocasiones un algoritmo de Pseudoordenación que minimiza el máximo de las distancias que hay entre la posición actual de un elemento y su posición final.

Por otra parte tenemos que el Mergesort garantiza que en la iteración i la Mayor Subsecuencia Creciente de la secuencia que estamos obteniendo tiene un tamaño mínimo de 2^i. Como veremos mañana este es otro de los criterios que se pueden usar para medir el orden de una secuencia y, por lo tanto, el Mergesort también consiste en aplicar iterativamente un algoritmo de Pseudoordenación a la secuencia.

Algoritmos de Pseudoordenación Perfectos

La diferencia fundamental entre el primer ejemplo y los otros dos es que el Selectionsort reduce el desorden de la secuencia en una unidad en cada iteración mientras que el Quicksort y el Mergesort lo reducen a la mitad en el mismo tiempo. Esto significa que se necesitarán N iteraciones O(N) para ordenar una secuencia con el primero y tan sólo log(N) iteraciones O(N) para ordenar la misma secuencia con los otros dos.

Esto nos lleva a una definición parecida a la que hice ayer: Un Algoritmo de Pseudoordenación Perfecto es aquel que en cada iteración reduce el desorden de la secuencia a la mitad. En consecuencia, dicho algoritmo aplicado log(N) veces ordena perfectamente la secuencia.

Como ya hemos visto, tanto el Quicksort como el Mergesort son algoritmos de pseudoordenación perfectos.

Aplicaciones

Las aplicaciones más evidentes para un algoritmo de pseudoordenación tienen que ver con aquellos casos en los que comparar elementos (y moverlos) es tremendamente costoso. Así pues, el tiempo ahorrado puede compensar con creces los errores cometidos con dicho algoritmo.

Estos errores, además, pueden controlarse. Es decir, en todo momento sabremos cual es el error máximo que estaremos cometiendo al aplicar un número fijo de veces un algoritmo de pseudoordenación y tomar su salida como si fuese una secuencia ordenada.

Por lo tanto, otra aplicación razonable para los algoritmos de ordenación basados en algoritmos de pseudoordenación es la de proporcionar la secuencia más ordenada posible en un tiempo dado. Es decir, si a media ejecución debemos parar (por un error o por estar trabajando en tiempo real) tendremos el mejor resultado posible dados los recursos disponibles. Técnicamente esto se resume diciendo que los algoritmos de ordenación basados en algoritmos de pseudoordenación son voraces y por lo tanto, su aplicación es de utilidad en el campo de la heurística.

Otra aplicación evidente consiste en hacer más eficientes los algoritmos de ordenación cuya función de comparación no es del todo fiable. Imaginemos que queremos ordenar en orden creciente de belleza 1.000.000 de cuadros. Para ello contamos con la colaboración de 1 experto que nos cobra 1€ por cada comparación de 2 cuadros que tenga que hacer. ¿Cómo podríamos ordenarlos de manera razonablemente barata? Bien, usando un algoritmo de ordenación basado en un algoritmo de pseudoordenación podemos gastar exactamente tanto como queramos y los errores que cometamos por no usar un algoritmo de ordenación normal seguramente no serán más grandes que los que cometa el experto al usar su criterio subjetivo.

Por último se me ocurre una aplicación muy 2.0 que en pasar un breve test a los usuarios de un servicio web para adivinar sus gustos. Para hacerlo perfectamente sería necesario usar un gran número de preguntas pero si no queremos agobiar a nuestros usuarios podemos colocar un botón “Me he cansado!” que finalice el proceso de aprendizaje prematuramente. De esa manera el usuario responde exactamente lo que le apetezca y el sistema aprende tanto como le es posible sin agobiar a nadie.

En definitiva seria muy interesante estudiar en profundidad estos algoritmos y darlos a conocer en los ámbitos en los que pueden ser de utilidad.

Merge Sort BOLAEXTRA: Este post pertenece a una serie especial de 5 artículos relacionados:

  1. Eficiencia Algorítmica y Notación Asintótica
  2. Algoritmos de Ordenación
  3. Algoritmos de Ordenación Adaptativos
  4. Algoritmos de Pseudoordenación
  5. Medidas del Orden de una Secuencia

Te recomiendo encarecidamente que leas los 5 en orden ya que cada uno de ellos depende fuertemente de los anteriores.

Escrito en 10/12/09 10:00 por Carlos Luna en las categorías:

Comentarios

Deja un Comentario

Quizás quieras usar textile para dar formato a tu comentario.

"linktext":http://       _em_       *strong*       -strike-       ^sup^       ~sub~
bq. Blockquote       # Lista numerada       * Lista no-numerada       ==html crudo, sin textile==

(no será mostrado) (http://...)