分支定界法的思想是首先确定目标值的上下界.doc

《分支定界法的思想是首先确定目标值的上下界.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分支定界法的思想是：首先确定目标值的上下界发布人：chengxu0921 发布时间：2008-7-2118:16:27 新闻类别：分支-界限法例1：设有A,B,C,D,E5人从事j1,j2,j3,j4,j55项工作每人只能从事一项,它们的效益表如下:　j1j2j3j4j5A13111047B13101085C59774D151210115E1011884求最佳安排,使效益最高？ 原文代码重写如下，希望增加点可读性。 programPlanJob;constMAX_SIZE=20;type TIntArray=array[1..MAX_SIZE]ofInteger; PN

2、ode=^Node; Node=record   Job2Man:TIntArray;    //Job2Man[n]=m,job-nassigntoperson-m   Man2Job:TIntArray;   //Man2Job[n]=m,person-nassigntojob-m   UpperVal:Integer;//uppervalue   JobsDep:Integer;  //jobsdecided,assearchdepth   Next:PNode; end;var  CurNode:PNode;     //Currentnode  NewNode

3、:PNode;     //Newbranchnode  DelNode:PNode;     //fordelete  GoalNode:PNode;    //thegoal  GoalMaxVal:Integer;//goalmaxvalue  CurMan,CurJob:Integer;    //CurrentManandJobofcurrentNode  Size:Integer;      //Personnumber,alsotasknumber  Values:array[1..MAX_SIZE,1..MAX_SIZE]ofInteger;functi

4、onCalUpperValue(ANode:PNode):Integer;var Res:Integer; Man,Job:Integer; JobMaxVal:Integer;begin Res:=0; withANode^do begin   forJob:=1toSizedo   begin     ifJob<=JobsDepthen     begin       Man:=Job2Man[Job];       Res:=Res+Values[Man,Job];       Continue;     end;     //elsefindthemaxval

5、ueforJob     JobMaxVal:=0;     forMan:=1toSizedo     begin       if(JobMaxVal

6、eger; FInput:Text; Res:PNode;begin Assign(FInput,'input.txt'); Reset(FInput); Read(FInput,Size); Readln(FInput); forMan:=1toSizedo begin   forJob:=1toSizedo     Read(FInput,Values[Man,Job]);   Readln(FInput); end; New(Res); withRes^do begin   forMan:=1toSizedo   begin     Man2Job[Man]:=0

7、;     Job2Man[Man]:=0;   end;   JobsDep:=0;   UpperVal:=CalUpperValue(Res);   Next:=nil; end; InitNode:=Res;end;procedureInsert(ANode:PNode;From:PNode);var PrevNode,NextNode:PNode;begin NextNode:=From; repeat   PrevNode:=NextNode;   NextNode:=PrevNode^.Next; until(NextNod