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

1、分支定界法的思想是首先确定目标值的上下界分支定界法的思想是：首先确定目标值的上下界发布人：chengxu0921发布时间：2008-7-21 18:16:27新闻类别：分支-界限法例1：设有A,B,C,D,E 5人从事j1,j2,j3,j4,j5 5项工作每人只能从事一项,它们的效益表如下:j1j2j3j4j5AB131085C59774D5E求最佳安排,使效益最高？原文代码重写如下，希望增加点可读性。program PlanJob;const MAX_SIZE = 20;type TIntArray = array1.MAX_SIZE of Integer;PNode = Node; Nod

2、e = record Job2Man: TIntArray; / Job2Mann = m, job-n assign to person-m Man2Job: TIntArray; / Man2Jobn = m, person-n assign to job-m UpperVal: Integer; / upper value JobsDep: Integer; / jobs decided, as search depth Next: PNode;end;var CurNode: PNode; / Current node NewNode: PNode; / New branch node

3、 DelNode: PNode; / for delete GoalNode: PNode; / the goal GoalMaxVal: Integer; / goal max value CurMan, CurJob: Integer; / Current Man and Job of current Node Size: Integer; / Person number, also task number Values: array1.MAX_SIZE, 1.MAX_SIZE of Integer;function CalUpperValue(ANode: PNode): Integer

4、;var Res: Integer;Man, Job: Integer;JobMaxVal: Integer;begin Res := 0; with ANode do begin for Job := 1 to Size do begin if Job = JobsDep then begin Man := Job2ManJob;Res := Res + ValuesMan, Job;Continue;end;/ else find the max value for JobJobMaxVal := 0; for Man := 1 to Size do begin if (JobMaxVal

5、 = NextNode.UpperVal);PrevNode.Next := ANode;ANode.Next := NextNode;end;procedure PrintNode(ANode: PNode);var Man, Job: Integer;AllJobAssigned: Boolean;begin AllJobAssigned := true; for Job := 1 to Size do begin Man := ANode.Job2ManJob; if 0 Man then Writeln(Job , Job, assign to man ,Man, , value ,

6、ValuesMan, Job) else AllJobAssigned := false;end;Writeln; if AllJobAssigned then Writeln(Value = , ANode.UpperVal) else Writeln(UpperVal = , ANode.UpperVal);end;begin CurNode := InitNode();GoalMaxVal := 0; repeat CurJob := CurNode.JobsDep + 1; for CurMan := 1 to Size do begin if CurNode.Man2JobCurMa

7、n 0 then Continue;/ New search branchNew(NewNode);NewNode := CurNode;NewNode.JobsDep := CurJob;NewNode.Man2JobCurMan := CurJob;NewNode.Job2ManCurJob := CurMan;NewNode.UpperVal := CalUpperValue(NewNode); if NewNode.UpperVal GoalMaxVal then Dispose(NewNode) /discard this branch if smaller than limit e

8、lse Insert(NewNode, CurNode); if CurJob GoalMaxVal then begin GoalNode := NewNode; GoalMaxVal := GoalNode.UpperVal end; / if end; / for CurMan DelNode := CurNode;CurNode := CurNode.Next;Dispose(DelNode);until (CurNode.UpperVal = GoalMaxVal) or (CurNode = nil); / end of repeat PrintNode(GoalNode);Rea

9、dln;end.input.txt:7131085597745output:Job 1 assign to man 4, value 15Job 2 assign to man 5, value 11Job 3 assign to man 2, value 10Job 4 assign to man 3, value 7Job 5 assign to man 1, value 7Value = 50如果扩展为10*10,input.txt:10597745597745运行约两分钟。output :Job 1 assign to man 9, value 15Job 2 assign to man 5, value 11Job 3 assign to man 2, value 10Job 4 assign to man 8, value 7Job 5 assign to man 6, value 7Job 6 assign to man 4, value 15Job 7 assign to man 10, value 11Job 8 assign to man 7, value 10Job 9 assign to man 3, value 7Job 10 assign to man 1, value 7Value = 100