《算法設(shè)計與分析》實驗報告5

?

實驗名稱: 作業(yè)調(diào)度問題

系????別:xxx???????????

專????業(yè):xxx? ? ? ? ? ?

班????級:xxx

姓????名:xxx? ? ? ? ??

學(xué)????號:xxx

實驗日期:xx年xx月xx日

1. ?算法題目

根據(jù)回溯法的設(shè)計思想和算法步驟，要求學(xué)生設(shè)計一個回溯算法，用于解決作業(yè)調(diào)度的問題。作業(yè)調(diào)度問題，作為經(jīng)典的組合問題，需要考慮所有任務(wù)的全排列。帶有回溯的遞歸調(diào)用，可以在中間環(huán)節(jié)中發(fā)現(xiàn)回溯后的后續(xù)操作是否還有必要繼續(xù)進行的可能性，從而實現(xiàn)剪枝，減少搜索n!空間的范圍。因此帶回溯的搜索算法可以解決該問題，至少在時間效率上有很大的提高。

?

2. ?設(shè)計思路與步驟

答：1 初始化變量X[i]

?2 設(shè)置解空間的第一個位置的值

3 對每一個x屬于Sk 循環(huán)執(zhí)行下列操作 k>=1

??3.1 Xk=x

??3.2 將Xk加入X

??3.3 if(X是最終解) 輸出結(jié)果bestTime

??3.4 if(X是部分解) 填寫下一個位置 k = k + 1;

??3.5 else 回溯，恢Xk和k:x[k] = -1; k = k - 1; ??

?

3. ?算法實現(xiàn)與代碼

?

#include<stdio.h>

//const int n = 3;

#define N 3

int BatchJob(int a[], int b[], int n);

?

int main()

{

int a[N] = { 2, 5, 4 }, b[N] = { 3, 2, 1 };

int bestTime = BatchJob(a, b, 3);

printf("最短作業(yè)時間是：%d\n", bestTime);

return 0;

}

?

int BatchJob(int a[], int b[], int n)

{

int i, j, k;

int x[10], sum1[10], sum2[10];

int bestTime = 1000; ????????????????????//假定最后完成時間不超過1000

for (i = 1; i <= n; i++)

{

x[i] = -1;

sum1[i] = 0;

sum2[i] = 0;

}

sum1[0] = 0; sum2[0] = 0;

k = 1;

while (k >= 1)

{

x[k] = x[k] + 1;

while (x[k] < n)

{

for (i = 1; i < k; i++) ??????//檢測作業(yè)x[k]是否重復(fù)處理

if (x[i] == x[k])

break;

if (i == k) { ?????????????//作業(yè)x[k]尚未處理

sum1[k] = sum1[k - 1] + a[x[k]];

if (sum1[k] > sum2[k - 1]) sum2[k] = sum1[k] + b[x[k]];

else sum2[k] = sum2[k - 1] + b[x[k]];

if (sum2[k] < bestTime)

break;

else

x[k] = x[k] + 1;//剪枝

}

else x[k] = x[k] + 1; ????????????//作業(yè)x[k]已處理

}

if (x[k] < n && k == n) ???????//得到一個作業(yè)安排

if (bestTime > sum2[k]){

bestTime = sum2[k];

printf("最短的作業(yè)安排是：");

for (j = 1; j <= n; j++)

printf("%d ",x[j] + 1);

////數(shù)組下標從0開始，打印作業(yè)編號從1開始

}

?

if (x[k] < n && k < n)

k = k + 1; ????????????????????//是解的子集，安排下一個作業(yè)

else { ?

x[k] = -1; k = k - 1; ????????????//重置x[k]，回溯

}

}

return bestTime;

}

?

4. ?測試用例與結(jié)果

?

5. ?問題與總結(jié)

答：xxx。