最佳调度问题(回溯算法)

{
if( time_machine[i] > time_max_K )
time_max_K = time_machine[i];
}
if(time_max_K<time_min)
{
time_min = time_max_K;
for(inti=1;i<=N;i++)
Res[i] = x[i];
}
}
else
{
for(inti=1;i<=K;i++)
{
x[k] = i;
if( placetest(k) )
{
time_machine[i] += t[k];
Backtrack(k+1,t,x);
time_machine[i] -= t[k];
}
}
}
}
三、结果与分析：
附录（源代码）
算法源代码（C++描述）
/*
}
if(time_max_K > time_min)
return false;
else
return true;
}
void Backtrack(int k,int t[],int x[])
{
if(k > N )
{
int time_max_K = time_machine[1];
for(int i=2;i<=K;i++)
结点；直至找到一个解或全部解。
二、核心代码：
boolplacetest(intk)
{
inttime_max_K = time_machine[1];
for(inti=2;i<=K;i++)
{
if( time_machine[i] > time_max_K )
time_max_K = time_machine[i];
{
cout << "请输入任务个数和机器个数："<<endl;
cin >> N >> K;
if( N <= K)
{
cout << "最短运行时间即为任务中时间最长者！"<<endl;
return 0;
}
int *t = new int[N+1];
int *x = new int[N+1];
cout << "请分别输入"<< N<<"个任务时间：" <<endl;
{
if( time_machine[i] > time_max_K )
time_max_K = time_machine[i];
}
if(time_max_K<time_min)
{
time_min = time_max_K;
for(int i=1;i<=N;i++)
Res[i] = x[i];
}
}
else
2、每搜索完一条路径则记录下time_min和Res[i]序列，开始结点就成为一个活结点，
同时也成为当前的扩展结点。在当前的扩展结点处向纵深方向移至一个新结点，
并成为一个新的活结点，也成为当前扩展结点。
3、如果在当前的扩展结点处不能再向纵深方向扩展，则当前扩展结点就成为死结点。
此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展
《算法设计与分析》上机报告
姓名：
学号：
日期：
上机题目：
最佳调度问题(回溯算法)
实验环境：
CPU: 2.10GHz ;内存: 6G ;操作系统：Win7 64位;软件平台：Visual Studio2008 ;
一、算法设计与分析：
题目:
最佳调度问题(回溯算法)
设有n个任务由m个可并行工作的机器来完成，完成任务i需要时间为ti。
system("pause");
return 0;
}
bool placetest(int k)
{
int time_max_K = time_machine[1];
for(int i=2;i<=K;i++)
{
if( time_machine[i] > time_max_K )
time_max_K = time_machine[i];
for(int i=1;i<N+1;i++)
{
cout << t[i] << ' ';
}
cout << endl;
clock_t start,finish;
double totaltime;
start=clock();
Backtrack(1,t,x);
finish=clock(); //1ms clock++
{
for(int i=1;i<=K;i++)
{
x[k] = i;//将第k个任务放到第i个机器上面
if( placetest(k) )
{
time_machine[i] += t[k];
Backtrack(k+1,t,x);
time_machine[i] -= t[k];
}
}
}
}
totaltime=(double)(finish-start)/CLOCKS_PER_SEC;
cout << "程序运行时间：" << totaltime << "s\n";
for(int i=1;i<N+1;i++)
cout << Res[i] << ' ';
cout << endl;
cout<< "min time:" << time_min <<endl;
int K,N;
int *time_machine;//[K+1]={0};
int *Res;//[N+1];
static int time_min = INT_MAX;
bool placetest(int k);
void Backtrack(int k,int t[],int x[]);
int main()
最佳调度问题(回溯算法)
设有n个任务由k个可并行工作的机器来完成，完成任务i需要时间为。
试设计一个算法找出完成这n个任务的最佳调度，使完成全部任务的时间最早。
*/
#include <iostream>
#include <ctime>
#include <windows.h>
using namespace std;
}
if(time_max_K > time_min)
returnfalse;
else
returntrue;
}
voidBacktrack(intk,intt[],intx[])
{
if(k > N )
{
inttime_max_K = time_machine[1];
for(inti=2;i<=K;i++)
试设计一个算法找出完成这个任务的最佳调度，使完成全部任务的时间最早。
算法思想：
解空间的表示：
一个深度为N的M叉树。
t[i]:第i个任务的时间
x[i]=j:当前输出结果
Res[i]=j:表示第i个任务要运行在第j台机器上
time_machine[i]:第i个机器上的运行时间
基本思路：
1、搜索从开始结点（根结点）出发，以DFS搜索整个解空间。
for(int i=1;i<N+1;i++)
cin >> 14,4,16,6,5,3};
time_machine = new int[K+1];
Res = new int[N+1];
for(int i=1;i<K+1;i++)
time_machine[i]=0;