【算法设计与分析】回溯法解决运动员配对问题(课程设计)

本文主要是介绍【算法设计与分析】回溯法解决运动员配对问题(课程设计),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

回溯法解决运动员配对问题

摘要

针对运动员最佳配对问题,本文利用回溯法寻求竞赛优势得分最优解,研究男女运动员最佳配对法,使各组男女双方竞赛优势的总和达到最大。针对这一问题,本题采用的是男运动员选女运动员的方法,构成了一棵排列树。树的结点表示女运动员,排列树的层数表示男运动员,经过算法处理后,输出符合最优值的编号。算例结果显示:男1号和女1号组合、男2号和女3号组合,男3号和女2号组合,竞赛优势最大。该算法简便、易懂,又有比较好的实用性和技巧性。

1、问题描述

羽毛球队有男女运动员各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] 。设计一个算法,计算男女运动员最佳配对法,使各组男女双方竞赛优势的总和达到最大。

2、问题分析

该问题输出为男女人员的搭配问题,由于运动员不能重复选择,因此,此问题的解空间树是一个排列树,可以使用排列树回溯法模板进行算法设计。
假设n为羽毛球队有男女运动员数量,P[i][j] 是男运动员i 和女运动员j 配对组成混合双打的男运动员竞赛优势;Q[i][j] 是女运动员i 和男运动员j 配合的女运动员竞赛优势
本题采用的是男运动员选女运动员的方法,这样就构成了一棵排列树。G表示女运动员,排列树的层数表示男运动员。
下面考虑剪枝函数,因为当人员没有选完时,不确定最终结果是否优于最优解,所以回溯过程中不需要剪枝函数进行剪枝,只有当一条分支运行到叶子结点时,才需要判断可行解于最优解的关系,考虑是否更新最优解。
最后考虑输出结果,输出结果应该时是包含运动员编号的集合,用x[i]表示,原数组存放初始编号,经过算法处理后,输出符合最优值的编号。

3、算法设计

首先将第 i 位男运动员与第 j 位女运动员的优势计算到二维数组j[ i ][ j ] 中,然后再在这个二维数组选 n 个组合(组合即对应每个点(i , j)),要求 n 个点不可同行或同列,将 n 个这样子符合条件的点求和,记录最大值。
第 i 层回溯对应第 i 位男运动员,该层回溯中应该选取一位没有被选择过的女运动员。为了记录女运动员是否被选择过,我们创建数组 x[ i ] 来记录,依次累加每一层的优势。当 i > n 时即为回溯的终点,此时更新最大的优势和。

4、程序代码

#include <stdio.h>
#include <stdlib.h>int if_OK(int c[], int K){  // 判断是否为一个解
int i,flag;
int arr[21] = {0};
for(i = 1; i <= K; i++){
arr[c[i]] += 1;}for(i = 1, flag = 1; i <= K; i++){if(arr[i] != 1){flag = 0;break;}}return flag;
}int is_part(int c[], int K){ // 判断是否为部分解int i, flag;int arr[21] = {0};for(i = 1; i <= K; i++){arr[c[i]] += 1;}for(i = 1, flag = 0; i <= K; i++){ // 这里与 if_OK 有区别if(arr[i] > 1){  flag = 0;break;}else if(arr[i] == 0){flag = 1;}}return flag;
}int func(int c[], int f[21][21], int K){ // 计算该解情况下,男女运动员竞赛优势的总和int i, count = 0;for(i = 1; i <= K; i++){count += f[i][c[i]];}return count;
}int main()
{    int i, j;int N;scanf("%d", &N);int p[21][21], q[21][21], f[21][21]; // p 记录男运动员的竞赛优势、 q记录女运动员的、 f是男女运动员匹配后的 。并且数组都是从 1开始的。for(i = 1; i <= N; i++){for(j = 1; j <= N; j++){scanf("%d", &(p[i][j]));}}for(i = 1; i <= N; i++){for(j = 1; j <= N; j++){scanf("%d", &(q[i][j]));f[j][i] = q[i][j] * p[j][i]; // 注意此处f、 p、 q的数组下标 !!!}}int com[21] = {0}; // 用来记录男女队员的匹配, com【i】中的 i 代表男队员、com【i】代表女队员int k = 1, tmp = 0, count = 0; //k队员编号,tmp是当前解的优势值, count是最优的优势值while(k >= 1 && k <= N){ // 注意 k <= Nwhile(com[k] <= N){com[k] = com[k] + 1;if(if_OK(com, N)){ // 表示该com【】为一组解tmp = func(com, f, N);if(tmp > count) count = tmp; // 记录最优解break;}else if(is_part(com, N)) k = k+1; // 部分解}com[k] = 0;k = k-1;}printf("%d" , count);return 0;
}

5、运行结果

假设n为羽毛球队有男女运动员数量,P[i][j] 是男运动员i 和女运动员j 配对组成混合双打的男运动员竞赛优势;Q[i][j] 是女运动员i 和男运动员j 配合的女运动员竞赛优势
在这里插入图片描述
本题采用的是男运动员选女运动员的方法,这样就构成了一棵排列树。G表示女运动员,排列树的层数表示男运动员。如第一层的G1=20表示,男运动员1号选女运动员1号的男女双方竞赛优势为20。
在这里插入图片描述

6、运行结果分析

输出结果应该时是运动员编号的集合,用x [i]表示,原数组存放初始编号,经过算法处理后,输出符合最优值的编号。
由排列树和输出结果可知,采用男运动员选女运动员的策略,其解空间是{(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)}竞赛优势最大为20+20+12=52,最优集合编号为x={1,3,2},即男1号和女1号组合、男2号和女3号组合,男3号和女2号组合,竞赛优势最大。时间复杂度分析:算法要动态的生成排列树,在每个节点处花费O(1)的时间,排列树中结点的个数为n!,因此,算法的时间复杂度为O(n!)。

这篇关于【算法设计与分析】回溯法解决运动员配对问题(课程设计)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

linux生产者,消费者问题

pthread_cond_wait() :用于阻塞当前线程,等待别的线程使用pthread_cond_signal()或pthread_cond_broadcast来唤醒它。 pthread_cond_wait() 必须与pthread_mutex 配套使用。pthread_cond_wait()函数一进入wait状态就会自动release mutex。当其他线程通过pthread

问题:第一次世界大战的起止时间是 #其他#学习方法#微信

问题:第一次世界大战的起止时间是 A.1913 ~1918 年 B.1913 ~1918 年 C.1914 ~1918 年 D.1914 ~1919 年 参考答案如图所示

2024.6.24 IDEA中文乱码问题(服务器 控制台 TOMcat)实测已解决

1.问题产生原因: 1.文件编码不一致:如果文件的编码方式与IDEA设置的编码方式不一致,就会产生乱码。确保文件和IDEA使用相同的编码,通常是UTF-8。2.IDEA设置问题:检查IDEA的全局编码设置和项目编码设置是否正确。3.终端或控制台编码问题:如果你在终端或控制台看到乱码,可能是终端的编码设置问题。确保终端使用的是支持你的文件的编码方式。 2.解决方案: 1.File -> S

vcpkg安装opencv中的特殊问题记录(无法找到opencv_corexd.dll)

我是按照网上的vcpkg安装opencv方法进行的(比如这篇:从0开始在visual studio上安装opencv(超详细,针对小白)),但是中间出现了一些别人没有遇到的问题,虽然原因没有找到,但是本人给出一些暂时的解决办法: 问题1: 我在安装库命令行使用的是 .\vcpkg.exe install opencv 我的电脑是x64,vcpkg在这条命令后默认下载的也是opencv2:x6

在线装修管理系统的设计

管理员账户功能包括:系统首页,个人中心,管理员管理,装修队管理,用户管理,装修管理,基础数据管理,论坛管理 前台账户功能包括:系统首页,个人中心,公告信息,论坛,装修,装修队 开发系统:Windows 架构模式:B/S JDK版本:Java JDK1.8 开发工具:IDEA(推荐) 数据库版本: mysql5.7 数据库可视化工具: navicat 服务器:SpringBoot自带 ap

[职场] 公务员的利弊分析 #知识分享#经验分享#其他

公务员的利弊分析     公务员作为一种稳定的职业选择,一直备受人们的关注。然而,就像任何其他职业一样,公务员职位也有其利与弊。本文将对公务员的利弊进行分析,帮助读者更好地了解这一职业的特点。 利: 1. 稳定的职业:公务员职位通常具有较高的稳定性,一旦进入公务员队伍,往往可以享受到稳定的工作环境和薪资待遇。这对于那些追求稳定的人来说,是一个很大的优势。 2. 薪资福利优厚:公务员的薪资和

问题-windows-VPN不正确关闭导致网页打不开

为什么会发生这类事情呢? 主要原因是关机之前vpn没有关掉导致的。 至于为什么没关掉vpn会导致网页打不开,我猜测是因为vpn建立的链接没被更改。 正确关掉vpn的时候,会把ip链接断掉,如果你不正确关掉,ip链接没有断掉,此时你vpn又是没启动的,没有域名解析,所以就打不开网站。 你可以在打不开网页的时候,把vpn打开,你会发现网络又可以登录了。 方法一 注意:方法一虽然方便,但是可能会有

DDei在线设计器-API-DDeiSheet

DDeiSheet   DDeiSheet是代表一个页签,一个页签含有一个DDeiStage用于显示图形。   DDeiSheet实例包含了一个页签的所有数据,在获取后可以通过它访问其他内容。DDeiFile中的sheets属性记录了当前文件的页签列表。   一个DDeiFile实例至少包含一个DDeiSheet实例。   本篇最后提供的示例可以在DDei文档直接预览 属性 属性名说明数

代码随想录算法训练营:12/60

非科班学习算法day12 | LeetCode150:逆波兰表达式 ,Leetcode239: 滑动窗口最大值  目录 介绍 一、基础概念补充: 1.c++字符串转为数字 1. std::stoi, std::stol, std::stoll, std::stoul, std::stoull(最常用) 2. std::stringstream 3. std::atoi, std

基于Springboot + vue 的抗疫物质管理系统的设计与实现

目录 📚 前言 📑摘要 📑系统流程 📚 系统架构设计 📚 数据库设计 📚 系统功能的具体实现    💬 系统登录注册 系统登录 登录界面   用户添加  💬 抗疫列表展示模块     区域信息管理 添加物资详情 抗疫物资列表展示 抗疫物资申请 抗疫物资审核 ✒️ 源码实现 💖 源码获取 😁 联系方式 📚 前言 📑博客主页: