Algoritmo para determinar el mejor equipo y formación?

Question

Estoy buscando algoritmos adecuados que podría utilizar en un simulador de gestión de equipo deportivo (por ejemplo, hockey o fútbol). Algunas características del simulador:

• El equipo puede jugar con diferentes formaciones (por ejemplo, fútbol 4-4-2).
• Cada jugador en el equipo tiene una calificación numérica de lo buenos que son para cada posición en la formación.
• Hay un grupo de jugadores de escuadrones de capacidades que van desde la cual el equipo se puede seleccionar

Qué algoritmos se pueden utilizar para determinar mediante programación y eficientemente los equipos y las formaciones más fuertes?

Answer 1

Si modelamos el problema gráfico y darse cuenta de que el número de diferentes formaciones es pequeña, el problema es maximum weighted bipartite matching, que es soluble por Hungarian Algorithm, ....

Pero cómo modelar el problema con los gráficos bipartitos? Establezca a los jugadores como una parte y los posiciona como otra parte (por ejemplo, en fútbol), para formar un grupo de jugadores y posición 11 para ellos, conecte a todos los jugadores a todas las posiciones y establezca el peso lateral correspondiente como clasificación de jugador correspondiente en la posición .

Ahora todo lo que debe hacer es encontrar un maximum (weighted) matching en este gráfico bipartito completo. (los códigos están disponibles en el enlace wiki).

Supongo que tenemos un número limitado de formaciones, para cada formación podemos encontrar el correspondiente gráfico correspondiente, y luego la coincidencia máxima, finalmente tomar el valor máximo sobre todas las formaciones posibles (en todos los gráficos).

Answer 2

La heurística más simple que se puede aplicar a su problema es el algoritmo codicioso, cuya explicación se puede encontrar en http://en.wikipedia.org/wiki/Greedy_algorithm.

Otra solución es crear dos nodos ficticios (comienzo y final) y considerar su grupo de jugadores como un gráfico ordenado (primero viene el portero, luego el defensor derecho, y así sucesivamente). Los bordes consistirán en la clasificación de los jugadores para el puesto considerado. En este escenario, tendrá un escenario donde puede aplicar el algoritmo A *, cuya descripción encontrará en http://en.wikipedia.org/wiki/A*_search_algorithm (solo recuerde que un problema de maximización es solo una minimización de la función inversa).

Answer 3

Puede probar un enfoque heurístico utilizando las herramientas de IA existentes para optimizaciones, como Genetic Algorithms o Hill Climbing.
Daré más detalles sobre la escalada, ya que es mi favorita.

representar a su problema, ya que los estados graficarG = (V,E) tal que V = {all possible states } y E = {(u,v) | swapping one player you can move from u to v }.
Además, deje que u:V->R sea una función de utilidad para una formación.
Dado que no queremos para generar el gráfico, vamos next:V->2^V ser una función tal que next(v) = {all possible formation that you can get by changing one player }

La idea de la escalada es inicio de una formación al azar, y con avidez hacer el mejor cambio posible, cuando esté atascado - reinicie el algoritmo de una nueva formación aleatoria.

1. best<- -INFINITY 
2. while there is more time 
3. choose a random matching 
4. NEXT <- next(s) 
5. if max{ u(v) | for each v in NEXT} < u(s): //s is a local maximum 
    5.1. if u(s) > best: best <- u(s) //if s is better then the previous result - store it. 
    5.2. go to 2. //restart the hill climbing from a different random point. 
6. else: 
    6.1. s <- max { NEXT } 
    6.2. goto 4. 
7. return best //when out of time, return the best solution found so far. 

Tenga en cuenta que esta variación de subida de pendientes (Hill escalada con reinicios aleatorios) es un any time algorithm - lo que significa que llegará a ser mejor cuando se le da más tiempo, y cuando se da un tiempo infinito - se funda el máximo global .