devbox
代码探险家
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

多智能体（机器人）任务分配问题求解AssignmentProblem_多智能体任务分配

作者：代码探险家 | 2024-08-09 14:14:01

赞

踩

多智能体任务分配

问题提出：
N个智能体，现在有个任务，就是让N个智能体要到N个目标位置，目标位置不能重复，目标位置与机器人一一对应，要使得期间所有所走的距离之和最短，求解最优任务分配。

在这里插入图片描述

问题抽象：
有N个师父， N个徒弟，每个徒弟只能选者一个师父学习, 每个师父只能带一个徒弟; 每个师父有自己的技能,每个徒弟有自己学习的天分, 当徒弟 j 在师父 i 门下学习, 产生效益为 Aij, 问如何安排使得总效益最大？

求解过程：

定义数据格式：
m i : 第 i 个 师 父 , i = 1 , 2 , 3 , ⋯ , n m_i: 第 i 个师父, i=1,2,3,⋯,n mi​:第i个师父,i=1,2,3,⋯,n
t j : 第 j 个 徒 弟 , j = 1 , 2 , 3 , ⋯ n , t_j: 第 j 个徒弟,j=1,2,3,⋯n, tj​:第j个徒弟,j=1,2,3,⋯n,
x i j : 第 j 个 徒 弟 是 否 在 第 i 个 师 父 门 下 学 习 : 1 , 是 ; 2 不 是 . x_{ij}: 第j 个徒弟是否在第i 个师父门下学习: 1, 是; 2 不是. xij​:第j个徒弟是否在第i个师父门下学习:1,是;2不是.
a i j : 第 j 个 徒 弟 在 第 i 个 师 父 门 下 学 习 产 生 的 效 益 . a_{ij}:第j 个徒弟在第i 个师父门下学习产生的效益. aij​:第j个徒弟在第i个师父门下学习产生的效益.

数学模型：

y = m a x ∑ i = 1 n a i j . x i j ( 式 0 ) y=max \sum_{i=1}^n a_{ij}.x_{ij} { ( 式0)} y=maxi=1∑n​aij​.xij​(式0)
∑ i = 1 n x i j = 1 , ∀ j = 1 , 2 , 3 , ⋯ , n ( 式 1 ) \sum_{i=1}^n x_{ij} =1 , \forall j=1,2,3,⋯,n { ( 式1)} i=1∑n​xij​=1,∀j=1,2,3,⋯,n(式1)
∑ j = 1 n x i j = 1 , ∀ i = 1 , 2 , 3 , ⋯ , n ( 式 2 ) \sum_{j=1}^n x_{ij} =1 , \forall i=1,2,3,⋯,n { ( 式2)} j=1∑n​xij​=1,∀i=1,2,3,⋯,n(式2)

x i j ∈ { 0 , 1 } ∀ i = 1 , 2 , 3 , ⋯ , n ; j = 1 , 2 , 3 , ⋯ , n ( 式 3 ) x_{ij} \in {\lbrace0,1}\rbrace \forall i=1,2,3,⋯,n;j=1,2,3,⋯,n (式3) xij​∈{0,1}∀i=1,2,3,⋯,n;j=1,2,3,⋯,n(式3)

  • 式0 为目标函数, 即最大化总效益；
  • 式1 表示一个师父只能带一个徒弟；
  • 式2 表示一个徒弟只能跟一个师父学习；
  • 式3表示师父-徒弟分配是原子操作，要么分配要么不分配。

在这个抽象的例子中，我们把
师父    ⟺    \iff ⟺智能体（机器人）
徒弟    ⟺    \iff ⟺要去的目标位置位置
效益    ⟺    \iff ⟺智能体（机器人）当前位置与目标位置二者之间距离

当然这个例子中是求最小，师父徒弟的例子是求最大，道理是一样的。

匈牙利算法

解决分配问题最常用的是匈牙利算法。

按照知乎上某位博主的支付报酬、矩阵求解思路：

若从指派问题的系数矩阵的某行（列）各元素中分别减去或者加上常数k，其最优任务分解问题不变。

这里是引用

通过寻找“0”元素巧妙得出0报酬的指派思路：
给出的代码如下：

#include <stdio.h>
typedef struct matrix
{
	int cost[101][101];
	int zeroelem[101][101];
 	int costforout[101][101];
 	int matrixsize;
}MATRIX;
MATRIX hungary;
int result[5041][2];								//用来储存解的结果,第一列表示工人第二列表示工件 
void zeroout(MATRIX &hungary);						//减去行列的最小值得到零元素 
void circlezero(MATRIX &hungary);					//圈出单行列零元素 
void twozero(MATRIX &hungary);						//圈出行列存在两个以上的零元素 
void judge(MATRIX &hungary,int result[2000][2]);	//判断是否符合匈牙利算法条件 
void refresh(MATRIX &hungary);						//不符合条件，对矩阵进行变形 
void output(int result[2000][2],MATRIX hungary);	//结果输出 
MATRIX input();										//初始输入 
int main()
{
	result[0][0]=0;
	hungary=input();
	zeroout(hungary);
	circlezero(hungary); 
	output(result,hungary);
}
MATRIX input()
{
	int i,j; 
	matrix hungary;
	printf("指派问题的匈牙利解法\n");
	printf("请输入cost矩阵的阶数:\n");
	scanf("%d",&hungary.matrixsize);
	printf("请输入代表工人和工件的%d阶矩阵:\n",hungary.matrixsize);
	for(i=1;i<=hungary.matrixsize;i++)
  		for(j=1;j<=hungary.matrixsize;j++)
  		{   
 			scanf("%d",&hungary.cost[i][j]);
 			hungary.costforout[i][j]=hungary.cost[i][j];
  		}

 	return hungary;
}
void zeroout(MATRIX &hungary)
{
	int i,j; 
	int tem;	//表示同行的最大元素或同列的最大元素 
	for(i=1;i<=hungary.matrixsize;i++)             //减去同行最大元素
 	{ 
  	 	tem=hungary.cost[i][1];
  	 	for(j=2;j<=hungary.matrixsize;j++)
    	if(hungary.cost[i][j]<tem)
    		tem=hungary.cost[i][j];
  		for(j=1;j<=hungary.matrixsize;j++)
   		hungary.cost[i][j]=hungary.cost[i][j]-tem;
 	}
 	for(j=1;j<=hungary.matrixsize;j++)            //减去同列最大元素
 	{
  		tem=hungary.cost[1][j];
  		for(i=2;i<=hungary.matrixsize;i++)
     	if(hungary.cost[i][j]<tem)
    		tem=hungary.cost[i][j];
  		for(i=1;i<=hungary.matrixsize;i++)
  			hungary.cost[i][j]=hungary.cost[i][j]-tem;
 	}
}
void circlezero(MATRIX &hungary)
{
	int i,j,p;  
	int flag; 
 	for(i=0;i<=hungary.matrixsize;i++)                         //在矩阵外面构建半圈矩阵标记0的个数；
  		hungary.cost[i][0]=0; 
 	for(j=1;j<=hungary.matrixsize;j++)
  		hungary.cost[0][j]=0;
 	for(i=1;i<=hungary.matrixsize;i++)
  		for(j=1;j<=hungary.matrixsize;j++)
   		if(hungary.cost[i][j]==0)
   		{
    		hungary.cost[i][0]++;
    		hungary.cost[0][j]++;
    		hungary.cost[0][0]++;
   		} 
 	for(i=0;i<=hungary.matrixsize;i++)               //新建一个矩阵
  		for(j=0;j<=hungary.matrixsize;j++)           
   			hungary.zeroelem[i][j]=0;   
 	flag=hungary.cost[0][0]+1;                         //flag = 0的总个数+1
	while(hungary.cost[0][0]<flag)                   
	{
  		flag=hungary.cost[0][0];                                       //行列单0的情况，
  		for(i=1;i<=hungary.matrixsize;i++)                             //第一遍先行后列
	 	{
   			if(hungary.cost[i][0]==1) 
			{
				for(j=1;j<=hungary.matrixsize;j++)                        
     			if(hungary.cost[i][j]==0&&hungary.zeroelem[i][j]==0)
      				break;
    			hungary.zeroelem[i][j]=1;
    			hungary.cost[i][0]--;
   		 		hungary.cost[0][j]--;
    			hungary.cost[0][0]--;
    			if(hungary.cost[0][j]>0)
     			for(p=1;p<=hungary.matrixsize;p++)
      			if(hungary.cost[p][j]==0&&hungary.zeroelem[p][j]==0)
      			{
       				hungary.zeroelem[p][j]=2;
       				hungary.cost[p][0]--;
       				hungary.cost[0][j]--;
       				hungary.cost[0][0]--;
      			}      
			}                           
	
  		}
		for(j=1;j<=hungary.matrixsize;j++)                            //   第二遍先列后行
 		{
   			if(hungary.cost[0][j]==1)
			{
		    	for(i=1;i<=hungary.matrixsize;i++)
     			if(hungary.cost[i][j]==0&&hungary.zeroelem[i][j]==0)
      				break;
    			hungary.zeroelem[i][j]=1;
    			hungary.cost[i][0]--;
    			hungary.cost[0][j]--;
    			hungary.cost[0][0]--;
    			if(hungary.cost[i][0]>0)
     			for(p=1;p<=hungary.matrixsize;p++)
      			if(hungary.cost[i][p]==0&&hungary.zeroelem[i][p]==0)
      			{
       				hungary.zeroelem[i][p]=2;
       				hungary.cost[i][0]--;
       				hungary.cost[0][p]--;
       				hungary.cost[0][0]--;
      			}
			}
  		}
	}
	if(hungary.cost[0][0]>0)
		twozero(hungary);
	else
		judge(hungary,result);
}
void judge(MATRIX &hungary,int result[5041][2])
{
	int i,j;
 	int num=0;	//线的条数 
 	int start;	//每组解的储存开始位置 
 	for(i=1;i<=hungary.matrixsize;i++)
  		for(j=1;j<=hungary.matrixsize;j++)
   		if(hungary.zeroelem[i][j]==1)
    		num++;						//划线的条数 
		if(num==hungary.matrixsize)
		{
  			start=result[0][0]*hungary.matrixsize+1;
   			for(i=1;i<=hungary.matrixsize;i++)
    			for(j=1;j<=hungary.matrixsize;j++)
     				if(hungary.zeroelem[i][j]==1)
     				{
      					result[start][0]=i;
      					result[start++][1]=j;
     				}
   					result[0][0]++;
  		}
 		else
  			refresh(hungary);
}
void twozero(MATRIX &hungary)
{
	int i,j;
	int p,q;
	int m,n;
	int flag;
    MATRIX backup;
	for(i=1;i<=hungary.matrixsize;i++)
		if(hungary.cost[i][0]>0)
			break;
	if(i<=hungary.matrixsize)
	{
		for(j=1;j<=hungary.matrixsize;j++)
		{
			backup=hungary;//备份以寻找多解 
			if(hungary.cost[i][j]==0&&hungary.zeroelem[i][j]==0)
			{
    			hungary.zeroelem[i][j]=1;
    			hungary.cost[i][0]--;
    			hungary.cost[0][j]--;
    			hungary.cost[0][0]--;
    			for(q=1;q<=hungary.matrixsize;q++)
     				if(hungary.cost[i][q]==0&&hungary.zeroelem[i][q]==0)
     				{
      					hungary.zeroelem[i][q]=2;
      					hungary.cost[i][0]--;
      					hungary.cost[0][q]--;
      					hungary.cost[0][0]--;
     				}
    			for(p=1;p<=hungary.matrixsize;p++)
     				if(hungary.cost[p][j]==0&&hungary.zeroelem[p][j]==0)
     				{
      					hungary.zeroelem[p][j]=2;
      					hungary.cost[p][0]--;
      					hungary.cost[0][j]--;
      					hungary.cost[0][0]--;
     				}
    			flag=hungary.cost[0][0]+1;
    			while(hungary.cost[0][0]<flag)
    			{
     				flag=hungary.cost[0][0];
     				for(p=i+1;p<=hungary.matrixsize;p++)
     				{
     			 		if(hungary.cost[p][0]==1)
						{
       						for(q=1;q<=hungary.matrixsize;q++)
        						if(hungary.cost[p][q]==0&&hungary.zeroelem[p][q]==0)
         							break;
       							hungary.zeroelem[p][q]=1;
       							hungary.cost[p][0]--;
       							hungary.cost[0][q]--;
       							hungary.cost[0][0]--;
       						for(m=1;m<=hungary.matrixsize;m++)
        						if(hungary.cost[m][q]==0&&hungary.zeroelem[m][q]==0)
        						{
        			 				hungary.zeroelem[m][q]=2;
         							hungary.cost[m][0]--;
         							hungary.cost[0][q]--;
         							hungary.cost[0][0]--;
        						}
      					}
     				}
     				for(q=1;q<=hungary.matrixsize;q++)
     				{
      					if(hungary.cost[0][q]==1)
						{
       						for(p=1;p<=hungary.matrixsize;p++)
        						if(hungary.cost[p][q]==0&&hungary.zeroelem[p][q]==0)
         							break;
       							hungary.zeroelem[p][q]=1;
       							hungary.cost[p][q]--;
       							hungary.cost[0][q]--;
       							hungary.cost[0][0]--;
       						for(n=1;n<=hungary.matrixsize;n++)
        						if(hungary.cost[p][n]==0&&hungary.zeroelem[p][n]==0)
								{
         							hungary.zeroelem[p][n]=2;
         							hungary.cost[p][0]--;
         							hungary.cost[0][n]--;
         							hungary.cost[0][0]--;
        						}
      					}
     				}
    			}
    			if(hungary.cost[0][0]>0)                   //确保hungary.cost[][]中的0元素都在zeroelem[][]中被完全标记出来。
     				twozero(hungary);
    			else 
     				judge(hungary,result);
   			}           
   			hungary=backup;
  		}
 	}
}
void refresh(MATRIX &hungary)
{
	int i,j,min=0;
	int flag1=0,flag2=0;
	for(i=1;i<=hungary.matrixsize;i++)
	{
		for(j=1;j<=hungary.matrixsize;j++)
		if(hungary.zeroelem[i][j]==1)
		{
			hungary.zeroelem[i][0]=1;         //有独立零元素
    		break;
   		}
	}
	while(flag1==0)
	{
		flag1=1;
		for(i=1;i<=hungary.matrixsize;i++)
			if(hungary.zeroelem[i][0]==0)
			{
				hungary.zeroelem[i][0]=2;
				for(j=1;j<=hungary.matrixsize;j++)
					if(hungary.zeroelem[i][j]==2)
					{
						hungary.zeroelem[0][j]=1;
					}
   			}
		for(j=1;j<=hungary.matrixsize;j++)
		{
			if(hungary.zeroelem[0][j]==1)
			{
				hungary.zeroelem[0][j]=2;
				for(i=1;i<=hungary.matrixsize;i++)
    				if(hungary.zeroelem[i][j]==1)
					{
						hungary.zeroelem[i][0]=0;
      					flag1=0;
     				}
   			}
  		}
 	}                    //对打勾的行和列标记成2 
	for(i=1;i<=hungary.matrixsize;i++)
	{
		if(hungary.zeroelem[i][0]==2)
		{
			for(j=1;j<=hungary.matrixsize;j++)
			{
    			if(hungary.zeroelem[0][j]!=2)
     				if(flag2==0)
     				{
     				 	min=hungary.cost[i][j];
      					flag2=1;
     				}
     			else
				{
      				if(hungary.cost[i][j]<min)
       					min=hungary.cost[i][j];
     			}
   			}        
  		}
 	}					//寻找未被覆盖的最小值 
	for(i=1;i<=hungary.matrixsize;i++)
	{
		if(hungary.zeroelem[i][0]==2)
			for(j=1;j<=hungary.matrixsize;j++)
				hungary.cost[i][j]=hungary.cost[i][j]-min;
	}
	for(j=1;j<=hungary.matrixsize;j++)
	{
		if(hungary.zeroelem[0][j]==2)
			for(i=1;i<=hungary.matrixsize;i++)
				hungary.cost[i][j]=hungary.cost[i][j]+min;
	}                   //未被划线的行减去未被覆盖的最小值，被划线的列加上未被覆盖的最小值 
	for(i=0;i<=hungary.matrixsize;i++)
		for(j=0;j<=hungary.matrixsize;j++)
			hungary.zeroelem[i][j]=0;              //矩阵清0
	circlezero(hungary); 
}
void output(int result[5041][2],MATRIX hungary)
{
	int num;	//解的数量 
	int minsum;	//最小的工作成本 
	int i,j;
	char w;
	int start;  //每个解的储存开始位置 
	minsum=0;
	for(i=1;i<=hungary.matrixsize;i++)
	{
		minsum=minsum+hungary.costforout[i][result[i][1]];
	}
	printf("最优解的目标函数值为%d.\n",minsum);
	num=result[0][0];
  	printf("有%d种解.\n",num);  
	getchar();
	for(i=1;i<=num;i++)
	{
		printf("按任意键输出第%d种解.\n",i);
		scanf("%c",&w);
		start=(i-1)*hungary.matrixsize+1;	 
		for(j=start;j<start+hungary.matrixsize;j++)
    			printf("第%d个人做第%d件工作.\n",result[j][0],result[j][1]);
 		printf("\n");
 	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236
  • 237
  • 238
  • 239
  • 240
  • 241
  • 242
  • 243
  • 244
  • 245
  • 246
  • 247
  • 248
  • 249
  • 250
  • 251
  • 252
  • 253
  • 254
  • 255
  • 256
  • 257
  • 258
  • 259
  • 260
  • 261
  • 262
  • 263
  • 264
  • 265
  • 266
  • 267
  • 268
  • 269
  • 270
  • 271
  • 272
  • 273
  • 274
  • 275
  • 276
  • 277
  • 278
  • 279
  • 280
  • 281
  • 282
  • 283
  • 284
  • 285
  • 286
  • 287
  • 288
  • 289
  • 290
  • 291
  • 292
  • 293
  • 294
  • 295
  • 296
  • 297
  • 298
  • 299
  • 300
  • 301
  • 302
  • 303
  • 304
  • 305
  • 306
  • 307
  • 308
  • 309
  • 310
  • 311
  • 312
  • 313
  • 314
  • 315
  • 316
  • 317
  • 318
  • 319
  • 320
  • 321
  • 322
  • 323
  • 324
  • 325
  • 326
  • 327
  • 328
  • 329
  • 330
  • 331
  • 332
  • 333
  • 334
  • 335
  • 336
  • 337
  • 338
  • 339
  • 340
  • 341
  • 342
  • 343
  • 344
  • 345
  • 346
  • 347
  • 348
  • 349
  • 350
  • 351
  • 352
  • 353
  • 354
  • 355
  • 356
  • 357
  • 358
  • 359

参考

Assignment Problem（任务分配问题） 详解
Cmd Markdown 公式指导手册
十分钟教你求解分配问题
匈牙利算法详解

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号