Algoritmo para los partidos menos requeridos para clasificar a los jugadores en el torneo.

Question

Suponiendo las siguientes condiciones:

1. Un nivel de habilidad superior siempre late un menor nivel de habilidad.
2. Dado n jugadores, cada uno tiene un distinto nivel de habilidad en comparación con los otros (n-1).
3. Si el jugador a tiene Un beat jugador B, y el jugador B ha latido el jugador C, entonces el jugador a es mejor que el jugador C y no coinciden con la necesidad de ocurrir.
4. El nivel de habilidad de cada jugador sólo puede ser utilizado para determinar si está completa (Se puede utilizar el nivel de habilidad para ayudar a que el algoritmo, se debe utilizar sólo el partido de la historia)
5. El algoritmo sólo se considera completa cuando cada jugador está correctamente clasificadas de acuerdo a su nivel de habilidad

Qué coincidencia algoritmo de clasificación de los n jugadores en el menor número de partidos?

Tenga en cuenta que he estado de partidos, y no las rondas. De manera concurrente las coincidencias que ocurren no ayuda. Aunque tengo curiosidad de que el algoritmo que hacerlo en el menor número de rondas así.

Si no hay una clara respuesta obvia, ¿qué métodos/técnicas vale la pena considerar?

La respuesta puede (probablemente?) ser un conocido estilo de torneo.

Si no tengo la sensación de que la respuesta es muy simple y está relacionado con algunas gráfico recorrido problema, o incluso relacionadas con los algoritmos de ordenación de enteros aleatorios.

---

Como ejemplo, voy a utilizar un algoritmo básico para 4 jugadores:

Player A (skill 4)
Player B (skill 3)
Player C (skill 2)
Player D (skill 1)

Los partidos

Round 1 (Match-making is random in round 1 as per condition 4)
A vs C: A wins
B vs D: B wins

Known: (A > C), (B > D)

Round 2
A vs B: A wins
C vs D: C wins

Known: (A > BCD), (B > D), (C > D)

Round 3
B vs C: B wins

Known: (A > BCD), (B > CD), (C > D)

Así que, dado que 4 jugadores, yo era capaz de encontrar el rango para todos los jugadores en 5 partidos.

Answer 1

Si estamos optimizando el número de fósforos, entonces este problema es exactamente equivalente al problema de encontrar un buen algoritmo de ordenación. Desde $m$ partidos de $2^m$ diferentes resultados posibles, y queremos distinguir $n!$ órdenes posibles entre los jugadores, debemos tener $2^m \ge n!$ o $m \ge \log_2 (n!) = O(n \log n)$ partidos. Algoritmos como quicksort o mergesort lograr esta cantidad de partidos, al menos asintóticamente.

(Por lo que sólo se ejecute quicksort, por ejemplo, y cada vez se le pide que compare dos elementos, tienen el correspondiente jugadores juegan un partido para decidir el resultado de la comparación.)

Es más interesante para optimizar el número de rondas. Desde cada ronda puede incluir hasta a $\frac n2$ partidos, el límite inferior en el número de rondas es sólo $\frac{\log_2 (n!)}{n/2} = O(\log n)$.

Podemos prestadas algunas de las construcciones a partir de la clasificación de las redes para lograr esta obligado, al menos asintóticamente. Una clasificación de la red puede ser pensado como un torneo de este tipo, con algunas restricciones:

1. Inicialmente, los jugadores se les da una calificación arbitraria de $1$ a $n$.
2. Cuando se jugó el partido entre los jugadores clasificados $i$ e $j$si $i<j$ pero el $i^{\text{th}}$ jugador pierde, los dos jugadores de intercambio de filas.
3. Los juegos tienen que estar arreglados de antemano -, pero en términos de rangos. (Así que las instrucciones para una ronda con 6 jugadores podrían ser "los jugadores clasificados 1 y 4 de juego, los jugadores clasificados 2 y 5 de juego, los jugadores se clasifican 3 y 6 jugar".)

La profundidad de un sistema de clasificación de la red es precisamente el número de rondas necesarias en el resultado del torneo.

Hay muchos clasificación de redes, tales como el bitonic clasificador, que ha calado $O(\log^2 n)$. Esto es bueno, pero no óptimo. La queratosis actínicas de la red es un sistema de clasificación de la red con la profundidad $O(\log n)$, la cual es óptima hasta un (enorme) constante; no es útil en la práctica.

Answer 2

La clasificación de inserción de combinación es óptima si el número de jugadores es menor que 15 o entre 20 y 22. Para un mayor número de jugadores existe un algoritmo de clasificación con menos comparaciones que la clasificación de inserción de combinación.

En general, este es un problema abierto.