运动员最佳配对问题实验报告.docx
- 文档编号:14570270
- 上传时间:2023-06-24
- 格式:DOCX
- 页数:14
- 大小:83.45KB
运动员最佳配对问题实验报告.docx
《运动员最佳配对问题实验报告.docx》由会员分享,可在线阅读,更多相关《运动员最佳配对问题实验报告.docx(14页珍藏版)》请在冰点文库上搜索。
运动员最佳配对问题实验报告
2011-2012第二学期
《算法设计与分析》期末考核
项目名称:
运动员最佳配对问题
1.项目描述(10分)
羽毛球队有男女运动员各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.算法设计(10分)
方法一:
优先队列式分支限界法
具体算法:
算法开始时创建一个最大堆,用于表示活结点优先队列
堆中每个结点的val值是优先队列的优先级。
接着算法计算出图中每个顶点的最大val。
如果搜索到所搜索的排列树的叶子节点,算法即告结束。
方法二:
回溯法
具体算法:
套用排列树框架,做好初始化后开始回溯,关键在于到达叶子节点时,需要计算当前的总和csum+=p[i][w[i]]*q[w[i]][i],若发现csum比之前的最优值大,则更新最优值和配对顺序,回溯完成后则可得到最大总和及其相应的运动员配对方法让男队员按自己编号顺序站定,女运动员和他们搭配的各种组合就是女运动员的各种排列。
因此,搜索的解空间树是“排列树”。
用回溯法搜索排列树的算法框架:
voidbacktrack(intt)
{
if(t>n)
output(x);
else
for(inti=f(n,t);i<=g(n,t);i++)
{
x[t]=h(i);
if(constraint(t)&&bound(t))backtrack(t+1);
}
}
程序(50分)
方法一:
分支限界法程序
#include
#include
#defineHeapSize60
typedefstruct
{
intn;//男运动员个数
int**p;//男运动员竞赛优势
int**q;//女运动员竞赛优势
}Sport;
typedefstruct
{
intw[20];//一种排列
intt;//已排到的位数
intval;//此种排列的配对和
}Node;
typedefstructminheap
{
intlast;//此时的元素个数
intmaxsize;//堆中的元素最大个数
Node*heep;
}Minheap,*Heap;
//建大根堆
voidMaxHeapInit(Heap&H)
{
H=(Heap)malloc(sizeof(Minheap));
H->maxsize=HeapSize;
H->last=0;
H->heep=(Node*)malloc((H->maxsize+1)*sizeof(Node));
}
//插入大根堆
voidHeapInsert(Nodex,HeapH)
{
inti;
if(H->last==H->maxsize)
{
printf("堆已满!
!
\n");
exit(0);
}
i=++H->last;
while(i!
=1&&x.val>H->heep[i/2].val)
{
H->heep[i]=H->heep[i/2];
i/=2;
}
H->heep[i]=x;
}
//取大根堆的根,并保持堆的性质
voidDeleteMax(HeapH,Node*x)
{
inti,ci;
Nodey;
if(H->last==0)
{
printf("空堆\n");
exit(0);
}
*x=H->heep[1];
y=H->heep[H->last--];
i=1;
ci=2;
while(ci<=H->last)
{
if(ci
ci++;
if(H->heep[ci].val break; H->heep[i]=H->heep[ci]; i=ci; ci*=2; } H->heep[i]=y; } //计算配对和 voidCompute(Sport&S,Node&T) { T.val=0; for(inti=0;i T.val+=S.p[i][T.w[i]]*S.q[T.w[i]][i]; } //主干函数 voidBacktrack(Sport&S) { NodefNode,sNode;//fNode为父节点,sNode为子节点 HeapH; inti,best=0;//最大的配对和 MaxHeapInit(H); for(i=0;i fNode.w[i]=i; fNode.t=0; fNode.val=0; HeapInsert(fNode,H); while(H->last! =0)//当堆为空时结束循环 { DeleteMax(H,&fNode); if(fNode.t==S.n-1)//为一个全排列时,比较节点内值是否比当前最优值更佳 { if(best best=fNode.val; } else { for(i=fNode.t;i { sNode=fNode; sNode.t++; sNode.w[sNode.t]=fNode.w[i]; sNode.w[i]=fNode.w[sNode.t]; Compute(S,sNode);//计算节点的val HeapInsert(sNode,H); } } } printf("最大配对总和为: %d\n",best); } //构造运动员结构体 voidSetSport(Sport&S) { inti,j; printf("请输入男运动员或女运动员的人数: "); scanf("%d",&S.n); S.p=(int**)malloc(S.n*sizeof(int)); S.q=(int**)malloc(S.n*sizeof(int)); if(S.p==NULL||S.q==NULL) { printf("内存分配失败! ! \n"); exit(-1); } for(i=0;i { S.p[i]=(int*)malloc(S.n*sizeof(int)); S.q[i]=(int*)malloc(S.n*sizeof(int)); if(S.p[i]==NULL||S.q[i]==NULL) { printf("内存分配失败! ! \n"); exit(-1); } } printf("请输入男运动员对女运动员的竞赛优势: \n"); for(i=0;i for(j=0;j scanf("%d",&S.p[i][j]); printf("请输入女运动员对男运动员的竞赛优势: \n"); for(i=0;i for(j=0;j scanf("%d",&S.q[i][j]); } //释放申请的堆空间 voidDestroy(Sport&S) { inti; for(i=0;i { free(S.p[i]); free(S.q[i]); } free(S.p); free(S.q); S.q=S.p=NULL; } intmain(void) { SportS; SetSport(S); Backtrack(S); Destroy(S); return0; } 方法二: 回溯法程序 #include #include typedefstruct { int**p;//男运动员竞赛优势 int**q;//女运动员竞赛优势 int*w;//排列编号 int*best;//最好的排列编号 intn;//男运动员个数 intbestsum;//最好的配对和 }Sport; voidSwap(int&a,int&b) { intt; t=a; a=b; b=t; } //计算运动员的配对和 voidCompute(Sport&S) { intsum=0; for(inti=0;i sum+=S.p[i][S.w[i]]*S.q[S.w[i]][i]; if(sum>S.bestsum) { S.bestsum=sum; for(inti=0;i S.best[i]=S.w[i];//保存最好的排列编号 } } //主干函数 voidBacktrack(intt,Sport&S) { if(t>=S.n) Compute(S); else for(inti=t;i { Swap(S.w[t],S.w[i]); Backtrack(t+1,S); Swap(S.w[t],S.w[i]); } } //释放申请的堆空间 voidDestroy(Sport&S) { inti; for(i=0;i { free(S.p[i]); free(S.q[i]); } free(S.p); free(S.q); free(S.best); free(S.w); S.q=S.p=NULL; S.best=S.w=NULL; } //构造运动员结构体 voidSetSport(Sport&S) { inti,j; printf("请输入男运动员或女运动员的人数: "); scanf("%d",&S.n); S.p=(int**)malloc(S.n*sizeof(int)); S.q=(int**)malloc(S.n*sizeof(int)); S.w=(int*)malloc(S.n*sizeof(int)); S.best=(int*)malloc(S.n*sizeof(int)); if(S.p==NULL||S.q==NULL||S.w==NULL||S.best==NULL) { printf("内存分配失败! ! \n"); exit(-1); } for(i=0;i { S.w[i]=i; S.p[i]=(int*)malloc(S.n*sizeof(int)); S.q[i]=(int*)malloc(S.n*sizeof(int)); if(S.p[i]==NULL||S.q[i]==NULL) { printf("内存分配失败! ! \n"); exit(-1); } } printf("请输入男运动员对女运动员的竞赛优势: \n"); for(i=0;i for(j=0;j scanf("%d",&S.p[i][j]); printf("请输入女运动员对男运动员的竞赛优势: \n"); for(i=0;i for(j=0;j scanf("%d",&S.q[i][j]); } //输出最好的配对结果 voidOutput(Sport&S) { inti; for(i=0;i printf("第%d号男运动员配第%d号女运动员\n",i,S.best[i]); printf("最大配对总和为: %d\n",S.bestsum); } intmain(void) { SportS; SetSport(S); Backtrack(0,S); Output(S); Destroy(S); return0; } 3.程序运行结果(10分) 分支限界法程序运行结果: 回溯法程序运行结果: 4.算法时间复杂度分析(20分) 方法一中回溯法,用到的是递归的进行深度优先搜索整个排列树;算法中没有剪枝函数和限界函数,算法的时间复杂度为o(n! );复杂度很高,方法二中用的是分支限界法对排列树进行广度优先搜索,算法的时间复杂度有所降低。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运动员 最佳 配对 问题 实验 报告