运动员最佳配对问题(分支界限法)

2023-11-06 00:40

本文主要是介绍运动员最佳配对问题(分支界限法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

运动员配对问题

一、问题描述

【问题简述】
羽毛球队有男女运动员各n人。给定2个n×n矩阵P和Q。P[i][j]是男运动员i和女运动员j配对组成混合双打的男运动员竞赛优势;Q[i][j]是女运动员i和男运动员j配合的女运动员竞赛优势。由于技术配合和心理状态等各种因素影响,P[i][j]不一定等于Q[j][i]。男运动员i和女运动员j配对组成混合双打的男女双方竞赛优势为P[i][j]×Q[j][i]。设计一个算法,计算男女运动员最佳配对法,使各组男女双方竞赛优势的总和达到最大。
【输入形式】
由文件input.txt给出输入数据。第1行有1个正整数n(1≤n≤20)。接下来的2n行,每行n个数。前n行是p,后n行是q。
【输出形式】
将计算的男女双方竞赛优势的总和的最大值输出到文件output.txt。

二、问题分析

【题目分析】
这道题目共有n!种配对情况,也就是相当于固定男运动员,然后对女运动员进行一次全排列,并求出对应的优势之和的最大值,本题可以用回溯法,也可以用分支限界法,在使用分支限界法的时候,关键是在于设计上界函数。
在这里,我们把上界函数定义为:剩下的未配对的女运动员(不考虑男运动员配对情况下)所能达到的优势最大值之和(记为r)与当前配对已达到的优势(记为sum)之和。
在使用分支限界法的时候,一旦搜索到所搜索过的叶节点,那么就立即结束算法,因为最先出来的叶节点必定是最优解。

三、算法设计

利用分支界限法求解此题:
①创建一个最大值堆,用于表示活结点优先队列
②队中每个结点的sum值是优先队列的优先级
③算法计算出每个顶点的最大sum值
④搜索到所搜索的排列数的叶子节点,算法结束,输出最大值

四、关键代码

【初始化数组】

file.open("input.txt",ios::in);		//打开输入文件file >> n;for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){file >> P[i][j];}}for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){file >> Q[i][j];}}file.close();	//关闭输入文件 

​ 利用两个二维数组来储存Pij和Qij,时间复杂度为O(n²),空间复杂度为O(n²)
【分支界限法求解】

while (Node->id != n ){for (int i = Node->id; i < n; i++){node* nNode = new node();nNode->id = Node->id + 1;nNode->x = new int[n];for (int t = 0; t < n; t++){nNode->x[t] = Node->x[t];}nNode->x[Node->id] = Node->x[i];nNode->x[i] = Node->x[Node->id];nNode->sum = Node->sum + P[Node->id][nNode->x[Node->id]] * Q[nNode->x[Node->id]][Node->id];nNode->r = Node->r - maxn[Node->id];nNode->up = nNode->sum + nNode->r;q.push(nNode);}if (!q.empty()){Node = q.top();q.pop();}else {tmp = 0;break;}}tmp = Node->sum;

​ 相较于回溯法的时间复杂度O(n!),分支界限法对排列树进行广度优先搜索,算法复杂度有所降低。

五、实验源码

#include<iostream>
#include<algorithm>
#include<queue>
#include <fstream>
using namespace std;
int P[20][20];
int Q[20][20];
int maxn[20];
int n;
fstream file;
struct node {int id;int sum;int r;int up;int* x;
};
struct cmp {bool operator()(node* a, node* b){return(a->up < b->up);}
};
int main()
{file.open("input.txt",ios::in);		//打开输入文件file >> n;for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){file >> P[i][j];}}for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){file >> Q[i][j];}}file.close();	//关闭输入文件 for (int i = 0; i < n; i++){int maxnum = 0;for (int j = 0; j < n; j++){maxnum = max(maxnum, Q[i][j] * P[j][i]);}maxn[i] = maxnum;}int tmp = 0;priority_queue<node*, vector<node*>, cmp>  q;node* Node = new node();Node->id = 0;Node->sum = 0;Node->r = 0;Node->up = 0;for (int i = 0; i < n; i++){Node->r += maxn[i];}Node->up = Node->r;Node->x = new int[n];for (int i = 0; i < n; i++){Node->x[i] = i;}while (Node->id != n ){for (int i = Node->id; i < n; i++){node* nNode = new node();nNode->id = Node->id + 1;nNode->x = new int[n];for (int t = 0; t < n; t++){nNode->x[t] = Node->x[t];}nNode->x[Node->id] = Node->x[i];nNode->x[i] = Node->x[Node->id];nNode->sum = Node->sum + P[Node->id][nNode->x[Node->id]] * Q[nNode->x[Node->id]][Node->id];nNode->r = Node->r - maxn[Node->id];nNode->up = nNode->sum + nNode->r;q.push(nNode);}if (!q.empty()){Node = q.top();q.pop();}else {tmp = 0;break;}}tmp = Node->sum;file.open("output.txt",ios::out); 	//打开输出文件  file << tmp;file.close();return(0);
}

实例输入txt文件:
在这里插入图片描述

六、实验心得

【回溯法与分支界限法的比较】
1.回溯法:
回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。这种以深度优先方式系统搜索问题解的算法称为回溯法。
2.分支限界法:
分支限界法是以广度优先或以最小耗费优先的方式搜索解空间树,在每一个活结点处,计算一个函数值,并根据函数值,从当前活结点表中选择一个最有利的结点作为扩展结点,使搜索朝着解空间上有最优解的分支推进,以便尽快地找出一个最优解,这种方法称为分支限界法。
3.回溯法的基本思想:
用回溯法解问题时,应明确定义问题的解空间。问题的解空间至少应包含问题的一个解。之后还应将解空间很好的组织起来,使得能用回溯法方便的搜索整个解空间。在组织解空间时常用到两种典型的解空间树,即子集树和排列树。确定了解空间的组织结构后,回溯法从开始结点出发,以深度优先方式搜索整个解空间。这个开始结点成为活结点,同时也成为当前的扩展结点。在当前的扩展结点处,搜索向纵深方向移至一个新结点。这个新结点就成为新的活结点,并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动,则当前扩展结点就成为死结点。此时,应往回移动至最近的一个活结点处,并使这个活结点成为当前的扩展结点。回溯法以这种工作方式递归的在解空间中搜索,直至找到所要求的解或解空间中已无活结点时为止。
4.分支限界法的基本思想:
分支限界法常以广度优先或以最小耗费有限的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树,常见的有子集树和排列树。在搜索问题的解空间树时,分支限界法和回溯法的主要区别在于它们对当前扩展节点所采用的扩展方式不同。在分支限界法中,每一个活结点只有一次机会成为扩展节点。活结点一旦成为扩展节点,就一次性产生其所有儿子节点。在这些儿子节点中,导致不可行解或导致非最优解的儿子节点被舍弃,其余儿子节点被加入活结点表中。此后,从活结点表中取下一节点为当前扩展节点。并重复上述节点扩展过程。这个过程移至持续到找到所需的解或活结点表为空为止。
从活结点表中选择下一扩展节点的不同方式导致不同的分支限界法。最常见的有以下两种方式:
(1)队列式分支限界法:队列式分支限界法将活结点表组织成一个队列,并按队列的先进先出原则选取下一个节点为当前扩展节点。
(2)有限队列式分支限界法:优先队列式的分支限界法将活结点表组织成一个优先队列,并按优先队列中规定的节点优先级选取优先级最高的下一个节点成为当前扩展节点。

【实验心得】
对排列树在分支界限法中的运用有了更好的理解与运用,并且对队列式分支限界法有了更加深刻的理解,也对分支限界法与回溯法的运用有了更好的区别运用。

下一个节点成为当前扩展节点。

【实验心得】
对排列树在分支界限法中的运用有了更好的理解与运用,并且对队列式分支限界法有了更加深刻的理解,也对分支限界法与回溯法的运用有了更好的区别运用。

这篇关于运动员最佳配对问题(分支界限法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/353479

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

pip无法安装osgeo失败的问题解决

《pip无法安装osgeo失败的问题解决》本文主要介绍了pip无法安装osgeo失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 进入官方提供的扩展包下载网站寻找版本适配的whl文件注意:要选择cp(python版本)和你py

解决Java中基于GeoTools的Shapefile读取乱码的问题

《解决Java中基于GeoTools的Shapefile读取乱码的问题》本文主要讨论了在使用Java编程语言进行地理信息数据解析时遇到的Shapefile属性信息乱码问题,以及根据不同的编码设置进行属... 目录前言1、Shapefile属性字段编码的情况:一、Shp文件常见的字符集编码1、System编码

Spring MVC使用视图解析的问题解读

《SpringMVC使用视图解析的问题解读》:本文主要介绍SpringMVC使用视图解析的问题解读,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC使用视图解析1. 会使用视图解析的情况2. 不会使用视图解析的情况总结Spring MVC使用视图

Redis解决缓存击穿问题的两种方法

《Redis解决缓存击穿问题的两种方法》缓存击穿问题也叫热点Key问题,就是⼀个被高并发访问并且缓存重建业务较复杂的key突然失效了,无数的请求访问会在瞬间给数据库带来巨大的冲击,本文给大家介绍了Re... 目录引言解决办法互斥锁(强一致,性能差)逻辑过期(高可用,性能优)设计逻辑过期时间引言缓存击穿:给