Te damos la bienvenida a nuestra página web, en este lugar encontrarás la solucíon que andabas buscando.
Solución:
Si modelamos su problema mediante un gráfico y notamos que el número de formaciones diferentes es pequeño, el problema es una coincidencia bipartita ponderada máxima, que se puede resolver con el algoritmo húngaro, …
Para modelar el problema con gráficos bipartitos, coloque jugadores en una parte y posiciones en la otra parte (por ejemplo, en fútbol), para formar un grupo de jugadores y 11 posiciones para ellos, conecte todos los jugadores a todas las posiciones y establezca el borde correspondiente pesos como una calificación de jugador correspondiente en la posición.
Ahora todo lo que debe hacer es encontrar una coincidencia máxima (ponderada) en este gráfico bipartito completo. (los códigos están disponibles en el enlace wiki).
Supuse que tenemos un número limitado de formaciones, para cada formación podemos encontrar el gráfico coincidente correspondiente, y su máximo peso coincidente, finalmente tomar el valor máximo sobre todas las formaciones posibles (en todos los gráficos).
Puede probar un enfoque heurístico utilizando herramientas de IA existentes para optimizaciones, como Algoritmos genéticos o Montañismo.
Daré más detalles sobre el montañismo, ya que es mi favorito.
Representa tu problema como un gráfico de estadosG = (V,E) tal que V = all possible states y E = (u,v) .
También, deja u:V->R sea una función de utilidad para una formación.
Como no queremos generar el gráfico, dejemos 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 escalar colinas es Comience desde una formación aleatoria y con avidez haga el mejor cambio posible.cuando esté atascado, reinicie el algoritmo desde 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 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 escalada (escalada con reinicios aleatorios) es una cualquier algoritmo de tiempo - lo que significa que será mejor cuando se dé más tiempo, y cuando se dé un tiempo infinito - funda el máximo global.
Te invitamos a añadir valor a nuestro contenido participando con tu veteranía en las explicaciones.