文档库 最新最全的文档下载
当前位置:文档库 › 图的匹配——匈牙利算法与KM算法

图的匹配——匈牙利算法与KM算法

图的匹配——匈牙利算法与KM算法
图的匹配——匈牙利算法与KM算法

图的匹配

一、什么是图的匹配

1.图的定义

无向图:无向图G 是指非空有限集合V G ,和V G 中某些元素的无序对的集合E G ,构成的二元组(V G ,E G )。V G 称为G 的顶点集,其中的元素称为G 的顶点。E G 称为G 的边集,其中的元素称为G 的边。在不混淆的情况下,有时记V =V G ,E =E G 。如果V ={v 1,…,v n },那么E 中的元素e 与V 中某两个元素构成的无序对(v i ,v j )相对应,记e =v i v j ,或e =v j v i 。在分析问题时,我们通常可以用小圆圈表示顶点,用小圆圈之的连线表示边。

二分图:设G 是一个图。如果存在V G 的一个划分X ,Y ,使得G 的任何一条边的一个端点在X 中,另一个端点在Y 中,则称G 为二分图,记作G =(X ,Y ,E)。如果G 中X 的每个顶点都与Y 的每个顶点相邻,则称G 为完全二分图。

2.匹配的相关概念

设G =(V ,E)是一个图,E M ?,如果M 不含环且任意两边都不相邻,则称M 为G 的一个匹配。G 中边数最多的匹配称为G 的最大匹配。

对于图G =(V ,E),在每条边e 上赋一个实数权w(e)。设M 是G 的一个匹配。定义∑∈=m

e e w M w )()(,并称之为匹配M 的权。G 中权最大的匹配称为G 的最大权匹配。如果

对一切,e ∈E ,w(e)=1,则G 的最大权匹配就是G 的最大匹配。

设M 是图G=(V ,E)的一个匹配,v i ∈V 。若v i 与M 中的边相关联,则称v i 是M 饱和点,否则称v i 为M 非饱和点。

如果G 中每个顶点都是M 饱和点,则称M 为G 的完美匹配。

设M 是G 的一个匹配,P 是G 的一条链。如果P 的边交替地一条是M 中的边,一条不是M 中的边,则称P 为M 交错链。类似地,我们可以定义G 的交错圈。易知,G 的交错圈一定是偶圈。

一条连接两个不同的M 非饱和点的M 交错链称为M 增广链。

两个集合S 1与S 2的“异或”操作S 1⊕S 2是指集合S 1⊕S 2=(S 1∩S 2)\(S 1∪S 2) 容易看出,设M 是G 的匹配,P 是G 中的M 增广链、则M ⊕P 也是G 的匹配,而且1+=⊕M P M 。

图表 1 “异或”操作

可以证明,G 中匹配M 是最大匹配当且仅当G 中没有M 增广链。

二、匹配算法

1.二分图的最大匹配

设有M个工人x1, x2, …, x m,和N项工作y1, y2, …, y n,规定每个工人至多做一项工作,而每项工作至多分配一名工人去做。由于种种原因,每个工人只能胜任其中的一项或几项工作。问应怎样分配才能使尽可能多的工人分配到他胜任的工作。这个问题称为人员分配问题。

人员分配问题可以用图的语言来表述。令X={x1, x2, …, x m},Y={y1, y2, …,y n},构造二分图G=(X, Y, E)如下:

对于1≤i≤m,1≤j≤n,当且仅当工人x

i 胜任工作y

i

时,G中有一条边x

i

y

i

,于是人

员分配问题就成为在G中求一个最大匹配的问题。

求最大匹配常用匈牙利算法,它的基本思想是:对于已知的匹配M,从X中的任一选定的M非饱和点出发,用标号法寻找M增广链。如果找到M增广链,则M就可以得到增广;否则从X中另一个M非饱和点出发,继续寻找M增广链。重复这个过程直到G中不存在增广链结束,此时的匹配就是G的最大匹配。这个算法通常称为匈牙利算法,因为这里介绍的寻找增广链的标号方法是由匈牙科学者Egerváry最早提出来的。

图表2 匈牙利算法

理解了这个算法,就不难写出人员分配问题的解答了。在给出程序之前,先做一些假设:

为了简单起见,假设工人数等于工作数,即N=M,且N≤100,这里,N也可以看作是二分图的|X|和|Y|。

数据从文件input.txt中读入,首先是N和|E|,下面|E|行每行两个数(I, J),表示工人I 可以胜任工作J,即二分图中的边x i y j。

结果输出到文件output.txt,第一行是最大匹配数s,下面s行每行两个数(I, J),表示分配工人I做工作J,即匹配边x i y j。

下面是人员分配问题的参考解答,该算法的时间复杂度为O(n3)。

Program match;

const

maxn = 100;

var

map: array[1 .. maxn, 1 .. maxn] of boolean; {保存二分图} cover: array[1 .. maxn] of boolean; {标记一个点是否为饱和点} link: array[1 .. maxn] of integer; {保存匹配边}

n: integer; {顶点数}

procedure init; {读入}

var

i, e, x, y: integer;

begin

assign(input, 'input.txt'); reset(input);

readln(n, e);

for i := 1 to e do begin

readln(x, y); map[x, y] := true;

end;

close(input);

end;

function find(i: integer): boolean; {从i出发,找增广链}

var

k, q: integer;

begin

find := true;

for k := 1 to n do

if map[i, k] and not cover[k] then begin

q := link[k]; link[k] := i; cover[k] := true;

if (q = 0) or find(q) then exit;

link[k] := q;

end;

find := false;

end;

procedure main; {求匹配}

var

i: integer;

begin

for i := 1 to n do begin

fillchar(cover, sizeof(cover), 0);

find(i);

end;

end;

procedure print; {输出}

var

i, s: integer; begin

assign(output, 'output.txt'); rewrite(output);

s := 0; for i := 1 to n do if link[i] <> 0 then s := s + 1; writeln(s);

for i := 1 to n do if link[i] <> 0 then writeln(link[i], ' ', i); close(output); end;

begin init; main; print; end.

2.二分图的最大权匹配

对于上面的人员分配问题,如果还考虑到工人做工的效率,就可以提出所谓的分派问题:应该怎样分配才能使总的效率最大?

同上一节,我们可以构造一个二分图G ,如果把工人x i 做工作y i 的效率w ij 看作是G 中边x i y i 的权,则分派问题就相当于在赋权二分图G 中求一个最大全匹配。

由线性规划的知识,求二分图G 的最大权匹配,只需在匈牙利算法的基础上少许改进

即可。它的基本思想是,对二分图的顶点编号,然后根据编号构造一个新的二分图G ’

,最

后把求G 的最大权匹配转换为求G ’

的完美匹配。

下面的这条定理是这个算法的理论基础。

定理:设M 是赋权图(权非负)的完全二分图),,,(w E Y X G =的一个完美匹配,这里Y X =。如果存在一组},{j i μλ,满足),,2,1,(,n j i w ij j i =≥+μλ,并且对一切

M y x j i ∈,均有ij j i w =+μλ,则M 是G 的最大权匹配。

下面,给出求最大权匹配的程序。输入文件中首先是N 和|E|,下面|E|行每行三个数(I, J, W),表示工人I 做工作J 的效率是W 。程序输出包括每个工人的选择和最后的总效益。其它假设参见上一节的算法假设。这个算法的时间复杂度也是O(n 3)。

Program maxmatch; const

maxn = 100; var

map: array[1 .. maxn, 1 .. maxn] of integer; {保存二分图}

link, lx, ly: array[1 .. maxn] of integer; {保存匹配边和每个点的标号} x, y: array[1 .. maxn] of boolean; {标记一个点是否为饱和点} n: integer; {顶点数}

procedure init; {读入} var

i, e, x, y: integer; begin

assign(input, 'input.txt'); reset(input);

for i := 1 to e do readln(x, y, map[x, y]);

close(input);

end;

function find(v: integer): boolean; {从v出发,找增广链} var

i, k: integer;

begin

find := true;

x[v] := true;

for i := 1 to n do

if not y[i] and (lx[v] + ly[i] = map[v, i]) then begin

y[i] := true; k := link[i]; link[i] := v;

if (k = 0) or find(k) then exit;

link[i] := k;

end;

find := false;

end;

procedure main; {求最大权匹配}

var

i, j, k, d: integer;

begin

fillchar(lx, sizeof(lx), 0); fillchar(ly, sizeof(ly), 0);

for i := 1 to n do

for j := 1 to n do

if map[i, j] > lx[i] then lx[i] := map[i, j];

for k := 1 to n do

repeat

fillchar(x, sizeof(x), 0); fillchar(y, sizeof(y), 0);

if find(k) then break;

d := maxint;

for i := 1 to n do if x[i] then

for j := 1 to n do if not y[j] then

if lx[i] + ly[j] - map[i, j] < d then

d := lx[i] + ly[j] - map[i, j];

for i := 1 to n do if x[i] then lx[i] := lx[i] - d;

for i := 1 to n do if y[i] then ly[i] := ly[i] + d;

until false;

end;

procedure print; {输出}

var

i, s: integer;

begin

assign(output, 'output.txt'); rewrite(output);

s := 0;

for i := 1 to n do s := s + map[link[i], i];

close(output);

end;

begin

init;

main;

print;

end.

3. 任意图的匹配

任意图的最大匹配算法也是建立在找增广链的基础上的,只是任意图的增广链要比二分图难找得多。这个算法比较复杂,竞赛中也很少用到,因此,这里就不做详细介绍了。

三、匹配的应用

1. 匹配与一一对应

问题:FJOI-信封问题

John先生晚上写了n封信,并相应地写了n个信封将信装好,准备寄出。但是,第二天John的儿子Small John将这n封信都拿出了信封。不幸的是,Small John无法将拿出的信正确地装回信封中了。

将Small John所提供的n封信依次编号为1,2,…,n;且n个信封也依次编号为1,2,…,n。假定Small John能提供一组信息:第i封信肯定不是装在信封j中。请编程帮助Small John,尽可能多地将信正确地装回信封。其中n≤100。

例如,有4封信,而且第一封信不是装在信封1、2和3中,第2封信不是装在信封2和3中,则可以确定的第一封信装在信封4中,而且第二封信则装在信封1中。但这些条件还不足以确定第三封和第四封信的位置。

分析:

看了这道题目,感觉上和小学数学竞赛中的逻辑推理题如出一辙,而逻辑推理题的做法一般是表上作业法。

就以前面的例子为例,根据条件,可以得到如下信息:

由于每一行每一列都应该只有一个√,因此,可以确定第一封信装在信封4中,于是可以得到:

然后,发现第二行有3个×,因此剩下一个肯定是√,于是就可以得出第二封信则装在信封1中:

现在,第3行和第4行都只有两个×,因此无法确定它们放在那个信封里。

这样我们就得到了一个初步的算法:在程序中建立一个二维表格,首先,根据条件填入若干个×,然后,检查所有还未确定的行和列,看有没有一行(列)中有n –1个×,如果没有,就结束;否则,把剩下的那一个空格填上√,并且填了√的那一行(列)的其它位置都填上×。

这种方法虽然很容易想到,但却有针对这个方法的反例,例如:

图表3 一个反例

图中上半部分的顶点表示“信”,下半部分的顶点表示“信封”,如果信i可能放在信封j中,则在信i和信封j之间连一条边。由于每个顶点的度数都大于或等于2,即每行每列都至少有两个空位,故前面的算法无法进行任何推理,而事实却并非如此,比如说中间的那封信就只能放在中间的那个信封里。

正是这个反例,使我们需要另辟蹊径。进一步分析可以发现,信和信封之间的关系,是一种一一对应的关系,这是因为一封信只能放到一个信封里,而一个信封也只能装一封信。而从信息学的角度来看,这种一一对应的关系,也可以看作是二分图的匹配关系。

令X={x1, x2, …, x m},Y={y1, y2, …,y n},构造二分图G=(X, Y, E),当且仅当信i可以

放到信封j中,G中存在边x i y j。这样,任何一种信的分配方案,都可以看作是图G的一个完美匹配。例如上图就有且仅有如下两种完美匹配:

图表 4 所有的完美匹配

由于中间的那条匹配边在两个完美匹配中都出现了,因此我们认为这条匹配边是“确定的”,换句话说,这条边所代表的关系也是确定的。容易看出,当且仅当对于G的所有完美匹配M,都存在一条匹配边x i y j,则可以确定信i可以放到信封j中。

这样,我们就从匹配的角度建立了一个新的模型。那么,这个模型要如何求解呢?

我们当然不能枚举出G所有的完美匹配,然后再去求它们边的交集——这和搜索就没什么分别。在这里,我们需要对这个模型再做一个小小的转换:我们发现,条件“对于G 的所有完美匹配M,都存在一条匹配边x i y j”,等价于“如果图G存在完美匹配,而删除图G中的一条边x i y j得到的图G’中却不存在完美匹配”。例如,左下图删除了一条“关键边”,故不存在完美匹配,而右下图删除的是一条“非关键边”,故存在完美匹配。

图表5 删边的例子

从表面上看,这个算法的时间复杂度似乎仍然很高。因为图G中最多有n2条边,每次试着删除一条边,又需要O(n3)的时间复杂度求一次完美匹配。总的复杂度高达O(n5)。

实际上,我们可以先找到图G的一个完美匹配M,这样,删边就只需考虑匹配边了(因为删除非匹配边得到G’,M仍然是G’的完美匹配)。这样,只需删除n条边,时间复杂度就降到了O(n4)。

再进一步分析,删除一条边以后,没有必要重新找完美匹配,只需检查可不可以找到新的增广链就可以了。这样,时间复杂度就进一步降到了O(n3)。

下面给出该题的参考程序。

program letter;

const

finp = 'input.txt';

fout = 'output.txt';

maxn = 100;

var

n, x, y: integer;

map: array[1 .. maxn, 1 .. maxn] of boolean;

link, cover: array[1 .. maxn] of integer;

function path(i: integer): boolean; {找增广轨}

var

k, p: integer;

begin

result := true;

for k := 1 to n do

if (cover[k] = 0) and map[i, k] then begin

p := link[k]; link[k] := i; cover[k] := 1;

if (p = 0) or path(p) then exit;

link[k] := p;

end;

result := false;

end;

begin

assign(input, finp); reset(input); assign(output, fout); rewrite(output);

readln(n);

fillchar(map, sizeof(map), true);

repeat

readln(x, y);

if x + y = 0 then break;

map[y, x] := false;

until false;

fillchar(link, sizeof(link), 0);

for x := 1 to n do begin

fillchar(cover, sizeof(cover), 0);

path(x);

end;

for x := 1 to n do begin

y := link[x]; link[x] := 0;

map[y, x] := false; fillchar(cover, sizeof(cover), 0);

if not path(y) then begin

link[x] := y; writeln(x, ' ', y);

end;

map[y, x] := true;

end;

close(output); close(input);

end.

2. “完美”的最大权匹配

问题:CTSC-丘比特的烦恼

随着社会的不断发展,人与人之间的感情越来越功利化。最近,爱神丘比特发现,爱情也已不再是完全纯洁的了。这使得丘比特很是苦恼,他越来越难找到合适的男女,并向他们射去丘比特之箭。于是丘比特千里迢迢远赴中国,找到了掌管东方人爱情的神——月下老人,向他求教。

月下老人告诉丘比特,纯洁的爱情并不是不存在,而是他没有找到。在东方,人们讲

究的是缘分。月下老人只要做一男一女两个泥人,在他们之间连上一条红线,那么它们所代表的人就会相爱——无论他们身处何地。而丘比特的爱情之箭只能射中两个距离相当近的人,选择的范围自然就小了很多,不能找到真正的有缘人。

丘比特听了月下老人的解释,茅塞顿开,回去之后用了人间的最新科技改造了自己的弓箭,使得丘比特之箭的射程大大增加。这样,射中有缘人的机会也增加了不少。

情人节(Valentine's day)的午夜零时,丘比特开始了自己的工作。他选择了一组数目相等的男女,感应到他们互相之间的缘分大小,并依次射出了神箭,使他们产生爱意。他希望能选择最好的方法,使被他选择的每一个人被射中一次,且每一对被射中的人之间的缘分的和最大。

当然,无论丘比特怎么改造自己的弓箭,总还是存在缺陷的。首先,弓箭的射程尽管增大了,但毕竟还是有限的,不能像月下老人那样,做到“千里姻缘一线牵”。其次,无论怎么改造,箭的轨迹终归只能是一条直线,也就是说,如果两个人之间的连线段上有别人,那么莫不可向他们射出丘比特之箭,否则,按月下老人的话,就是“乱点鸳鸯谱”了。

作为一个凡人,你的任务是运用先进的计算机为丘比特找到最佳的方案。

输入文件第一行为正整数k,表示丘比特之箭的射程,第二行为正整数n(n<30),随后有2n行,表示丘比特选中的人的信息,其中前n行为男子,后n行为女子。每个人的信息由两部分组成:他的姓名和他的位置。姓名是长度小于20且仅包含字母的字符串,忽略大小写的区别,位置是由一对整数表示的坐标,它们之间用空格分隔。格式为Name x y。输入文件剩下的部分描述了这些人的缘分。每一行的格式为Name1 Name2 p。Name1和Name2为有缘人的姓名,p是他们之间的缘分值(p为小于等于255的正整数)。以一个End 作为文件结束标志。每两个人之间的缘分至多只被描述一次。如果没有被描述,则说明他们缘分值为1。

输出文件仅一个正整数,表示每一对被射中的人之间的缘分的总和。这个和应当是最大的。

分析:

题目中出现了三类物体和两种关系,我们一个个的来分析:

丘比特的箭,它有一个属性是射程,

男人和女人,他们的属性包括名字和位置,

男人和女人之间的关系,这个关系是他们俩的缘分值,

箭与男女的关系,如果两人的距离不超过箭的射程,并无他人阻挡,则可能被箭射中。题目就是要求一种射箭的方案,使得所有被射中的男女的缘分和最大。

这个问题很像是要求一个二分图的最大权匹配。因为男人和女人分属两个集合,而且同性之间没有任何关系,因此是一个二分图。而把缘分值记做边上的权,则缘分和最大,就对应了这个二分图中的一个最大权匹配。

要注意的是,题目中虽然说明没有被描述的男女之间缘分值为1,但这并不代表所得到的二分图是完全二分图。因为在构图的过程中,我们必须还考虑到箭的射程等因素——如果两人的距离超过了箭的射程,则他俩注定无缘了。

这时问题就来了,因为题目中除了要求缘分和最大之外,还要求“被丘比特选择的每一个人都要被射中一次”。

你可能会觉得,要缘分和越大,当然被射中的人越多越好,其实并不是这样。例如:

图表6 一个反例

如果要求最大权匹配,则会选择匹配边AD,缘分和为10。但由于每个人都要被射中一次,因此我们只能选择AC和BD,缘分和为2。

换句话说,对于这个例子,正确答案应该是2,而最大权匹配的值却是10。这说明,这道题目和简单的最大权匹配还是有区别的,因为题目再要求权值最大的同时,还要求是一个完美匹配,我们称之为“完美”的最大权匹配。

那么,这道题是否就不能用最大权匹配来做了呢?先别急,我们再来回顾一下求最大权匹配的算法:我们通过对顶点编号, 将图G转化为G’,然后在把求G的最大权匹配转换为求G’的完美匹配——这里好像就是求完美匹配,但对于上面的那个例子,又为什么不呢?

原来,对于上面的例子,在标号过后,新的图G’中加入了一条新的边BC,而这条边的权值是0,在图G’中的完美匹配,实际上是AD和BC,对应到图G中,就是边AD了。

因此,如果我们预先把BC的边的权值设为-∞,再求图中的最大权匹配,就不会再有问题了。

更一般的,如果要求二分图的“完美”的最大权匹配,只需将原图中没有的边的权值设为-∞,就可以了。

下面给出这道题目的程序。

program cupid;

const

finp = 'cupid.in';

fout = 'cupid.out';

maxn = 30;

type

Tperson = record

x, y: integer;

name: string;

end;

Tpersons = array[1 .. maxn] of Tperson;

var

len, n, i, j, k, d: integer;

line, nl, nr: string;

man, woman: Tpersons;

lx, ly, link: array[1 .. maxn] of integer;

map: array[1 .. maxn, 1 .. maxn] of byte;

cx, cy: array[1 .. maxn] of boolean;

function same(const A, B: string): boolean; {判断AB是否相等}

var

i: integer;

begin

result := false;

if length(A) <> length(B) then exit;

for i := 1 to length(A) do if upcase(A[i]) <> upcase(B[i]) then exit;

result := true;

end;

function find(const p: Tpersons; const name: string): integer; {找编号} begin

result := n;

while (result > 0) and not same(p[result].name, name) do result := result - 1; end;

function path(i: integer): boolean; {找增广轨}

var

k, p: integer;

begin

result := true;

cx[i] := true;

for k := 1 to n do

if not cy[k] and (map[i, k] = lx[i] + ly[k]) and (map[i, k] > 0) then begin

cy[k] := true; p := link[k]; link[k] := i;

if (p = 0) or path(p) then exit;

link[k] := p;

end;

result := false;

end;

function inside(A, B, P: Tperson): boolean; {判断P是否挡住AB}

begin

A.x := A.x - P.x; A.y := A.y - P.y;

B.x := B.x - P.x; B.y := B.y - P.y;

result := (A.x * B.y = A.y * B.x) and ((A.x * B.x < 0) or (A.y * B.y < 0)); end;

begin

assign(input, finp); reset(input); assign(output, fout); rewrite(output); readln(len, n);

for i := 1 to n do readln(man[i].x, man[i].y, man[i].name);

for i := 1 to n do readln(woman[i].x, woman[i].y, woman[i].name);

fillchar(map, sizeof(map), 1);

repeat

readln(line);

if line = 'End' then break;

i := pos(' ', line); nl := ' ' + copy(line, 1, i - 1); delete(line, 1, i);

i := pos(' ', line); nr := ' ' + copy(line, 1, i - 1); delete(line, 1, i);

i := find(man, nl); j := find(woman, nr);

if (i = 0) or (j = 0) then begin

i := find(man, nr); j := find(woman, nl);

end;

val(line, map[i, j], k);

until false;

for i := 1 to n do for j := 1 to n do begin

if sqr(man[i].x - woman[j].x) + sqr(man[i].y - woman[j].y) >

sqr(len) then map[i, j] := 0;

for k := 1 to n do

if (i <> k) and inside(man[i], woman[j], man[k]) or

(j <> k) and inside(man[i], woman[j], woman[k]) then map[i, j] := 0;

end;

fillchar(lx, sizeof(lx), 0); fillchar(ly, sizeof(ly), 0);

for i := 1 to n do for j := 1 to n do

if map[i, j] > lx[i] then lx[i] := map[i, j];

fillchar(link, sizeof(link), 0);

for k := 1 to n do

repeat

fillchar(cx, sizeof(cx), 0); fillchar(cy, sizeof(cy), 0);

if path(k) then break;

d := maxint;

for i := 1 to n do if cx[i] then for j := 1 to n do if not cy[j] then

if (map[i, j] > 0) and (lx[i] + ly[j] - map[i, j] < d) then

d := lx[i] + ly[j] - map[i, j];

for i := 1 to n do if cx[i] then lx[i] := lx[i] - d;

for i := 1 to n do if cy[i] then ly[i] := ly[i] + d;

until false;

len := 0; for i := 1 to n do len := len + map[link[i], i];

writeln(len);

close(output); close(input);

end.

3. 稀疏图的匹配

问题:IPSC-Magic

一个著名的魔术师上台表演,跟着他的是一位漂亮的女助手。魔术师先从他的魔术帽中拽出了几只兔子,接着他又从女助手的围巾中变出了一束鲜花,最后,他把女助手锁在一个看上去空着的箱子里。然后,魔术师选了一个观众来配合一个表演:他在一个桌子上摆出N张牌(所有N张牌两两不同,且N为奇数)。魔术师让这位自愿者走上讲台从中选出(N+1)/2张牌,其余的牌都在魔术师的帽子里永远的消失了。魔术师在选出的牌上方晃了晃手,接着他选出其中一张交给那一位自愿者,自愿者向观众展示了手中的这张牌,随后又将其藏在自己的衣袋里。那位女助手从箱子里放出来后,来到桌前也在剩下的(N +1)/2-1张牌上方晃了晃手,马上就说出了自愿者衣袋中的是什么牌。

表格 4

其中,自愿者选的牌-魔术师选的牌=助手所看到的牌。表中包括了自愿者选牌的所有可能性,它们两两不同。而助手所看到的牌,也是两两不同的。

首先,魔术师和他的助手都要记住这张表。这样,当助手看到的牌是2,4时,她就可以肯定自愿者选的牌是2,4,5,且魔术师选的牌就是5。

现在,告诉你n 的值,要你求出这张表。其中n ≤15。

分析:

为了便于分析,我们令M 表示从N 张牌中选取(N +1)/2张牌的方案数,显然,从这N 张牌中选出(N +1)/2-1张牌的方案数也是M 。

我们先从枚举的角度入手,下面给出两种枚举的方法: 对于自愿者的每种选牌的方案,枚举魔术师所选的牌。 对于自愿者的每种选牌的方案,所对应的助手看到的牌。

方案一需要M 次决策,每次决策中有N 种选择;方案二同样需要M 次决策,而每次决策的可以有M 种选择。从这点上来看,方案一要好得多。、

可是方案一所表现出来的“自愿者的选牌的方案”和“魔术师所选的牌”之间的关系并不是一一对应的关系,对于自愿者不同的选牌的方案,魔术师可以选择相同的牌。

而方案二中所表现出的关系正是一一对应的关系,因为题目要求对于自愿者不同的选牌的方案,助手看到的牌必须不同。

前面已经提到过,从信息学的角度来看,一一对应,也可以看作是一种二分图的匹配的关系。因此,方案二更容易让人联系到匹配。

令X=自愿者的选牌的方案集,Y=助手看到的牌的集合,构造二分图G=(X, Y , E),当且仅当1=-?j i i j Y X X Y 且时,G 中存在边x i y j 。这样,就把原问题转换成求图G 的一个完美匹配。

下面问题又来了。首先,二分图的顶点高达2M 个,当N=15时,M 接近8000,而求匹配的复杂度为O(M 3),这样高的复杂度,如何能够承受?

注意到这个图是一个稀疏图,一共只有MN 条边。而稀疏二分图匹配的复杂度也可以表示成O(|V|×|E|)。因此,时间复杂度应该是O(M 2N),基本上可以承受了。

另外,由于这是稀疏图,我们用邻接表来存储,则空间复杂度仅为O(NM),同样可以承受。

最后要说明的是,这道题目也可以用构造法以获得更好的效率,但不如匹配容易想到。具体的构造方法这里就不给出了,读者可以自己想一想。

下面给出参考程序:

program magic;

const

n = 15;

half = (n + 1) shr 1;

m = 8000;

var

map: array[1 .. m, 0 .. half] of integer;

link: array[1 .. m] of integer;

cover: array[1 .. m] of boolean;

bits: array[1 .. n] of integer;

index: array[0 .. 1 shl n - 1] of integer;

i, sum: integer;

procedure buildA(d, p, x: integer); {建图}

var

i: integer;

begin

if d = half then begin

sum := sum + 1; index[x] := sum;

exit;

end;

for i := p + 1 to n do buildA(d + 1, i, x or bits[i]); end;

procedure buildB(d, p, x: integer); {建图}

var

i, k: integer;

begin

if d > half then begin

sum := sum + 1; map[sum, 0] := x; k := 0;

for i := 1 to n do

if x and bits[i] <> 0 then begin

k := k + 1; map[sum, k] := index[x - bits[i]];

end;

exit;

end;

for i := p + 1 to n do buildB(d + 1, i, x xor bits[i]); end;

function path(i: integer): boolean; {找增广轨}

var

k, p, v: integer;

begin

result := true;

for k := 1 to half do begin

v := map[i, k];

if not cover[v] then begin

p := link[v]; link[v] := i; cover[v] := true;

if (p = 0) or path(p) then exit;

link[v] := p;

end;

end;

result := false;

end;

procedure show(d, p, x: integer); {输出}

var

i, k: integer;

begin

if d = half then begin

sum := sum + 1; k := map[link[sum], 0] xor x;

for i := 1 to n do if bits[i] and (x + k) <> 0 then write(i, ' ');

for i := 1 to n do if bits[i] = k then writeln('-> ', i);

exit;

end;

for i := p + 1 to n do show(d + 1, i, x xor bits[i]);

end;

begin

for i := 1 to n do bits[i] := 1 shl (i - 1);

sum := 0; buildA(1, 0, 0); sum := 0; buildB(1, 0, 0);

fillchar(link, sizeof(link), 0);

for i := 1 to sum do begin

fillchar(cover, sizeof(cover), false);

path(i);

end;

assign(output, 'output.txt'); rewrite(output);

sum := 0; show(1, 0, 0);

close(output);

end.

4. 最小最大匹配

问题:OOPC-神秘之山

M个人在追一只奇怪的小动物。眼看就要追到了,那小东西却一溜烟蹿上一座神秘的山。众人抬头望去那山看起来就是这个样子:

图表7 样例示意图

那山由N+1条线段组成。各个端点从左到右编号为0…N+1,即x[i]

根据经验来说那小东西极有可能藏在1…N 中的某个端点。有趣的是大家很快发现了原来M恰好等于N,这样,他们决定每人选一个点,看看它是否在躲那里。

一开始,他们都在山脚下,第i 个人的位置是(s[i], 0)。他们每人选择一个中间点(x[i], 0),先以速度w[i]水平走到那里,再一口气沿直线以速度c[i]爬到他的目的地。由于他们的数学不好,他们只知道如何选择一个最好的整数来作为中间点的横坐标x[i]。而且很明显,路线的任何一个部分都不能在山的上方(他们又不会飞)。

他们不希望这次再失败了,因此队长决定要寻找一个方案,使得最后一个到达目的地的人尽量早点到。他们该怎么做呢?

其中1≤N≤100,0≤x[i], y[i], s[i]≤1000,1≤c[i]

输入

第一行包含一个整数N。以下N+2行每行,包含两个整数xi和yi,代表相应端点的坐标。以下N行每行包含3个整数:ci, wi和si,代表第i个人的爬山速度,行走速度和初始位置

输出

输出最后一个人到达目的地的最早可能时间,四舍五入到小数点后两位。

样例输入

3

0 0

3 4

6 1

12 6

16 0

2 4 4

8 10 15

4 2

5 14

样例输出

1.43

样例说明

在这里例子中,第一个人先到(5, 0)再爬到端点2;第二个人直接爬到端点3;第三个人先到(4, 0)再爬到端点1。如下图:

图表8 样例的解答

分析:

题目中的数据繁多复杂,我们先把他们提出来一个个分析:

人,共n个,与之有关的有初始横坐标s,速度w和c

山头,共n个,与之有关的有坐标x和y

根据这些信息,可以得到,人和山头的关系:t[I, J],表示第i个人到达山头j所需的最短时间。

题目中已经指明是一个人负责一个山头,这显然是一个一一对应的关系,因此,我们可以从二分图的匹配的角度来考虑这个问题。

那么,这道题目属于哪一种匹配呢?是简单的最大匹配,还是最大权匹配,或者是前面所提到的“完美”最大权匹配呢?

其实都不是。因为一般的最大权匹配,一个匹配的权的定义是该匹配中所有边上权的和,而这道题目,一个匹配的权是指该匹配的边上权值的最大值。题目要求这个最大值最小,我们暂且称之为“最小最大匹配”。

直接求解似乎不太方便。换一个角度,如果我们给出一个时间,就可以用完美匹配的算法来判断能否在这个时间内完成所有的工作。

具体的来说,对于给定的二分图G和最大时间T,我们可以导出新的图G’,G’中所有边的权都不超过T。如果G’存在完美匹配,则所有工作可以在T时间内完成,否则则不能。

这样,一个简单的算法就诞生了:依次增加T,知道求出一个完美匹配为止。由于二分图中的边不会超过n2,因此T最多增加n2次,而每次增加T的值,需要O(n2)的时间来找增广链,这样总的时间复杂度就是O(n4)。

我们还可以采用二分查找的方法来寻找这个T,这样的算法时间复杂度就可以降到为O(n3logN)。

参考程序如下:

program mountain;

const

finp = 'input.txt';

fout = 'output.txt';

maxn = 100;

var

i, k, d, p, m, n, ds, lo, hi: integer;

x, y, c, w, s, a, b, link: array[0 .. maxn + 1] of integer;

len: array[1 .. maxn, 1 .. maxn] of integer;

ls: array[1 .. maxn * maxn] of integer;

cover: array[1 .. maxn] of boolean;

function path(i: integer): boolean; {找增广轨}

var

k, p: integer;

begin

result := true;

for k := 1 to n do

if not cover[k] and (len[i, k] <= ds) then begin

cover[k] := true; p := link[k]; link[k] := i;

if (p = 0) or path(p) then exit;

link[k] := p;

end;

result := false;

end;

function update(k, i, p: integer; var v: integer): integer; {计算耗费} begin

result := round((abs(s[k] - p) / w[k] +

sqrt(sqr(p - x[i]) + sqr(y[i])) / c[k]) * 100);

if (result < v) and (a[i] <= p) and (p <= b[i]) then v := result;

end;

procedure sort(l, u: integer); {排序}

var

i, j, k, x: integer;

begin

i := l; j := u; x := ls[(i + j) div 2];

repeat

while ls[i] < x do i := i + 1;

while ls[j] > x do j := j - 1;

if i <= j then begin

k := ls[i]; ls[i] := ls[j]; ls[j] := k;

i := i + 1; j := j - 1;

end;

until i > j;

if l < j then sort(l, j);

if i < u then sort(i, u);

end;

begin

assign(input, finp); reset(input); assign(output, fout); rewrite(output); repeat

readln(n);

if n = 0 then break;

for i := 0 to n + 1 do readln(x[i], y[i]);

for i := 1 to n do readln(c[i], w[i], s[i]);

for i := 1 to n do begin

a[i] := x[i] - x[0]; b[i] := x[n + 1] - x[i];

for k := 1 to n do begin

if y[k] >= y[i] then continue;

d := abs(y[i] * (x[k] - x[i]) div (y[i] - y[k]));

if (k < i) and (d < a[i]) then a[i] := d;

if (k > i) and (d < b[i]) then b[i] := d;

end;

a[i] := x[i] - a[i]; b[i] := x[i] + b[i];

end;

m := 0;

for k := 1 to n do

for i := 1 to n do begin

len[k, i] := maxint;

ds := round(y[i] * c[k] / sqrt(sqr(w[k]) - sqr(c[k])));

if ds > abs(s[k] - x[i]) then ds := abs(s[k] - x[i]);

update(k, i, a[i], len[k, i]); update(k, i, b[i], len[k, i]);

if s[k] < x[i] then p := x[i] - ds else p := x[i] + ds;

for d := p - 1 to p + 1 do update(k, i, d, len[k, i]);

m := m + 1; ls[m] := len[k, i];

end;

lo := 1; hi := m; sort(lo, hi);

while lo < hi do begin

fillchar(link, sizeof(link), 0); fillchar(cover, sizeof(cover), 0);

p := (lo + hi) div 2; ds := ls[p]; i := 1;

while (i <= n) and path(i) do begin

i := i + 1; fillchar(cover, sizeof(cover), 0);

end;

if i > n then hi := p else lo := p + 1;

end;

writeln((ls[hi] / 100) : 0 : 2);

until false;

close(input); close(output);

end.

第九章分批法练习题参考答案

第九章分批法练习题参考答案 一、某工业企业生产甲、乙两种产品。生产组织属于小批生产,采用分批法计算成本。2002年4月份的生产情况和生产费用资料如下: (1)本月份生产的产品批号有: 2051批号:甲产品12台,本月投产,本月完工8台。 2052批号:乙产品10台,本月投产,本月完工3台。 (2)本月份的成本资料:(单位:元) 2051批号甲产品完工数量较大,完工产品与在产品之间分配费用采用约当产量法。在产品完工率为50%,原材料在生产开始时一次投入。 2052批号乙产品完工数量少,完工产品按计划成本结转。 每台计划成本为:原材料880元,燃料140元,工资及福利费720元,制造费用450元。 要求:根据上列资料,采用分批法,登记产品成本明细账,计算各批产品的完工产品成本和月末在产品成本。

解: 甲产品费用分配情况: 材料费用分配率=6840/12=570 燃料费用分配率=1452/(8+4×50%)=145.2 工资及福利费分配率=4200/(8+4×50%)=420 制造费用分配率=2450/(8+4×50%)=245 产品成本明细账 产品批号:2051 投产日期:4月 产品名称:甲批量:12台完工日期:4月完工8台

乙产品完工产品成本按计划成本转出 完工产品原材料计划成本=880×3=2640 完工产品燃料计划成本=140×3=420 完工产品工资及福利费计划成本=720×3=2160 完工产品制造费用=450×3=1350 产品成本计算单 产品批号:2052 投产日期:4月 产品名称:乙批量:10台完工日期:4月完工3台

二、某企业生产属于小批生产,产品批数多,每月末都有很多批号没有完工,因而采用简化的分批法计算产品成本。 (1)8月份生产的产品批号有: 8210号:甲产品6件,7月投产,8月25日全部完工。 8211号:乙产品14件,7月投产,8月完工8件。 8212号:丙产品8件,7月末投产,尚未完工。 8213号:丁产品6件,8月投产,尚未完工。 (3)各批号产品8月末累计原材料费用(原材料在生产开始时一次投入)和生产工时为: 8210号:原材料32000元,工时9200小时。 8211号:原材料98000元,工时29600小时。 8212号:原材料62400元,工时18200小时。 8213号:原材料42600元,工时8320小时。 (4)8月末,该企业全部产品累计原材料费用235000元,工时65320小时,工资及福利费26128元,制造费用 32660元。 (5)8月末,完工产品工时25200小时,其中乙产品16000

二分图的最大匹配完美匹配和匈牙利算法

二分图的最大匹配完美匹配和匈牙利算法 匈牙利算法是由匈牙利数学家Edmonds于1965年提出,因而得名。匈牙利算法是基于Hall定理中充分性证明的思想,它是二部图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。这篇文章讲无权二分图(unweighted bipartite graph)的最大匹配(maximum matching)和完美匹配(perfect matching),以及用于求解匹配的匈牙利算法(Hungarian Algorithm);不讲带权二分图的最佳匹配。二分图:简单来说,如果图中点可以被分为两组,并且使得所有边都跨越组的边界,则这就是一个二分图。准确地说:把一个图的顶点划分为两个不相交集U 和V ,使得每一条边都分别连接U、V 中的顶点。如果存在这样的划分,则此图为一个二分图。二分图的一个等价定义是:不含有「含奇数条边的环」的图。图 1 是一个二分图。为了清晰,我们以后都把它画成图 2 的形式。匹配:在图论中,一个「匹配」(matching)是一个边的集合,其中任意两条边都没有公共顶点。例如,图3、图4 中红色的边就是图 2 的匹配。我们定义匹配点、匹配边、未匹配点、非匹配边,它们的含义非常显然。例如图 3 中1、4、5、7 为匹配点,其他顶点为未匹配点;1-5、4-7为匹配边,其他边为非匹配边。最大匹配:一个图所有匹配中,所含匹

配边数最多的匹配,称为这个图的最大匹配。图 4 是一个最大匹配,它包含4 条匹配边。完美匹配:如果一个图的某个匹配中,所有的顶点都是匹配点,那么它就是一个完美匹配。图 4 是一个完美匹配。显然,完美匹配一定是最大匹配(完美匹配的任何一个点都已经匹配,添加一条新的匹配边一定会与已有的匹配边冲突)。但并非每个图都存在完美匹配。举例来说:如下图所示,如果在某一对男孩和女孩之间存在相连的边,就意味着他们彼此喜欢。是否可能让所有男孩和女孩两两配对,使得每对儿都互相喜欢呢?图论中,这就是完美匹配问题。如果换一个说法:最多有多少互相喜欢的男孩/女孩可以配对儿?这就是最大匹配问题。基本概念讲完了。求解最大匹配问题的一个算法是匈牙利算法,下面讲的概念都为这个算法服务。交替路:从一个未匹配点出发,依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。增广路:从一个未匹配点出发,走交替路,如果途径另一个未匹配点(出发的点不算),则这条交替路称为增广路(agumenting path)。例如,图5 中的一条增广路如图6 所示(图中的匹配点均用红色标出):增广路有一个重要特点:非匹配边比匹配边多一条。因此,研究增广路的意义是改进匹配。只要把增广路中的匹配边和非匹配边的身份交换即可。由于中间的匹配节点不存在其他相连的匹配边,所以这样做不会破坏匹配的性质。交换后,图中的匹配边数

分批法例题及答案

(一)基本情况 某企业属单件小批多步骤生产企业,按购货单位要求小批生产甲、乙、丙三种产品,产品成本计算采用分批法,该企业9月份的有关成本计算资料如下: 1、各生产批别产量、费用资料 (1)901号甲产品50件,7月份投产,本月全部完工,7、8两月累计费用为:直接材料4000元,直接人工1000元,制造费用1200元。本月发生费用:直接人工400元,制造费用500元。 (2)902号乙产品100件,8月份投产,本月完工60件,未完工40件,8月份发生生产费用为:直接材料60000元,直接人工15000元,制造费用13000元。本月发生费用:直接人工7000元,制造费用6000元。 (3)903号丙产品7件,本月份投产,尚未完工,本月发生生产费用为:直接材料20000元,工资福利费5600元,制造费用4800元。 2、其他资料 (1)三种产品的原材料均在生产开始时一次投入。 (2)902号乙产品本月完工产品数量在批内所占比重较大(60%),根据生产费用发生情况,其原材料费用按照完工产品和在产品的实际数量比例分配外,其他费用采用约当产量比例法在完工产品和月末在产品之间进行分配,在产品完工程度为50%。 (二)成本计算过程 1、901号成本计算 901号产品,本月全部完工,7、8、9三个月份累计生产费用全部为完工产品成本,除以完工产品数量,为完工产品单位成本。 表8—1 901号产品成本计算单 批号:901 产品名称甲投产日期:7月份 会计分录: 借:库存商品7100 贷:基本生产成本—甲产品7100 2、902号产品成本计算 902号本月完工60件,尚有40件未完工,属于是跨月陆续完工,且完工产品数量在批内所占比重较大,生产费用应在完工产品和月末在产品之间进行分配。因原材料一次投入,完工产品和在产品负担的原材料费用相同,按产品数量分配。其余按约当产量比例分配。 约当产量=完工产品数量+在产品约当产量 直接材料项目的约当产量=60+40×100%=100 直接人工项目约当产量=60+40×50%=80

用改进的匈牙利算法求解运输问题

用改进的匈牙利算法求解运输问题 李雪娇,于洪珍 中国矿业大学信电学院,江苏徐州 (221008) Email :liaohuchushan@https://www.wendangku.net/doc/3f16008249.html, 摘 要:本文提出用改进的匈牙利算法求解运输问题。此算法不但可以直接求取最优解,而且在运量受限制的运输问题中有很好的应用。 关键词:改进,匈牙利算法,运输问题,最优解 0. 引言 在现实生活中,我们常常会遇到许多运输问题。运输问题的求解多采用表上作业法。在此方法中,我们需要先利用最小元素法或西北角法求出一组基本可行解,再对此解检验其最优性。若此解非最优解,则又要进行解的改进。这一过程比较麻烦,尤其对一些结构不太大的模型,编程时往往过于繁琐。 同时,经典运输问题在实际应用中有很大的局限性, 对一些运输量受限制或运输能力受限制的运输问题,我们无法用表上作业法直接求取。在此,我们采用改进的匈牙利算法处理这类运输问题。为了便于描述,设物资供应量12[...]m A a a a =,物资需求量12[...]n B b b b =,从到i A j B 的单物的物资运价,最小运输量 (假设m )。 i j C i j L n >1. 匈牙利算法[1][4] 匈牙利算法的基本思想是修改效益矩阵的行和列,使得每行和每列中至少有一个零元素。经过一定的变换,得到不同行、不同列只有一个零元素。从而得到一个与这些零元素相匹配的完全分配方案。这种方法总是在有限步内收敛于一个最优解。该方法的理论基础是:在效益矩阵的任何行或列中,加上或减去一个常数后不会改变最优解的分配。求解步骤如下: 第一步:使指派问题的系数矩阵经变换后,在各行各列中都出现零元素,即从系数矩阵的每行(或列)元素中减去该行(或列)的最小元素。 第二步:寻求找n 个独立的零元素,以得到最优解:(1)从只有一个0元素的行(或列)开始,对这个0元素加圈,记为θ。然后划去此元素所在列(或行)的其他0元素,记作?。反复进行,直到所有的0元素被划完。(2)若仍有没有划圈的0元素,则从剩有0元素最少的行开始,比较这行0元素所在各列中0元素的数目,选择0元素少的那列的0元素加圈θ,然后划掉同行同列的其他0元素,反复进行直到所有的0元素被划掉或圈出。 (3)若元素的数目m 等于矩阵的阶数,那么指派问题的最优解已得到。若m ,则转入下一步。 n n <第三步:作最少的直线覆盖所有0元素,以确定该系数矩阵中能找到最多的独立元素数:若l ,必须再变换当前的系数矩阵,才能找到个独立的0元素,为此转第四步;若l ,而,应回到第二步(2),另行试探。 n

二分图匹配(匈牙利算法和KM算法)

前言: 高中时候老师讲这个就听得迷迷糊糊,有一晚花了通宵看KM的Pascal代码,大概知道过程了,后来老师说不是重点,所以忘的差不多了。都知道二分图匹配是个难点,我这周花了些时间研究了一下这两个算法,总结一下 1.基本概念 M代表匹配集合 未盖点:不与任何一条属于M的边相连的点 交错轨:属于M的边与不属于M的边交替出现的轨(链) 可增广轨:两端点是未盖点的交错轨 判断M是最大匹配的标准:M中不存在可增广轨 2.最大匹配,匈牙利算法 时间复杂度:O(|V||E|) 原理: 寻找M的可增广轨P,P包含2k+1条边,其中k条属于M,k+1条不属于M。修改M 为M&P。即这条轨进行与M进行对称差分运算。 所谓对称差分运算,就是比如X和Y都是集合,X&Y=(X并Y)-(x交Y) 有一个定理是:M&P的边数是|M|+1,因此对称差分运算扩大了M 实现: 关于这个实现,有DFS和BFS两种方法。先列出DFS的代码,带注释。这段代码来自中山大学的教材

核心部分在dfs(x),来寻找可增广轨。如果找到的话,在Hungarian()中,最大匹配数加一。这是用了刚才提到的定理。大家可以想想初始状态是什么,又是如何变化的 view plaincopy to clipboardprint?

第二种方法BFS,来自我的学长cnhawk 核心步骤还是寻找可增广链,过程是: 1.从左的一个未匹配点开始,把所有她相连的点加入队列 2.如果在右边找到一个未匹配点,则找到可增广链 3.如果在右边找到的是一个匹配的点,则看它是从左边哪个点匹配而来的,将那个点出发的所有右边点加入队列 这么说还是不容易明白,看代码吧

二分图的最大匹配经典之匈牙利算法

Doctor的图论计划之——二分图最大匹配 第一讲二分图的最大匹配经典之匈牙利算法 二分图,顾名思义就是分成了两个部分的图……很白痴的解释(自己吐槽了先),但吐槽的同时我们也要发现一些二分图的基本性质! 性质1 二分图之所以分成了两个部分,那是因为单独的一个部分中的任意两点不连通! 性质2 二分图匹配——匈牙利算法中我们只需记录集合1到集合2的单向边就可以了(注意看上边的图,箭头是单向的)思考这是为什么! 但是!二分图确实是无向图!!!只不过匈牙利算法只是从一个集合另一个集合走一遍罢了!!!! 性质3 树是一种特殊的二分图! 紫色的结点构成集合1,绿色的结点构成集合2,换句话说,儿子和爸爸打仗时爷爷和

孙子站在同一战线!(也可以认为是儿子和爸妈吵架时总是爷爷奶奶护着,小时候有这样的记忆没有?反正我没有!) PS:树就是无回路懂不? 性质3 对于任意二分图,其包含的环一定全部是偶环!(充要可证) 可以证明,含有奇数条边的环一定有两个在相同集合内的点有边相连! 也就是说——二分图的bfs子树一定不含奇环! 接下来说一下二分图求最大匹配的算法——匈牙利算法 【例1】传说中的多米诺骨牌覆盖问题 在一个n*m的棋盘上,摆放一些1*2大小的多米诺骨牌,但棋盘某些地方是坏 掉的,即不能将骨牌置于这些坏掉的格子上,求最多能摆上的骨牌数量 【例2】传说中的猎人打鸟问题 猎人要在n*n的格子里打鸟,他可以在某一行中打一枪,这样此行中的所有鸟都被 打掉,也可以在某一列中打,这样此列中的所有鸟都打掉.问至少打几枪,才能打光 所有的鸟? 【例3】传说中的搞对象问题 一保守教师想带学生郊游, 却怕他们途中谈恋爱,他认为满足下面条件之一的两 人谈恋爱几率很小: (1)身高差>40 (2) 性别相同(3) 爱好不同类型的音乐(4) 爱好同类型的运动 告诉你每个同学的信息,问老师最多能带多少学生? 这样的问题如何解决?搜索?怎么搜?会不会超时?答案很简单,三道题中的元素都可以用很简单的方式分成两个互不相干的部分,因此可以用二分图匹配来解决这个问题:形象的说,我们规定搞基和百合都是不允许的,已知一群男人和女人,他们可以看做图中的顶点,男人构成了集合A,女人构成了集合B,边表示这名男人和这名女人互相有好感(可以配成一对)不考虑个人因素,现在希望为这些饥渴的男男女女找到最多的配对数(脚踏两只船也是不允许的!)为了解决这样的问题我们才引入了二分图的匹配算法——匈牙利算法! 匈牙利算法是一种用增广路求二分图最大匹配的算法。它由匈牙利数学家Edmonds于1965年提出,因而得名。 如果暴搜的话那么无疑时间复杂度将成为O(2^E)!无法快速实现,于是我们就提出了更为高效的算法,这种算法是从网络流演变而来,但这里我们抛开所有网络流的知识,但从这一算法的角度来进行阐释! 解释一些常用的名词 交错轨:所谓交错轨,还有一种更为文雅的说法叫增广轨,这种说法让人不禁联想到蛋疼的网络流算法,所以我更喜欢用一种与网络流无关的说法来称呼它,下面我们来举几个交错轨的例子:

匈牙利算法

匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法,并推动了后来的原始对偶方法。美国数学家哈罗德·库恩于1955年提出该算法。此算法之所以被称作匈牙利算法,是因为算法很大一部分是基于以前匈牙利数学家Dénes K?nig和Jen? Egerváry的工作之上创建起来的。 匈牙利算法是由匈牙利数学家Edmonds于1965年提出,因而得名。匈牙利算法是基于Hall定理中充分性证明的思想,它是部图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。 二分图: 二分图又称作二部图,是图论中的一种特殊模型。设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),则称图G为一个二分图。图一就是一个二分图。 匈牙利算法: 匈牙利算法是由匈牙利数学家Edmonds于1965年提出,因而得名。匈牙利算法是基于Hall定理中充分性证明的思想,它是一种用增广路径求二分图最大匹配的算法。 Hall定理: 二部图G中的两部分顶点组成的集合分别为X, Y; X={X1, X2, X3,X4, .........,Xm}, Y={y1, y2, y3, y4 , .........,yn}, G中有一组无公共点的边,一端恰好为组成X的点的充分必要条件是:X中的任意k个点至少与Y中的k个点相邻。(1≤k≤m) 匹配: 给定一个二分图G,在G的一个子图M中,M的边集中的任意两条边都不依附于同一个顶点,则称M是一个匹配。图一中红线为就是一组匹配。 未盖点: 设Vi是图G的一个顶点,如果Vi 不与任意一条属于匹配M的边相关联,就称Vi 是一个未盖点。如图一中的a 3、b1。

可以直接用的匈牙利算法

将xyl程序存入M文件,在matlab中先写入邻接矩阵marix,而后再写function [z,ans]=xyl(marix) 回车得出结果 程序文件 xyl.m function [z,ans]=xyl(marix) %输入效率矩阵 marix 为方阵; %若效率矩阵中有 M,则用一充分大的数代替; %输出z为最优解,ans为最优分配矩阵; %////////////////////////////////////////////////// a=marix; b=a; %确定矩阵维数 s=length(a); %确定矩阵行最小值,进行行减 ml=min(a'); for i=1:s a(i,:)=a(i,:)-ml(i); end %确定矩阵列最小值,进行列减 mr=min(a); for j=1:s a(:,j)=a(:,j)-mr(j); end % start working num=0; while(num~=s) %终止条件是“(0)”的个数与矩阵的维数相同 %index用以标记矩阵中的零元素,若a(i,j)=0,则index(i,j)=1,否则index(i,j)=0 index=ones(s); index=a&index; index=~index; %flag用以标记划线位,flag=0 表示未被划线, %flag=1 表示有划线过,flag=2 表示为两直线交点 %ans用以记录 a 中“(0)”的位置 %循环后重新初始化flag,ans flag = zeros(s); ans = zeros(s); %一次循环划线全过程,终止条件是所有的零元素均被直线覆盖, %即在flag>0位,index=0 while(sum(sum(index))) %按行找出“(0)”所在位置,并对“(0)”所在列划线, %即设置flag,同时修改index,将结果填入ans for i=1:s t=0;

匈牙利法真题演练

匈牙利法真题演练(07年5月): 某车间产品装配组有王成、赵云、江平、李鹏四位员工.现有A、B、C、D 四项任务,在现有生产技术组织条件下,每位员工完成每项工作所需要的工时如表1所示。问:请运用匈牙利法求出员工与任务的配置情况,以保证完成任务的总时间最短,并求出完成任务的量短时间。 表1 王成赵云江平李鹏 工作 任务 员工 A 10 5 9 18 B 13 18 6 12 C 3 2 4 4 D 18 9 10 16 解题步骤: 1、建立矩阵 105918(-5) 1318612(-6) 3244(-2) 1891016(-9) 2、行列约减 5 0 4 13 7 12 0 6 1 0 2 2 9 0 1 7 (-1)(-2) PS:行约减以后需要检查列是否都有“0”

3、盖“0” 4 0 4 11 6 12 0 4 0 0 2 0 8 0 1 5 “盖0”只有三条,需要找出剩下数字中最小约数 4、继续约减,交叉处加上约数 3 0 3 10 6 13 0 4 0 1 2 0 7 0 0 4 当我们做完第三步会发现盖0线的数目仍然小于矩阵维数,继续寻找最小约数 将未被盖0线覆盖的数字都减去最小约数,同时在盖0线交叉点上的数字加上这个最小约数 5、数据转化 0 0 3 7 3 13 0 1 0 4 5 0 4 0 0 1 四条盖0线,四个维度,进行求最优解,首先只有一个0的行列,打钩 6、求最优解 0√0× 3 7 3 13 0√ 1 0× 4 5 0√ 4 0√0× 1 得到最优解如下:王—A;赵—D;江—B;李—C。 对照工时消耗表,完成任务的总时间为10+9+6+4=29

成本会计练习分批法及答案

分批法课堂练习 1、资料:某企业第一车间生产501批次甲产品、601批次乙产品、502批次 丙产品三批产品,6月份有关成本计算资料如下: (1)月初在产品成本 501批次甲产品为104000元,其中直接材料84000元,直接人工12000元,制造费用8000元;502批次丙产品124000元,其中直接材料120000元,直接人工2000元,制造费用2000元。 (2)本月生产情况 501甲产品为5月2日投产40件,本月26日已全部完工验收入库,本月实际生产工时为8000小时。601乙产品为本月4日投产120件,本月已完工入库12件,本月实际生产工时为4400小时。502丙产品为5月6日投产60件,本月尚未完工,本月实际生产工时为4000小时。 (3)本月发生生产费用 本月投入原材料396000元,全部为601乙产品耗用。本月产品生产工人工资为49200元,提取应付福利费为6888元,制造费用总额为44280元。 (4)单位产品定额成本 601乙产品单位产品定额成本为4825元,其中直接材料3300元,直接人工825元,制造费用700元。 要求:根据上述资料材料采用分批法计算产品成本,具体计算程序如下:(1)按产品批别开设产品成本计算单并登记月初在产品成本。 (2)编制601批产品耗用原材料的会计分录并记入产品成本计算单。 (3)用生产工时分配法在各批产品之间分配本月发生的直接人工费用,根据分配结果编制会计分录并记入有关产品成本计算单。 (4)采用生产工时分配法在各批产品之间分配本月发生的制造费用,根据分配结果编制会计分录并记入有关产品成本计算单。 (5)计算本月完工产品和月末在产品成本,编制结转完工产品成本的会计分录。601乙产品本月少量完工,其完工产品成本按定额成本结转。 产品成本成本计算单批量:40件 开工日期:5月2日批别:501批次 产品:甲产品完工日期:6月26日

线性规划和匈牙利法

二、生产任务分配的匈牙利法 在实际的生产管理工作中,常会遇到这样的问题,就是如何根据生产作业汁划将不同任务在不同的工人(或班组)之间分配,使完成任务总的消耗时间或费用最小。解决这类问题的简便而有效的方法是匈牙利法,它是由匈牙利数学家D. Konig所提出。 例有4项任务A、B、C、D,分别由甲、乙、丙、丁4个人去完成,规定每人承担其中一项任务,不同的人完成同一任务所花时间(h)不同,见表3-3,求如何分配,使完成这4项任务的总时间最小。 匈牙利法求解此问题的步骤是: 1)按表3-3列出矩阵 2)将矩阵作行、列约简:首先进行行约简。在矩阵的每一行中选取最小元素, 然后将该行的各元素都减去此数,得到如下新矩阵 行约简是比较一名工人担任不同任务时所花的时间,各行中减去最小值后的时间表示该工人担任其它任务时,所多花费的时间,每行中的“0”表示该工人承担这项任务最有利。然后将经过行约筒后的矩阵中没有“0”的列再进行约简,即从该列中选出最小元素,并将其它元素减去此数,得到新矩阵 列约简是比较一项任务有不同工人承担所托时间,各列中减去最小值后的时间表示任务由其他工人担任时,所多花费的时间,每列中的“0”表示这项任务由该工人承担最有利。 3) 检验是否已得最优分配方案;作零的覆盖线,即对有“0”的行和列,划上一条覆盖线,能覆盖所有零元素的最少覆盖线数称为维数,当覆盖线的维数等于矩阵阶数时,可知已得最优分配方案,若维数小于阶数,再作调整。本例可用三条覆盖线覆盖住所有零元素,维数是3,矩阵的阶数是4,维数不等于阶数,因此矩阵还必须调整。

4) 矩阵的调整。在上述矩阵中.有三种元素,一种是无线覆盖元素,另一种是单线覆盖元素,还有一种是双线覆盖元素。在无线覆荒元素中找出最小值,本例为“1”,将无线覆盖得元素都减去“1”,而双线覆盖的元素加上“1”,单线覆盖的元素不变。这样得到新矩阵 5) 再检验——作覆盖线,方法与步骤3相同。现在的最少覆盖线数为4,与矩阵阶数相等,可知已能进行最优分配。 6) 确定最优分配方案。进行具体分配时,可以对只有一个零元素的列(行)先分配(记√号),分配后,划去与该零元素同行(列)的其他零元素(记×号)这样依改做完各列(行),得到分配结果。如果矩阵能通过直接观察找到位于不同行不同列的零元素,那么就可以直接确定分配方案。 最优分配方案:甲——D,乙——B,丙——A,丁——C。 总消耗工时为:Z=7+5+4+5=21 (h)。

匈牙利算法

匈牙利算法是一种用于在多项式时间内解决任务分配问题的组合优化算法,它推广了后来的原始对偶方法。美国数学家哈罗德·库恩(Harold Kuhn)于1955年提出了该算法。该算法之所以称为匈牙利算法,是因为该算法的很大一部分是基于前匈牙利数学家DéNESK?nig和Jen?egerváry的工作。 概念 在介绍匈牙利算法之前,我想介绍一些概念。接下来的M是G 的匹配项。 如果是,则边缘已经在匹配的M上。 M交织路径:P是G的路径。如果P中的边缘是属于m的边缘,而不属于m但属于G的边缘是交替的,则p是M交织的路径。例如:路径。 M饱和点:例如,如果V与M中的边相关联,则称V为m饱和,否则V为非m饱和。如果它们全部属于m饱和点,则其他点都属于非m饱和点。 M扩展路径:P是m隔行扫描路径。如果P的起点和终点均为非m饱和点,则p称为m增强路径。例如(不要与流网络中的扩展路径混淆)。 寻找最大匹配数的一种显而易见的算法是先找到所有匹配项,然后保留匹配数最大的匹配项。但是该算法的时间复杂度是边数的指数函数。因此,我们需要找到一种更有效的算法。本文介绍了一种使用扩展路径查找最大匹配的方法(称为匈牙利算法,由匈牙利的

Edmonds于1965年提出)。 增强导轨(也称为增强导轨或交错导轨)的定义 如果P是连接图G中两个不匹配顶点的路径,并且属于m和不属于m的边缘(即,匹配边缘和待匹配边缘)在P上交替,则p称为相对于M. 从增强路径的定义可以得出三个结论 (1)P的路径数必须为奇数,并且第一个边缘和最后一个边缘都不属于M。 (2)通过将m和P取反可以获得更大的匹配度。 (3)当且仅当没有M的增强路径时,M是G的最大匹配。 算法概述: (1)将M设置为null (2)通过XOR操作找到扩展路径P并获得更大的匹配项而不是m (3)重复(2),直到找不到增强路径

简化分批法例题

简化分批法例题 [例]某厂生产有第0102009、0103004、0104001等定单产品,其成本和工时总数汇总登记在“生产成本——基本生产成本”二级账中,如表7-5所示。第0102009、0103004、0104001定单的生产成本,如表7-6、7-7、7-8所示。 基本生产成本二级账 累计工资及福利费分配率=5000/1000=5(元/工时) 累计制造费用分配率=6000/1000=6(元/工时) 基本生产成本二级账月末在产品直接材料费用 =23840+50000=73840(元) 基本生产成本二级账月末在产品生产工时 =300+180=480(工时) 产品成本明细账 表1 产品批号:0102009 开工日期:200×年2月 表2 产品批号:0103004 开工日期:200×年3月15 产品名称:批量:5台完工日期: 产品成本明细账

表3 产品批号:0104001 开工日期:200×年4月5日

(分批法)习题 1、资料:某厂属于小批生产,采用简化的分批法计算成本。4月份生产情况如 下: (1)(1)月初在产品成本:101批号,直接材料3750元;102批号,直接材料2200元;103批号,直接材料1600元。月初直接人工1725 元,制造费用2350元。 (2)(2)月初在产品耗用累计工时:101批号1800小时;102批号590小时;103批号960小时。 (3)(3)本月的生产情况,发生的工时和直接材料如下表所示: (4)(4)本月发生的各项间接费用为:直接人工1400元,制造费用2025元。 要求:根据上述资料,登记基本生产成本二级帐和产品成本明细帐;计算完工产品成本。 答案如下: 基本生产成本二级帐 产品成本明细帐 批号:101 投产日期:2月 产品名称:甲完工日期:4月 产量:10件

一种基于能量最小化的多目标跟踪算法研究

优先出版 计 算 机 应 用 研 究 第32卷 -------------------------------- 基金项目:国家“八六三“高技术研究发展计划(2011AA110501) 作者简介:李艳萍(1976 -),女,陕西岐山人,讲师,硕士,主要研究方向为信息检索、视频处理(lyp_swj@https://www.wendangku.net/doc/3f16008249.html,);林建辉(1964 -),男,福建莆田人,教授,博士,主要研究方向为图像处理、数据挖掘. 一种基于能量最小化的多目标跟踪算法研究 李艳萍1,林建辉2 (1.西南交通大学 机械工程学院,成都 610031;2.西南交通大学 牵引动力国家重点实验室,成都 610031) 摘 要:现有的多目标跟踪算法只关注生成所有目标的区分性运动和外观模型,如果目标的场景拥挤,掩蔽频繁,外观 相似,则很难找到合适的描述符将这些目标区分开。鉴于此,本文基于一种在线学习条件随机场模型对跟踪问题进行建 模,并将其转化为能量最小化问题。最后提出一种近似算法,可用于高效确定能量成本低、质量高的跟踪问题的解。基 于3种公共数据集对本文算法进行评估,实验结果表明,本文算法相对其他几种最新算法,具有很大的性能提升,无论 在区分外观相似且空间距离较近的目标方面,还是在处理摄像机运动方面,本文算法的性能均很优异。 关键词:多目标跟踪;外观模型;描述符;能量函数;踪迹碎片;近似算法 中图分类号:TP391 文献标志码:A Research on multi-target tracking algorithm based on energy minimization LI Yan-ping 1, LIN Jian-hui 2 (1. School of Mechanical Engineering, Southwest Jiaotong University, Chengdu 610031, China; 2. Traction Power State Key Laboratory of Southwest Jiaotong University, Chengdu 610031, China) Abstract: Multi-target tracking is an important but difficult project in computer vision field, the existing multi-target tracking algorithm which only focus on producing discriminative motion and appearance models for all targets, it is difficult to find descriptors to distinguish targets in crowded scenes with frequent occlusions and similar appearances. In order to this problem, the tracking problem is modeled by using an online learned CRF model, and is transformed into an energy minimization problem. Finally, an approximation algorithm is proposed for efficiently finding good tracking solutions with low energy costs. We evaluate our approach on three public data sets, and the simulation results show significant improvements compared with several state-of-art methods. The proposed algorithm is more powerful at distinguishing spatially close targets with similar appearances, as well as in dealing with camera motions. Key Words: multi-target tracking; appearance models; descriptors; energy functions; tracklets; approximation algorithm 0 引言 多目标跟踪是计算机视觉领域研究难度较大的一个重要课 题。它需要在保持所有目标身份的前提下,确定所有目标的轨 迹。人们提出了多种基于关联的跟踪算法[1,2],这些算法往往根 据检测响应或踪迹碎片间的多种信息来确定合适的链接亲和力 (linking affinity),然后通过匈牙利算法、MCMC 等算法确定概 率最大的全局解。然而,如何更好地将不同目标区分开,仍然 是一个关键问题,这影响到基于关联的跟踪算法的性能。如果 目标的场景拥挤,掩蔽频繁,外观相似,则很难找到合适的描 述符来将这些目标区分开。本文提出一种在线学习有条件随机 场模型(CRF)来更好地将不同的目标尤其是空间距离较近、外观 类似的高难度目标区分开。图1给出了应用本文算法时的部分 跟踪示例。 图1应用本文算法时的目标跟踪结果示例 为了确定每一个目标的身份,经常使用运动和外观信息来生成区分性描述符。运动描述符经常基于速度和踪迹碎片间的距离,而外观描述符为了区分不同的目标往往基于全局或局部颜色直方图。另外,线性运动模型在目标跟踪研究中得到了广 泛研究[3,4]。踪迹碎片间的链接概率往往基于两个踪迹碎片对线 性运动假设的满足程度。然而,如果摄像机运动导致观测角度

匈牙利算法

匈牙利算法(Edmonds算法)步聚: (1)首先用(*)标记X中所有的非M顶点,然后交替进行步骤(2),(3)。 (2)选取一个刚标记(用(*)或在步骤(3)中用(y i)标记)过的X中顶点,例如顶点x ,如果x i与y为同一非匹配边的两端点,且在本步骤中y尚未被标记过,则用(x i)i 去标记Y中顶点y。重复步骤(2),直至对刚标记过的X中顶点全部完成一遍上述过程。 (3)选取一个刚标记(在步骤(2)中用(x i)标记)过的Y中结点,例如y i,如果y i与x为 同一匹配边的两端点,且在本步骤中x尚未被标记过,则用(y i)去标记X中结点x。 重复步骤(3),直至对刚标记过的Y中结点全部完成一遍上述过程。 (2),(3)交替执行,直到下述情况之一出现为止: (I)标记到一个Y中顶点y,它不是M顶点。这时从y出发循标记回溯,直到(*)标 记的X中顶点x,我们求得一条交替链。设其长度为2k+1,显然其中k条是匹配 边,k+1条是非匹配边。 (II)步骤(2)或(3)找不到可标记结点,而又不是情况(I)。 (4)当(2),(3)步骤中断于情况(I),则将交替链中非匹配边改为匹配边,原匹配边改为非 匹配边(从而得到一个比原匹配多一条边的新匹配),回到步骤(1),同时消除一切现有 标记。 (5)对一切可能,(2)和(3)步骤均中断于情况(II),或步骤(1)无可标记结点,算法终止 (算法找不到交替链). 以上算法说穿了,就是从二分图中找出一条路径来,让路径的起点和终点都是还没有匹配过的点,并且路径经过的连线是一条没被匹配、一条已经匹配过交替出现。找到这样的路径后,显然路径里没被匹配的连线比已经匹配了的连线多一条,于是修改匹配图,把路径里所有匹配过的连线去掉匹配关系,把没有匹配的连线变成匹配的,这样匹配数就比原来多1个。不断执行上述操作,直到找不到这样的路径为止。 下面给出此算法的一个例子:

算法学习:图论之用匈牙利算法求二分图的最大匹配

用匈牙利算法求二分图的最大匹配 什么是二分图,什么是二分图的最大匹配,这些定义我就不讲了,网上随便都找得到。二分图的最大匹配有两种求法,第一种是最大流(我在此假设读者已有网络流的知识);第二种就是我现在要讲的匈牙利算法。这个算法说白了就是最大流的算法,但是它跟据二分图匹配这个问题的特点,把最大流算法做了简化,提高了效率。匈牙利算法其实很简单,但是网上搜不到什么说得清楚的文章。所以我决定要写一下。 最大流算法的核心问题就是找增广路径(augment path)。匈牙利算法也不例外,它的基本模式就是: 可见和最大流算法是一样的。但是这里的增广路径就有它一定的特殊性,下面我来分析一下。 (注:匈牙利算法虽然根本上是最大流算法,但是它不需要建网络模型,所以图中不再需要源点和汇点,仅仅是一个二分图。每条边也不需要有方向。) 图1 图2 图1是我给出的二分图中的一个匹配:[1,5]和[2,6]。图2就是在这个匹配的基础上找到的一条增广路径:3->6->2->5->1->4。我们借由它来描述一下二分图中的增广路径的性质: (1)有奇数条边。 (2)起点在二分图的左半边,终点在右半边。 (3)路径上的点一定是一个在左半边,一个在右半边,交替出现。(其实二分图的性质就决定了这一点,因为二分图同一边的点之间没有边相连,不要忘记哦。) (4)整条路径上没有重复的点。 (5)起点和终点都是目前还没有配对的点,而其它所有点都是已经配好对的。(如图1、图2所示,[1,5]和[2,6]在图1中是两对已经配好对的点;而起点3和终点4目前还没有与其它点配对。) (6)路径上的所有第奇数条边都不在原匹配中,所有第偶数条边都出现在原匹配中。(如图1、图2所示,原有的匹配是[1,5]和[2,6],这两条配匹的边在图2给出的增广路径中分边是第2和第4条边。而增广路径的第1、3、5条边都没有出现在图1给出的匹配中。) (7)最后,也是最重要的一条,把增广路径上的所有第奇数条边加入到原匹配中去,并把增广路径中的所有第偶数条边从原匹配中删除(这个操作称为增广路径的取反),则新的匹配数就比原匹配数增加了1个。(如图2所示,新的匹配就是所有蓝色的边,而所有红色的边则从原匹配中删除。则新的匹配数为3。) 不难想通,在最初始时,还没有任何匹配时,图1中的两条灰色的边本身也是增广路径。因此在这张二分图中寻找最大配匹的过程可能如下: (1)找到增广路径1->5,把它取反,则匹配数增加到1。 (2)找到增广路径2->6,把它取反,则匹配数增加到2。 (3)找到增广路径3->6->2->5->1->4,把它取反,则匹配数增加到3。 (4)再也找不到增广路径,结束。 当然,这只是一种可能的流程。也可能有别的找增广路径的顺序,或者找到不同的增广路径,最终的匹配方案也可能不一样。但是最大匹配数一定都是相同的。 对于增广路径还可以用一个递归的方法来描述。这个描述不一定最准确,但是它揭示了寻找增广路径的一般方法:“从点A出发的增广路径”一定首先连向一个在原匹配中没有与点A配对的点B。如果点B在原匹配中没有与任何点配对,则它就是这条增广路径的终点;反之,如果点B已与点C配对,那么这条增广路径就是从A到B,再从B 到C,再加上“从点C出发的增广路径”。并且,这条从C出发的增广路径中不能与前半部分的增广路径有重复的点。 比如图2中,我们要寻找一条从3出发的增广路径,要做以下3步: (1)首先从3出发,它能连到的点只有6,而6在图1中已经与2配对,所以目前的增广路径就是3->6->2再加上从2出发的增广路径。 (2)从2出发,它能连到的不与前半部分路径重复的点只有5,而且5确实在原匹配中没有与2配对。所以从2连到5。

(完整版)成本会计期末考试试题及答案

2.采用简化的分批法,累计间接计人费用分配率( )。 A. 只是各批产品之间分配间接计人费用依据 B.只是各批在产品之间分配间接计人费用依据 C.即是各批产品之间又是完工产品与月末在产品之间分配间接计人费用的依据D.是完工产品与月末在产品之间分配间接计人费用的依据 3.制造费用( )。 A.都是直接计人费用 B.都是间接计人费用 C. 都是间接生产费用 D.既包括间接生产费用,又包括直接生产费用 6.技术经济指标变动对产品成本的影响主要表现在对( )指标的影响。 A. 产品总成本B,产品单位成本 C. 产品产量 D. 产品总成本和产品产量 8)。 A.“基本生产成本”B.“辅助生产成本” C. “制造费用”D.“管理费用” 9.简化分批法是( )。 A. 分批计算在产品成本的分批法B.不分批计算在产品成本的分批法 C.不计算在产品成本的分批法 D. 不分批计算完工产品成本的分批法 10.为基本生产车间租用设备预付的租金按月摊销时,应借记的账户是( )。 A.“待摊费用”账户B.贷记“预提费用”账户 C. “制造费用”账户 D. “基本生产成本”账户 二、多项选择题(每小题2分,共14分) 1.下列各项中,不属于工业企业费用要素的是( )。 A.废品损失 B. 外购燃料 C. 制造费用 D. 直接材料 E.工资及福利费 4.下列各项中,不属于产品生产成本项目的是( )。 A.外购动力 B. 工资费用 C. 折旧费 D. 直接材料 E.燃料及动力 5.下列项目中,属于制造费用的有( )。 A. 生产车间的保险费B.厂部办公楼折旧 C. 在产品盘亏和毁损D.低值易耗品摊销 E. 季节性停工损失 7.一般来说,企业应根据本单位( )等具体情况与条件来组织成本会计工作。 A. 生产规模的大小B.生产经营业务的特点 C. 成本计算方法D.企业机构的设置

图的匹配——匈牙利算法与KM算法

图的匹配 一、什么是图的匹配 1.图的定义 无向图:无向图G 是指非空有限集合V G ,和V G 中某些元素的无序对的集合E G ,构成的二元组(V G ,E G )。V G 称为G 的顶点集,其中的元素称为G 的顶点。E G 称为G 的边集,其中的元素称为G 的边。在不混淆的情况下,有时记V =V G ,E =E G 。如果V ={v 1,…,v n },那么E 中的元素e 与V 中某两个元素构成的无序对(v i ,v j )相对应,记e =v i v j ,或e =v j v i 。在分析问题时,我们通常可以用小圆圈表示顶点,用小圆圈之的连线表示边。 二分图:设G 是一个图。如果存在V G 的一个划分X ,Y ,使得G 的任何一条边的一个端点在X 中,另一个端点在Y 中,则称G 为二分图,记作G =(X ,Y ,E)。如果G 中X 的每个顶点都与Y 的每个顶点相邻,则称G 为完全二分图。 2.匹配的相关概念 设G =(V ,E)是一个图,E M ?,如果M 不含环且任意两边都不相邻,则称M 为G 的一个匹配。G 中边数最多的匹配称为G 的最大匹配。 对于图G =(V ,E),在每条边e 上赋一个实数权w(e)。设M 是G 的一个匹配。定义∑∈=m e e w M w )()(,并称之为匹配M 的权。G 中权最大的匹配称为G 的最大权匹配。如果 对一切,e ∈E ,w(e)=1,则G 的最大权匹配就是G 的最大匹配。 设M 是图G=(V ,E)的一个匹配,v i ∈V 。若v i 与M 中的边相关联,则称v i 是M 饱和点,否则称v i 为M 非饱和点。 如果G 中每个顶点都是M 饱和点,则称M 为G 的完美匹配。 设M 是G 的一个匹配,P 是G 的一条链。如果P 的边交替地一条是M 中的边,一条不是M 中的边,则称P 为M 交错链。类似地,我们可以定义G 的交错圈。易知,G 的交错圈一定是偶圈。 一条连接两个不同的M 非饱和点的M 交错链称为M 增广链。 两个集合S 1与S 2的“异或”操作S 1⊕S 2是指集合S 1⊕S 2=(S 1∩S 2)\(S 1∪S 2) 容易看出,设M 是G 的匹配,P 是G 中的M 增广链、则M ⊕P 也是G 的匹配,而且1+=⊕M P M 。 图表 1 “异或”操作 可以证明,G 中匹配M 是最大匹配当且仅当G 中没有M 增广链。

相关文档