bubble - sorting algorithms examples
Algoritmo de clasificación basado en comparación (3)
Busqué en Google, busque el capítulo 12.3, Clasificación topológica y búsqueda en profundidad.
http://www.cs.cmu.edu/~avrim/451f09/lectures/lect1006.pdf
Su conjunto de relaciones describe un gráfico acíclico dirigido (ojalá sea acíclico) y, por lo tanto, la clasificación topológica es exactamente lo que necesita.
Me gustaría clasificar u ordenar una colección de artículos (con un tamaño potencialmente mayor que 100,000) donde los artículos de la colección no tienen un valor intrínseco (comparable), en cambio, todo lo que tengo son las comparaciones entre dos artículos que han sido proporcionados por los usuarios Una manera subjetiva.
Ejemplo: Considere una colección con elementos [a, b, c, d] y comparaciones por los usuarios b > a , a > d , d > c . El orden correcto de esta colección sería [b, a, d, c] .
Este ejemplo es simple, sin embargo, podría haber casos más complicados:
- Dado que las comparaciones son subjetivas, un usuario también podría decir que
c > b. En cuyo caso eso causaría un conflicto con el pedido anterior. - Además, es posible que no tenga comparaciones que "conecten" todos los elementos, es decir,
b > a,d > c. En cuyo caso el ordenamiento es ambiguo. Podría ser[b, a, d, c]o[d, c, b, a]. En este caso, cualquiera de los pedidos es aceptable.
Si es posible, sería bueno tener en cuenta de alguna manera múltiples instancias de la misma comparación y dar más peso a las personas con mayores incidencias. Pero una solución sin esta condición todavía sería aceptable.
Una aplicación similar de este algoritmo fue utilizada por la aplicación FaceMash de Zuckerberg donde clasificó a las personas según las comparaciones (si lo entendí correctamente), pero no he podido encontrar lo que realmente era ese algoritmo.
¿Hay un algoritmo que ya exista que pueda resolver el problema anterior? No me gustaría gastar esfuerzos tratando de encontrar uno si ese es el caso. Si no hay un algoritmo específico, ¿hay tal vez ciertos tipos de algoritmos o técnicas que me puedan indicar?
Este es un problema que ya ha ocurrido en otra arena: ¡juegos competitivos! Aquí, también, el objetivo es asignar a cada jugador un "rango" global sobre la base de una serie de comparaciones de 1 contra 1. La dificultad, por supuesto, es que las comparaciones no son transitivas (en su pregunta, entiendo que "subjetivo" significa "proporcionado por un ser humano"). Kasparov le gana a Fischer (¡no conozco a otro jugador de ajedrez!) Bob le gana a Kasparov, potencialmente.
Esto hace que los algoritmos inútiles que dependen de la transitividad (es decir, a > b and b > c => a > c ) a medida que termine con (probablemente) un gráfico altamente cíclico.
Se han ideado varios sistemas de clasificación para abordar este problema.
El sistema más conocido es probablemente el algoritmo / puntuación de Elo para jugadores de ajedrez competitivos. Sus descendientes (por ejemplo, el sistema de calificación de Glicko ) son más sofisticados y tienen en cuenta las propiedades estadísticas del registro de ganancias / pérdidas. En otras palabras, ¿qué tan confiable es una calificación? Esto es similar a su idea de ponderar más los registros con más "juegos" jugados. Glicko también forma la base del sistema TrueSkill utilizado en Xbox Live para videojuegos multijugador.
Usted puede estar interesado en el problema de conjunto de arco de retroalimentación mínima. Esencialmente, el problema es encontrar el número mínimo de comparaciones que "vayan por el camino equivocado" si los elementos están ordenados linealmente en algún orden. Esto es lo mismo que encontrar el número mínimo de bordes que se deben eliminar para que el gráfico sea acíclico. Desafortunadamente, resolver el problema exactamente es NP-difícil.
Un par de enlaces que discuten el problema:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.8157&rep=rep1&type=pdf