学生面试问题

July,2007　ICSINPRACTICEANDTHEORY学生面试问题

吴值民,　邹波,　康兴挡

指导老师:卢厚清

(解放军理工大学工程兵工程学院,南京　210007)

摘要:　在求解本题时,先对题中提出了四个要求进行相应的数学处理,处理的方法是将四个定性要求转化为定量化约束条件或目标函数,建立了每个问题的数学模型,借鉴组合数学中的平衡不完全区组设计相关概念和方法对问题一和问题三第一问进行了求解,得到了固定学生人数时老师人数的下限公式,构造一种启发式搜索算法再对问题一和问题三进行求解,得到问题一和问题三的确切老师人数近似最小值,经过分析求解过程和结果,指出算法的优缺点,并利用启发式算法对问题二进行求解,提出一种矩阵编码的遗传算法也对问题二和问题三第二问进行求解,对上述两种算法求解结果进行了分析比较,给出了最后的结果,阐明了算法的有效性.

关键词:　区组设计;启发式搜索;遗传算法

1　对要求的处理

　　题中提出了四个方面的定性要求Y1—Y4,建立相应数学模型时,先要对它们进行处理:

1)定性要求转化为定量化的指标,用老师面试学生数量的方差来度量老师面试学生数量的均衡性;用关联矩阵变量计算出任意两考生的“面试组”中有两位、三位、四位相同老师数量总和;求出被任意两位老师面试的两个学生集合中出现相同学生的人数的最大值.

2)确定性的要求转化为约束条件,非确定性要求转化为目标函数.

2　数学模型的建立

引入关联矩阵Q,其元素为xij,表示学生与老师的面试关系,即

xij=

0　第i名老师不面试第j名学生1　第i名老师面试第j名学生

　(i=1,2,…,M,j=1,2,…,N)(1)

利用问题一至三对要求满足的不同情况,按照对要求处理方法,很容易建立数学模型,这里只给出问题二的数学模型,是一个多目标非线性0—1规划问题.其余几个问题模型与之类似.问题二的数学模型为:

(2)min[f1;f32;f33;f4]

M

∑x

i=1M

ij

=4j=1,…,Nj,k=1,…,N

i=1,…,M,j=1,…,N

s.t.

∑

i=1

(xij×xik)<4

(3)

xij=1,0

收稿日期:2007203201

14期吴值民,等:学生面试问题139

其中,

M

N

ij

∑∑x

ffff

1

-

1MM

M

MN

ij

====

i=1j=1∑∑x

i=1j=1ki

2

N-1N

32

∑∑D∑x

i=1j=i+1

N

k=1M

N-1

×xkj-2×xkj-3

N

33

∑∑D∑x

i=1j=i+1

k=1

ki

4

i=1,…,M,j=1,…,M且i≠j

max

∑x

k=1

ik

×xjk

其中D(x)为符号函数,

D(x)=

0　x≠01　x=0

3　组合数学方法组合数学[1]中有一个平衡不完全区组设计的定义,可以借鉴其中的概念和方法对问题一和问题三的第一问进行求解.平衡不完全区组设计的定义为:设X={x1,x2,…,xv}是v个元素的集.X的一个平衡不完全区组设计是b个k2子集组成的族(诸k2子集记为B1,B2,…,Bb,也叫做区组),合于下列条件:

1)每一元在b个区组的恰恰r个出现;

2)每两个元在b个区组的恰恰Κ个中同时出现;

3)k),则参数平衡不完全区组有一个必要条件:一个平衡不完全区组的参数为(b,v,r,k,Κ

满足等式:bk=vr和r(k-1)=Κ(v-1).

定理　当学生数量N>1,在一个满足条件的面试方案中,若任意两个老师的组合都在“面试组”出现且仅出现一次,则分配的方案是平衡不完全区组.

证明　任意两老师的组合都在“面试组”中出现,则每一个老师面试学生人数相同,设为

r,满足定义中的条件1;任意两老师的组合都在“面试组”出现且仅出现一次,即分配方案满

足每两个元在N个区组中恰恰Κ=1次出现,满足条件2;k=4,当N>1时,M=v>4,则k对于问题一中面试组中不出现两位老师相同的情形,若存在任意两老师的组合都在“面试组”中出现的面试方案,则显然老师资源已最大化利用,老师人数最少,由定理可知,参数满足下列公式

kN=Mrr(k-

1)=Κ(M-1)1+(4)

1+48N.在一般情况下,对一个特定的

2

学生数N来说,不一定能得到一个任意两老师都在面试组中出现的情形,如N=2,需要老

其中k=4,Κ=1,得到老师人数M值M=

师数为7,无法使任意两老师组合都在面试组中出现,设平均每位老师面试人数为r,r不一

140数　学　的　实　践　与　认　识37卷

定为整数,对一个特定的老师来说,他与其它老师能组成的两两组合总数量为:M-1,一定是大于等于实际面试方案中平均与其它老师组成的两两组合的数量.则得到如下公式:

4N=Mr

(5)

3rΦM-1

由于M,r和N都大于0,对不等式进行求解所以老师数应该满足下列公式

MΕ

1+1+48N2

(6)

　　借鉴该方法,求得问题一中面试组中没有三位老师相同的情形老师数满足的公式为:

(7)M(M-1)(M-2)Ε24N　　问题三中的第一问求解方法,与上相同,这里给出问题三第一问中不出现两位老师相同的求解过程.当文理老师各一半时,设老师面试学生数平均值为r,对M󰃗2个文科老师和M󰃗2个理科老师来看,组成的两两组合只能为“文文”,“理理”,“文理”,其中“文文”和“理理”情形相同,分别求出能组成的总数量为:

2

“文文”:CM:M2󰃗4,从一个面试组来看,一个面试组需“文文”组合为1个,需󰃗2,“文理”“文理”为4个,在当老师数M>4时,显然有下式成立:

CM󰃗22

1

>

M󰃗42

4

(8)

　　说明“文文”组合相对于“文理”组合有多余,所以在最理想的情况下,“文理”组合都在面试组中出现,这时老师人数也会最少.对于一般情况,对一特定的老师来说,他与其它老师能组成的“文理”组合数量为:M󰃗2,一定是大于等于平均每个老师在面试组与其它老师组成的“文理”组合数量,则得到下列不等式:

4N=Mr

(9)

2rΦM󰃗2

求解得到老师人数下限,如公式(10)所示,当每一个“文理”组合都在面试组中出现时,取等号.

MΕ4M

3

N

(10)(11)

问题三第一问,若面试组中不出现三位老师相同的情形,则老师人数满足下列公式:

-2M2Ε32N

4　启发式搜索算法

4.1　基本思想

设计一个基于状态变化的搜索系统S.设为

S={s1,s2,…,sn},nΦN

(12)

其中,sj={tj1,tj2,tj3,tj4},Sj对应一名学生,tj1,tj2,tj3,tj4对应给该学生面试的四名老师.学生与老师的面试关系即为系统的一种状态.当前系统中有n名学生则称处于n状态.4.2　基本做法

在n14期吴值民,等:学生面试问题141

改变系统状态指打乱学生与老师间的面试关系,重新搜索组合,形成新的n状态,再试图增加学生,若多次操作都无法成功,则加入新老师.

加入新老师有两种做法:一是在不改变系统的状态,加入老师后试图加入学生,进行搜索;二是改变之前n个学生与老师的面试关系,整体重新搜索,使系统到达另一种n状态,在新的状态下搜索出可行的老师组合来加入新学生.

这样直到所有学生都被加入,则老师的人数也是近似最少的.而且也得到老师与学生的面试表.

在实际操作过程中,为了提高搜索效率和速度,设计了两个检验.

老师检验:在系统中给新增加的学生确定面试老师时,对准备加入到该生的面试组的老师进行是否满足约束条件的检验,若老师满足条件,则认为该老师通过检验,否则认为未通过检验.

学生检验:在准备加入新学生时,在不改变系统其它学生与老师面试关系前提下,搜索看是否能够找到满足条件的四名老师,若能找到,则将这名学生加入系统,称这名学生通过准入检验,否则认为这名学生未通过准入检验.4.3　几种启发式算法1)择优搜索.在系统中试图加入新的学生时,优先找系统中面试学生人数最少的老师.但加入这名学生后,不改变系统中以前的学生与老师间的面试关系.找不到,就认为准入检验失败.加入一名老师后,再用上面的方法搜索.

2)均度优先搜索.在系统中试图加入新的学生时,按择优搜索的方法进行搜索,当学生准入检验失败,则加入一名老师,加入老师后,先打断系统中所有学生与老师的面试关系,重新搜索组合,按每次都试图找面试数最少的老师的原则,将学生加入.

3)回溯均度优先搜索.当需加入新学生时,学生准入检验失败,则先打乱系统中学生与老师的面试关系,重新搜索组合,从一种n状态转化到另外一种n状态,多次试验都无法搜索出一个可加入新学生的方案,则需加入新老师.加入老师后,也是先打乱系统中学生与老师的面试关系,再按均度优先方法重新搜索组合.4.4　求解结果分析

在图1中,前两张图左边为任意两面试组中不出现两位老师相同的启发式搜索算法求解结果,右边为任意两面试组中不出现三位老师时启发式搜索算法求解结果.其中红线为利用组合数学方法得到公式的计算结果,没有经过向上取整;绿线为择优搜索求解结果,蓝线为均度优先搜索结果,由于采用回溯机制后计算量会大增,在图1的后两张图中给出规模小的情况下回溯均度优先搜索结果,在图中可以看到,回溯均度优先搜索结果最优,所需老师数量最少,搜索结果中有几个点与落在线线上,说明在这种情况下,老师资源得到最大化利用,所有老师的组合都在面试组中出现.

对问题三启发式搜索算法求解结果与之类似.4.5　启发式搜索算法的优点

1)每个解都有确定的面试方案对应;

2)提供老师人数最小值M确实可行,也有指派方案可供参考;

3)与组合数学方法推导的公式相比差距不大,说明启发式算法效率高;4)条件可以任意扩充或减少.利用相同的方法,在其它条件下,也可以求解类似问题.

142数　学　的　实　践　与　认　识37卷

图1　问题一启发式搜索算法求解结果

5　遗传算法

从问题二的数学模型可以看到这是一个多目标的非线性0—1规划问题,常规整数规划方法难以求解,可以考虑用智能算法中的遗传算法[2]进行求解.5.1　矩阵编码

在遗传算法中,待解问题的一个解从表现型到基因型的映射称为编码,实质是解的一种向量表示方法,最初遗传算法是采用二进制编码方法,该方法操作简便,但不能反映问题的特定知识.针对实际问题可以采用特定编码,以利于问题求解.对于此模型,一个解即具体分配方案表示为X=(xij)M×N,可以将矩阵每一列当成一个整体,当成染色体表示中的一个基因位,该基因位中只有4个元素为1,其余为0,显然第k个基因位确定了第k名学生被面试的4名老师.这种表示的好处就是遗传算子在进行运算时,是对于染色体的基因部分进行操作,即采用矩阵编码方法.编码如图2所示.

图2　矩阵编码方法

14期吴值民,等:学生面试问题143

5.2　适应值函数

对于多目标问题,先将多目标综合成单目标,多目标综合方法有很多,这里采用线性加权求和的方法,其中权值由目标值优先级别、自身数量级决定.本小组经过多次试验,由各计算出的各目标值的数量级确定权重.

设总目标为f,权值分别为w1、w2、w32、w33、w4.则得到该个体适应值函数,且适应值越小则该个体越优.

f=w1f

1

+w2f2+w32f

32

+w33f

33

+w4f

4

(13)

5.3　交叉算子

遗传算法中的所谓交叉运算,是指对两个相互配对的染色体按某种方式相互交换其部分基因,从而形成两个新的个体.在本文的遗传算法中,种群中每个个体的每一个基因位,为一名学生被面试的老师的分配方案,选中的父代种群中的两个体X、Y进行单点交叉或多点交叉,交换相同基因位对应的所有数据,相当于在两种不同的方案中交换相同学生被面试的老师分配方案,得到两种新的分配方案,对于本模型,由于所计算的数据量较大,故采用多点交叉.这里只给出单点交叉的示意图,设新个体为X′、Y′,单点交叉如图3所示,i为随机生成交叉点.图3　单点交叉

5.4　两代竞争,稳态遗传

在标准遗传算法中,常根据个体的适应度大小采用“赌轮选择”策略,该策略简单实用,但容易引起“早熟收敛”和“搜索迟钝”问题.有效的解决方式是采用保优策略,采取了精英个体保留策略和锦标赛方法.本文的做法为,父代种群先经过自适应选择、交叉和变异后生成当代种群,当代种群的个体与父代种群较优的一部分个体共同竞争产生下一代种群.可以即适当加大交叉、变异概率,让在当代中产生更多新的个体和基因,有利于两代竞争时在更多个体和基因中择优,这样扩大染色体的选择范围,加大了适应度好的染色体被选中的概率,可以有效提高搜索效率.

6　启发式搜索算法与遗传算法求解结果

144数　学　的　实　践　与　认　识

表1　问题二求解结果

搜索方法承上择优搜索均度优先搜索遗传算法

两老师相同次数

882687068287

37卷

三个老师相两老师最面试同次数

0431

老师最少面试学生数

216361

老师最多老师面试

相同学生数

111210

面试学生数学生数方差

686465

820.16671.24

表2　问题三第二问求解结果

搜索方法均度优先搜索遗传算法

两老师相同次数

87778717

三个老师相两老师最面试同次数

491178老师最少面试学生数63

老师最多老师面试相同学生数2014面试学生数学生数方差64

0.16672.1449

参考文献:[1]　LiuCL.组合数学导论[M].成都:四川大学出版社,1987.

[2]　玄光男,程润伟.遗传算法与工程优化[M].北京:清华大学出版社,2004.[3]　蔡锁章.数学建模原理与方法[M].北京:海洋出版社,2000.[4]　蔡锁章.数学建模原理与方法[M].北京:海洋出版社,2000.

StudentInterviewProblem

WUZhi2min,　ZOUYun2bo,　KANGXing2dang

(EngineeringInstituteofEngineeringCorps,PLAUniversityof

Sci&Tech,Nanjing210007,China)

Abstract:　Inordertosolvetheproblem,thequalitativerequestsweretransformedinto.Themathematicmodelswereestablished.relevantquantitativerestrictsorobjectfunctions

Therelativeconceptsandmethodofbalancedincompleteblockdesignwereusedforreferencetosolvethefirstquestionandthethirdquestion.Thefloorlevelformulaofteacherswasdeducedwiththemethodmentionedabove.Aheuristicsearchalgorithmwasestablishedtosolvethefirstandthethirdquestionsagainandtheapproximateleastnumbersofteachersweregot.Thestrongpointandshortcomingsofalgorithmwerepointedoutafteranalyzetheprocessandresults.Thesecondquestionwassolvedwiththeheuristicalgorithmmentionedaboveandgeneticalgorithmbasedonmatrixcoding.Thegeneticalgorithmbasedonmatrixcodingwasalsoappliedonthethirdquestion.Thetwomethodsthispaperpresentedandtheirrespectiveresultswerecomparedandanalyzed.Theconclusionwasgivenoutandthemethodswere.effectiveaftertheanalysis

Keywords:　blockdesign;heuristicsearch;geneticalgorithm