图的应用:相对最后期限限制下的并行任务调度-- C++实现


一般的最后期限都是相对于第一个任务的开始时间而言的,假设在任务调度问题中加入一种新类型的限制,需要某个任务必须在指定的

时间点之前开始,即指定和另外一个任务的开始时间的相对时间

在优先级限制的前提下,如果任务v必须在任务w启动后的d个时间单位内开始,则添加一条从v到w的负权重为d的边,然后将所有边的权

重取反,这样就把问题转化为一个有环有负权重的求最短路径问题,可以使用BellmanFord算法解决。

思路:其实所有边的权值取反,然后算最短路径 和 原来的权值算最长路径得出来的是一样的结果 要这样处理只是因为关键路径基于

AcyclicLongnestPath算法,而这个算法用到了拓扑排序,肯定无法处理带环的图。采取环值取反这样处理以后就可以使用

BellmanFord算法来求最短路径,也可以得到一样的结果)

测试代码

//main.cpp

#include <time.h>
#include<windows.h>


#include "Component.h"
#include "EdgesWeightDirectionGraph.h"


using namespace jay;


int main(int argc, char* argv[])
{
	// 
	EdgesWeightDirectionGraph<double,int> gra(30);

	int iCount;// 顶点的个数(任务编号由 0 至 iCount-1 共iCount个)

	cin>>iCount;

	int iBegin = 2 * iCount ;    // 起点(额外添加)
	int iEnd   = 2 * iCount + 1; // 终点(额外添加)

	for (int i=0;i<10;i++)
	{
		int iCurentTask; // 当前顶点(任务编号/任务的起始顶点)
		cin>>iCurentTask;

		double weight;
		cin>>weight; // 权重

		// 权值取反
		double tmp = -weight;
		// 任务的边
		gra.AddEdge(iBegin,iCurentTask,0.0); // 起点到当前任务的起始顶点
		gra.AddEdge(iCurentTask,iCurentTask + iCount,tmp); // 当前任务的起始顶点到当前任务的结束顶点
		gra.AddEdge(iCurentTask + iCount,iEnd,0.0); // 当前任务的结束顶点到终点

		// 优先级的边
		int iAfterCount;// 需当前任务完成才能开始的任务个数
		cin>>iAfterCount;
		for (int j=0;j<iAfterCount;j++)
		{
			int iAferTask;
			cin>>iAferTask;

			gra.AddEdge(iCurentTask + iCount,iAferTask,0.0); // 当前任务的结束顶点到后续任务的起始顶点

		}
	}

	// 2号任务必须在4号任务启动后的12个时间单位之内开始
//	gra.AddEdge(2,4,12.0);

	// 2号任务必须在7号任务启动后的70个时间单位之内开始
	gra.AddEdge(2,7,70.0);

	// 4号任务必须在0号任务启动后的80个时间单位之内开始
//	gra.AddEdge(4,0,60.0);

	gra.Show();

	gra.BellmanFordShortestPath(iBegin);

	gra.pathTo(1);

	gra.pathTo(5);

	gra.pathTo(8); 
	gra.pathTo(2);
	cout << "全部任务输出:" <<endl;
	cout.flags(ios::right);
	cout <<  setw(10)<< "任务编号"  <<  setw(10)<< "开始时间"  <<  setw(10)<< "结束时间" << endl;
	for (int i=0;i<iCount;i++)
	{
		cout <<  setw(10)<< i  <<  setw(10)<< abs(gra.distTo(i))  <<  setw(10)<< abs(gra.distTo(i+iCount)) << endl;
	}

	cout << "总用时:" <<abs(gra.distTo(iEnd)) <<endl;


}

 

 

暂无评论

注册用户登录后才能发表或者回复评论,请先登录 注册。