最佳调度问题（C语言）--回溯法

灰太狼 2022-01-05 10:59 346阅读 0赞

## ***N后问题*** ##

*转载于： [https://blog.csdn.net/qq\_35524157/article/details/79048737][https_blog.csdn.net_qq_35524157_article_details_79048737] 的JAVA版本*

**题目描述**  
有n个任务由k个可并行工作的机器完成。完成任务i需要的时间为Ti。  
找出完成这n个任务的最佳调度，使得完成全部任务的时间最少。用文件导入每个任务所需要的时间Ti

**解题思路**  
回溯法是从初始状态出发，在隐式图中以深度优先的方式搜索问题的解。  
当发现不满足求解条件时就回溯，尝试其他路径，即“能进则进，进不了则换，换不了则退”的基本搜索方法。

**算法设计**  
:①问题解的形式：最佳调度算法的解表示成n元组的形式（X1，X2，…，Xn），  
其中Xi（i=1,2…，n）表示第i个任务放在第Xi个机器上处理。  
②显约束： 当前容器处理时间与新加入该容器任务比最少时间短。  
③隐约束：当前时间比最少时间短。  
④解空间：根据显约束第i个任务有k个机器可以选择，显然满足显约束的n元组共有kn种，他们构成了最佳调度问题的解空间。

**具体代码实现**

#include<stdio.h>
    #include<math.h>
    #define MAX 100
    #define MAX_VALUE 32767
    
    int a[3][MAX]={0};		//用于存放调度任务的信息，第1行为任务编号，第2行为任务所需时间，第3行为调度结果
    int s[MAX]={0};			//表示当前机器需要工作的时间
    int nbest[MAX]={0};		//表示当前调度结果
    int minn=MAX_VALUE;		//表示调度后的最少时间
    int n;					//表示任务数
    int k;					//表示机器数
    
    //向文件读入一个数字 
    void fileWriteInt(int i){
    	FILE *fp;
    	fp = fopen("i:\\算法\\回溯法\\output.txt", "a");
    	
    	if (fp == NULL) {			//若打开文件失败则退出
            printf("不能打开文件！\n");
            return ;
        }
    	
    	fprintf(fp,"%d\n",i); 
    	
    	fclose(fp);	
    }
    
     //从文件读取数据 
    void fileRead(){
    	FILE *fp;
    	fp = fopen("i:\\算法\\回溯法\\input.txt", "r");
    	if (fp == NULL) {			//若打开文件失败则退出
            printf("不能打开文件！\n");
            return ;
        }
     	//从文件中读任务数n和机器数k 
        fscanf(fp,"%d",&n);
        fscanf(fp,"%d",&k);
    		
    	
    	//从文件中读取集合S中的n正整数元素
    	for(int i=1;i<=n;i++){
    		a[0][i]=i;
    		fscanf(fp,"%d",&a[1][i]);
    		a[3][i]=0;
    	}
    	
    	fclose(fp);	
    }
    
    void search(int x,int y){        
            //最佳调度算法
            if(y>minn)      //隐约束剪枝
                return;
            if(x>n){        //到达叶结点
                if(y<minn){     //判断最优解，更新最优解和最优值
                    minn = y;       
                    for(int i=1;i<=n;i++){
                        a[2][i] = nbest[i];
                    }
                }
                return;
            }
            for(int i=1;i<=k;i++){
                if(s[i]+a[1][x]<minn){      //显约束剪枝
                    s[i] += a[1][x];
                    nbest[x]=i;
                    search(x+1,fmax(y,s[i]));        //递归
                    s[i] -= a[1][x];
                }
            }
            return;
        }
    
    
    int main(){
    	fileRead();
    	search(1,0);
    	fileWriteInt(minn);
    	return 0;
    }

[https_blog.csdn.net_qq_35524157_article_details_79048737]: https://blog.csdn.net/qq_35524157/article/details/79048737