扩展棋盘多项式在二分图匹配中的应用研究

扩展了现有的棋盘多项式表达,把二分图匹配的图论问题转换成扩展的棋盘多项式问题来进行求解。在计算k个棋子在棋盘上按不同行不同列布局总数的同时,通过计算扩展的棋盘多项式,给出了详细布局方案的解析解。在算法实现上,提出了计算扩展棋盘多项式的非递归求解算法,可以提高算法的执行效率。在二分图匹配应用中,通过计算所有最大匹配方案,可以从这些方案中优中选优,选出满足附加约束条件的最优解。最后实验结果验证了本方法的有效性。