分枝界定法和匈牙利法算法和源代码Word文档下载推荐.docx
- 文档编号:4275366
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:28
- 大小:61.89KB
分枝界定法和匈牙利法算法和源代码Word文档下载推荐.docx
《分枝界定法和匈牙利法算法和源代码Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《分枝界定法和匈牙利法算法和源代码Word文档下载推荐.docx(28页珍藏版)》请在冰点文库上搜索。
i++)
for(j=0;
j<
b;
j++)
for(k=0;
k<
c;
k++)
for(l=0;
l<
d;
l++)
if(Is_Total(i,j,k,l,n))
{
sum[i]=func(i,j,k,l)+
func0(Is_Zero(i),Is_Zero(j),Is_Zero(k),Is_Zero(l));
cout<
<
"
"
<
sum="
sum[i]<
endl;
}
inttemp=sum[0];
//设立标志位
for(intm=0;
m<
size;
m++)
if(sum[m]<
temp&
&
sum[m]!
=0)//从所有解中找出最小值
temp=sum[m];
returntemp;
/*主函数*/
int_tmain(intargc,_TCHAR*argv[])
intn,Result;
//定义总人数和结果
inta,b,c,d;
//定义每一个限制人数
cout<
Enterthenumbersofthepeople:
"
;
cin>
>
n;
Enterthepeopleofeveryhospital:
a>
b>
c>
Result=Branch(a,b,c,d,n);
TheMincostis"
Result<
cin.get();
return0;
说明:
此题结果为无穷多解,计算机无法在短时间内计算出最优解。
匈牙利分派法
根据匈牙利分派法,矩阵经过一系列简单处理后得到各行、各列均有零元素的矩阵后,判断并得到n个独立零元素,为分派问题的最优解。
第一步,变换矩阵使每行每列都至少出现一个零元素。
第二步,试派,寻找独立的零元素。
若同行(列)有两个以上的零元素,则循环试派,直到一定次数后,再分别处理同行(列)多个零元素,直到每行每列都只有小于等于1个的零元素。
(划零元素在程序中表示为-1)
第三步,累加零元素个数为m。
若m=n,则得到最优解,停止。
零元素对应的xij=1,其余为0。
若m<
n,转向第四步。
第四步,作最少的覆盖零元素的直线,以确定最多的独立零元素个数。
第五步,累加划出的覆盖零元素的直线数为l。
若l<
n,转第六步。
若l=n,而m<
n,说明试派不成功,转向第二步,重新试派。
第六步,变换系数,在不出现负元素的前提下增加零元素的个数。
解题步骤如下:
第一问、运输费用最少的运输方案。
任务
汽车
A
B
C
D
E
1
110
125
143
105
128
2
132
197
218
162
207
3
87
286
107
95
78
4
114
155
198
243
1、虚拟汽车5,取所有任务最小值。
5
2、取零元素
9
23
45
57
30
75
188
17
21
55
14
129
27
3、划零和取独立零元素
-1
4、划线及变换系数重新取零元素
19
31
43
16
61
7
41
115
5、重新分派
6、得到结果
第一辆汽车完成任务2,第二辆汽车完成任务1,第三辆汽车完成任务35,第四辆汽车完成任务4。
总费用为125+132+107+78+128=570
第二问、利润最高的运输方案。
1、矩阵变号,虚拟汽车5,取所有最小值
-110
-125
-143
-105
-128
-132
-197
-218
-162
-207
-87
-286
-107
-95
-78
-114
-155
-198
-243
18
15
53
11
166
179
153
208
96
88
77
121
68
86
4、线数为4<
5,零元也为4<
5,划线及变换系数重新取零元素
64
123
136
165
131
25
6、线数为4<
5,必须再次变换系数重新取零元素
89
98
111
85
140
156
7、重新分派
8、线数为4<
5,继续变换系数重新取零元素
104
80
93
67
122
174
35
9、重新分派
10、得到结果
车1完成任务A,汽车2完成任务C、D,汽车3完成任务B,汽车4完成任务E,此时的最大利润为:
110+218+162+286+243=1019元
constintsize=10;
constintMax=65535;
constintsign=-1;
intr,c,flag;
//定义行列以及求最大最小值标志
/*初始系数矩阵*/
intA[size][size]={{110,125,143,105,128},
{132,197,218,162,207},
{87,286,107,95,78},
{114,155,198,128,243}};
intB[size][size];
//参与运算矩阵
intMinR[size];
//求反最小值
intMinC[size];
//求列最小值
intRow[size]={0};
//记录打钩的行
intCol[size]={0};
//记录打钩的列
/*打印矩阵*/
voidOut_print()
inti,j;
r;
{
cout<
B[i][j]<
\t"
cout<
}
/*获得矩阵行数*/
voidGet_Row()
inti=0;
while(A[i][0]!
='
\0'
)
i++;
r=i;
/*获得矩阵列数*/
voidGet_Col()
while(A[0][i]!
c=i;
/*任务分配模式选择*/
intMod()
intflag;
if(r==c)//行列数相等时
flag=2;
elseif(r<
c)//列数大于行数时
flag=1;
else
flag=0;
//行数大于列数时
returnflag;
/*获得行最小值*/
voidFind_RMin()
inti,j,temp;
temp=B[i][0];
for(j=1;
if(B[i][j]<
temp)//找到一行中最小值赋给标志位
temp=B[i][j];
MinR[i]=temp;
//将一行中最小值赋给MinR数组
/*获得列最小值*/
voidFind_CMin()
for(j=0;
temp=B[0][j];
for(i=1;
temp)//找到一列中最小值赋给标志位
MinC[j]=temp;
//将一列中最小值赋给MinR数组
/*矩阵变换函数*/
voidMatrix_ExChange()
inti,j,temp0,temp1;
/*矩阵转置*/
for(j=i+1;
{
temp0=B[j][i];
B[j][i]=B[i][j];
B[i][j]=temp0;
temp1=A[j][i];
A[j][i]=A[i][j];
A[i][j]=temp1;
}
/*矩阵调整函数*/
voidSqMatrix_Improve()
B[i][j]=A[i][j];
//将初始矩阵赋给运算矩阵
if(flag==1)//若求最大值则将矩阵全部变号,转换为求最小值
for(i=0;
for(j=0;
{
B[i][j]=-B[i][j];
A[i][j]=-A[i][j];
}
Find_RMin();
//获得行最小值
Find_CMin();
//获得列最小值
if(Mod()==2);
//行列数相等则什么也不做
//行数小于列数时把列最小值放到列末尾与原矩阵合并成增广矩阵
elseif(Mod()==1)
B[r][i]=MinC[i];
A[r][i]=MinC[i];
r=r+1;
//重新调整行数
else//行数大于于列数时把一维零矩阵放到行末尾与原矩阵合并成增广矩阵
B[i][c]=0;
A[i][c]=0;
c=c+1;
//重新调整列数
Matrix_ExChange();
//合并后进行矩阵转置
//此处可以添加限制条件代码
//B[4][0]=Max;
//B[3][3]=Max;
Out_print();
//输出调整后的矩阵
/*行零元素获得函数*/
voidGet_RZero()
//重新获得行最小值
B[i][j]-=MinR[i];
//每一行减去行最小值得到零元
/*列零元素获得函数*/
voidGet_CZero()
//重新获得列最小值
{
//当该列存在零元时跳出内循环继续寻找没有零元的列
if(B[j][i]==0)
break;
if(j==r)
B[j][i]-=MinC[i];
//每一列减去列最小值得到零元
/*重新分派函数*/
voidReturn_Assignment()
//将被赋予被划去的零元(-1代表被划去的零元)重置
if(B[i][j]==sign)
B[i][j]=0;
/*零元素累加函数*/
intCount_Zero()
inti,j,count=0;
if(0==B[i][j])
count++;
returncount;
/*试分派函数*/
voidTry_Assignment()
inti,j,k,row,col,num=0;
intcount=0,flag=0;
intcountr=0,countc=0;
while(!
flag&
num<
r)//进行r次循环,当全部行列的单个零元处理完后跳出
if(B[i][j]==0)//对行零元数目累加
count++;
if(count==1)//行零元只有一个时处理该零元所在列的其他零元
for(j=0;
if(B[i][j]==0)//获得该行零元的坐标
row=i;
col=j;
break;
for(k=0;
k++)//将该零元所在列的其他零元划掉
if(k!
=row&
B[k][col]==0)
B[k][col]=sign;
count=0;
//重置累加器
if(B[j][i]==0)//对列零元数目累加
if(count==1)//列零元只有一个时处理该零元所在行的其他零元
if(B[j][i]==0)//获得该列零元的坐标
row=j;
col=i;
k++)//将该零元所在行的其他零元划掉
=col&
B[row][k]==0)
B[row][k]=sign;
{
j++)//计算每一行零元是否都只有一个
if(B[i][j]==0)
countr++;
if(countr==1)//只有一个零元,重置累加器
countr=0;
if(countr>
1)//大于一个零元则跳出循环
if(countr==0)//当每行零元都只有一个时,对列零元进行处理
for(i=0;
if(B[j][i]==0)//计算每一列零元是否都只有一个
countc++;
if(countc==1)//只有一个零元,重置累加器
countc=0;
if(countc>
break;
//行列零元都只有一个时表示单个零元处理完毕同时多零元行也因为分派转换为单零元
if(countc==0)
flag=1;
//当行列零元总存在大于一个时继续分派并累加次数
if(countr>
1||countc>
1)
countr=0;
countc=0;
num++;
//当单个零元都处理完毕后,再对剩下的无法进行分派的多零元行进行处理
i++)//先进行行零元处理
if(B[i][j]==0)
if(count>
1)
if(B[i][j]==0)//获得该行第一个零元的坐标
{
row=i;
col=j;
}
k++)//对该零元所在列的其他零元进行处理
if(k!
B[k][col]=sign;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 分枝 界定 匈牙利 算法 源代码
![提示](https://static.bingdoc.com/images/bang_tan.gif)