AN APPROACH FOR LINE CONFIGURATION BASED ON OPTIMAL BIPARTITE GRAPH MATCHING
A teams line-up plays a critical role in soccer. Motivated by the theory of the optimal matching in bipartite graph, we propose an approach based on Kuhn-Munkres algorithm for line-up configuration according to the specific formation and team information.A weighted bipartite graph is constructed to model the relationship between players and positions: there are two kinds of vertex sets, one represents players, and the other represents positions.The weight of every edge between two sets represents the score for some player in the corresponding position.Then Kuhn-Munkres algorithm is employed to compute the maximum weight of a constructed bipartite graph, which is regarded as optimal result.Besides by prohibiting some of the players playing and then re-scheduling the algorithm we find a number of good line-up.Next through data mining and decision tree algorithm we get the player features of best line-up in the corresponding positions, and compare them with the result. Theoretical analysis and experimental results show that the method proposed can complete the best lineup configuration function, and as a reference in the non-professional football.
line configuration optimal matching of bipartite graph Kuhn-Munkres algorithm data mining decision tree algorithm
HOU YIHAN KANG XIN HE ZUGUO
Beijing University of Posts and Telecommunications Computer Science Beijing,100876
国际会议
成都
英文
1236-1240
2011-11-25（万方平台首次上网日期，不代表论文的发表时间）