分支定界之深度搜索定界

深度搜索定界

原文 http://it.pjschool.com.cn/Article/ArticleShow.asp?ArticleID=231

原文题为分支定界, 深度搜索定界是其中例2,
例1代码已重写为 http://blog.csdn.net/jq0123/archive/2006/05/30/762957.aspx
此为例2代码重写.

根据 http://www.skyheart.com.cn/html/DATASTRUCTE/20060528103723307.htm
分支定界 (branch and bound) 算法是一种在问题的解空间树上搜索问题的解的方法。但与回溯算法不同，分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树，并且，在分支定界算法中，每一个活结点只有一次机会成为扩展结点。
些例不算是分支定界算法, 而是回溯算法, 应用了限界函数（ bounding function）来定界.

原代码对于如下数据输出为27，错误。
3 12
11 7 5 5 4 7
11 7 5 5 4 7

输出应为
11 11 4
7 7 7 5
7 5 5 5 4
Time=26

{
http://it.pjschool.com.cn/Article/ArticleShow.asp?ArticleID=231

分支定界法的思想是：首先确定目标值的上下界，边搜索边减掉搜索树的某些支，提高搜索效率。

2. 2 深度搜索定界

例2：设定有n台处理机p1，p2，......pn,和m个作业j1,j2,...jm,处理机可并行工作,作业未完成不能中断，作业ji在处理机上的处理时间为ti,求解最佳方案,使得完成m项工作的时间最短?

说明：本题有两重搜索法，搜索处理机和搜索作业，当m，n较大时，搜索处理机不可能？搜索作业容易确定上下界，容易剪支。

若输入文件是：

3 6
11 7 5 5 4 7

输出结果如下：

7 7

5 5 4

11

time=14　

}
program Jobs;

const
MAXN = 100;
MAXM = 1000;

var
JobReqTime: array[1..MAXM] of Integer;

// jobs count on processor-I
JobNums, BestJobNums: array[1..MAXN] of Integer;

// TimeBlocks[Proc, Seq]: the Seq block time of Proc
// TimeBlocks[2, 4] = 12 means processor-2's 4th job requires 12 time.
TimeBlocks, BestTmBlocks: array[1..MAXN, 1..MAXM] of Integer;

MaxTimeTotal: Integer; // = ProcUsedTime[1]
ProcUsedTime: array[1..MAXN] of Integer;
JobDone: array[1..MAXM] of Boolean;
Least: Integer;
I, J: Integer;
FreeProc: Integer;
ProcNum, JobNum: Integer; // Number of Processors and Jobs
Rest: Integer;

procedure print;
var
I, J: Integer;
begin
for I := 1 to ProcNum do
begin
for J := 1 to BestJobNums[I] do
Write(BestTmBlocks[I, J], ' ');
Writeln;
end ;
Writeln('Time=', MaxTimeTotal);
end;

procedure InitReadParams;
var
F: Text;
I, J: Integer;
temp: Integer;
begin
Assign(F, 'input.txt');
Reset(F);
Readln(F, ProcNum, JobNum);
Rest := 0;
for I := 1 to JobNum do
begin
Read(F, JobReqTime[I]);
Inc(Rest, JobReqTime[I]);
end;
Close(F);

Least := Trunc(Rest div ProcNum); { 确定下界 }

// Sort requested times, decsending.
for I := 1 to JobNum - 1 do
for J := I + 1 to JobNum do
if JobReqTime[I] < JobReqTime[J] then
begin
temp := JobReqTime[I];
JobReqTime[I] := JobReqTime[J];
JobReqTime[J] := temp;
end;
end;

{
Processor can reject job if required time too much.
1. ProcUsedTime[] should less than MaxTimeTotal
2. ProcUsedTime[] should not ascend
}
function ProcRejectJob(AProc, AJob: Integer): Boolean;
var
NewUsedTime: Integer;
begin
NewUsedTime := ProcUsedTime[AProc] + JobReqTime[AJob];
if 1 = AProc then
ProcRejectJob := NewUsedTime >= MaxTimeTotal
else
ProcRejectJob := NewUsedTime > ProcUsedTime[AProc - 1];
end;

procedure AddJobToProc(AJob, AProc: Integer);
begin
Inc(JobNums[AProc]);
TimeBlocks[AProc, JobNums[AProc]] := JobReqTime[AJob];
Inc(ProcUsedTime[AProc], JobReqTime[AJob]);
Dec(Rest, JobReqTime[AJob]);
end;

procedure RemoveJobFromProc(AJob, AProc: Integer);
begin
Dec(JobNums[AProc]);
Dec(ProcUsedTime[AProc], JobReqTime[AJob]);
Inc(Rest, JobReqTime[AJob]);
end;

{ 从AJob..JobNum中选取作业放在处理机AProc上 }
procedure SearchFrom(AJob, AProc: Integer);
var
I: Integer;
begin
if MaxTimeTotal = Least then Exit;

for I := AJob to JobNum do
begin
if JobDone[I] then Continue;
if ProcRejectJob(AProc, I) then Continue;

JobDone[I] := True;
AddJobToProc(I, AProc);
// try to add more jobs
SearchFrom(I + 1, AProc);
RemoveJobFromProc(I, AProc);
JobDone[I] := False;
end; // for I

if Rest = 0 then
begin
BestJobNums := JobNums;
BestTmBlocks := TimeBlocks;
MaxTimeTotal := ProcUsedTime[1]; // ProcUsedTime[1] is always the largest
end
else if Rest > (ProcNum - AProc) * ProcUsedTime[AProc] then
Exit // stop this search branch
else if AProc < ProcNum then
SearchFrom(1, AProc + 1);

end;

begin
InitReadParams;

{ 确定上界 }
FillChar(ProcUsedTime, SizeOf(ProcUsedTime), 0);
FillChar(BestTmBlocks, SizeOf(BestTmBlocks), 0);
FillChar(BestJobNums, SizeOf(BestJobNums), 0);
for I := 1 to JobNum do
begin
// find the most free proccessor
FreeProc := 1;
for J := 2 to ProcNum do
if ProcUsedTime[J] < ProcUsedTime[FreeProc] then FreeProc := J;

// assign job-I to most free proc
ProcUsedTime[FreeProc] := ProcUsedTime[FreeProc] + JobReqTime[I];
BestJobNums[FreeProc] := BestJobNums[FreeProc] + 1;
BestTmBlocks[FreeProc, BestJobNums[FreeProc]] := JobReqTime[I];
end;

MaxTimeTotal := 0;
for I := 1 to ProcNum do
if ProcUsedTime[I] > MaxTimeTotal then
MaxTimeTotal := ProcUsedTime[I];

// start to search
FillChar(JobDone, SizeOf(JobDone), False);
FillChar(ProcUsedTime, SizeOf(ProcUsedTime), 0);
FillChar(TimeBlocks, SizeOf(TimeBlocks), 0);
FillChar(JobNums, SizeOf(JobNums), 0);
SearchFrom(1, 1);

print;
ReadLn;
end.