算法-回溯法解决最佳调度问题

冷不防 2022-07-24 08:10 226阅读 0赞

> **问题：**
> 
> 假设有 n 个任务由 k 个可并行工作的机器来完成。完成任务 i 需要时间为ti ，设计完成这 n 个任务的最佳调度算法，使得完成全部任务的时间最早。
> 
> **算法设计：**
> 
> 　　从n个作业中找出有最小完成时间和的作业调度，所以批处理作业调度问题的解空间是一棵排列树。按照回溯法搜索排列树的算法框架，设开始时t=\[1,2, ... , n\]是所给的n个作业的完成时间，则相应的排列树由t\[1:n\]的所有排列构成。
> 
> 　　数组len\[\]用于存储一组空间解，comp()函数用于计算一个完整调度的完成时间，search()函数用来做搜索，best记录相应的当前最佳作业调度完成时间。
> 
> 　　当dep>n时，算法搜索至叶子结点，得到一个新的作业调度方案。此时算法适时更新当前最优值和相应的当前最佳调度。
> 
> 　　当dep<n时，若当前扩展结点位于排列树的第（n-1）层，此时算法选择下一个要安排的作业进行搜索且向第(n-2)层回溯，以深度优先方式递归的对相应的子树进行搜索，对不满足上界约束的结点，则剪去相应的子树向第(n-2)层回溯。
> 
>     #include<stdio.h>
>     int n=7,k=3,best=66666;
>     int len[99];
>     int t[99]={2,14,4,16,6,5,3};
>     int comp(){
>     	int tmp=0;
>     	for(int i=0; i<k; i++)
>     		if(len[i]>tmp)
>     			tmp=len[i];
>     	return tmp;
>     }
>     void search(int dep,int *len,int *t){
>     	if(dep==n) {
>     		int tmp=comp();
>     		if(tmp<best)
>     			best=tmp;
>     		return;
>     	}
>     	for(int i=0; i<k; i++) {
>     		len[i]+=t[dep];
>     		if(len[i]<best)
>     			search(dep+1,len,t);
>     		len[i]-=t[dep];
>     	}
>     }
>     int main(){
>     	int i;
>     	for (i=0; i<k; i++)
>     		len[i]=0;
>     	search(0,len,t);
>     	printf("%d\n",best);
>     	return 0;
>     }
> 
>   
>   
> 
> 
>   
> 参考博文：http://www.acmerblog.com/backtracking-3-2937.html