分配问题——匹配.ppt

吨间题一配
制作:重庆大学龚劬
d要角容
训
〖引例:车辆调度问题
基本概念
最大权匹配算法
Kuhn- munkras算法的 MATLAB程序
自编函数 maxmatch的用法
匚k
应用:引例的求解
引例:车辆调度问题
设某车队有8辆车,存放在不同的地点,队长要派出
其中5辆到5个工地去运货。各车从存放处调到装货地点所
需费用列于下页表,问应选哪5辆车调到何处去运货,才
能使各车从车所在地点调到装货地点所需的总费用最少?
5
7
8
3025183227192226
2931
19
18
2829301919222
2519
18
20
1817
16
引例:车辆调度问题
地点组12345678
3025183227192226
31
1918
19
2519
18
20
181716
16
y
8
基本櫬倉
匹配:图G=(VE)中一些互不相邻的边构成的集合M,称
为G的一个匹配;M中边的端点称为M渗透点;V中的其余顶点
称为M非渗透点。
理想匹配:若匹配M渗透了图G的所有顶点,则称M为G
的理想匹配
最大匹配:若匹配M是G中边数最多的匹配,则称M为G
的最大匹配
·M可增长路径:设M是图G=(vE)的一个匹配,P是G中
的一条路径。若P的边在M与E-M中交替出现,则称P是一条M
交错路径;若一条M交错路径的起点和终点都是M非渗透点,
则称其为M可增长路径。
基本櫬倉
最大权匹配:在加权二部图G中,边权和最大的
匹配M称为G的最大权匹配。
二部图的边矩阵A:A=(a)mn
「1当x:与y相邻,
0当x,与y;不相邻
二部图的边权矩阵A:A=(a1)mxn,a;为边
(x,y)的权,若x;与y之间无边,则a;取0
大匹配算依
●可容顶点标:vv∈V(G定义一个标记v)≥0满足
l(x)+(y)≥w(xy)
则称(v〕是二部图的可容顶点标。
二部图的边矩阵A:A=(an)mwn
二部图的边权矩阵A:A=(a1})mxm,a1;为边
y)的权,若x1与y之间无边,则a;取0
Kuhn- Munkres算法步骤:(略)
7程序—Ruhn-wha算法
function sum=kuhngong(A)
M=zeros(n, 2)
n=size (A, 1); W=A; I=zeros(n, 2);
for i=1: n
for i=1: n
if (FLAG AGL(j==i&(M(,2))
1)<W(j)
M(,1)=i;M(j2)=i;
d
end
end
end
end
FLAG AGL=zeros(n, n)
FLAG3=1:
G S=zeros(1, n)
while Flag
FLAG T=zeros (1, n)
FLAG3=0
FLAG_NGLS=Zeros(1, n); f=zeros(n, 2)
for i=1: n
for j=1: n
f~M(i,1)
FLAG_ AGL(D=i;
break.
end
end
end
d
Y7绍程序—又ih-wka算法(续)
while FLAG4
fprintf(1二部图最大权匹配运行结果n")
for i=1:n
fprintf(1;n求得最大权匹配M={方
if FLAG S(i
sum=0
for j=1: r
if FLAG aGl(d==i
for i=1
FLAG_ NGLS()
nd, end. endend
fprintf(1, X%ody/od, i,j)
FLAG_ EQU=l
sum=sum+w(ij; break;
for i=1: n
end
if FLAG NGLS(N=FLAGT(
FLAG_ EQU=0; break;
fprintf(1, \ n)
FLAG4=0: al=inf
fprint(4最大权W(M)=% g\ sum);
if FLAG EQU
return
A65520
if(FLAG_S()&(w FLAG_T()
temp=l(i, 1 )+0, 2)-w(ij)
s(1n)
if al>temp
FLAG4=1
end, end, end, end
7拓程序—Rhn- mankera算法(续)
if M(y, 2)
%/0%start
for z=1: n
(,1)=(i,1)a;
if(FLAG AGL(z,y==z)&(M(Y, 2)==z)
end, end
FLAG_S(