awd.h

贪婪算法合集,包括二分覆盖,单源最短路径,拓扑排序,机器调度问题

//加权有向图的耗费邻接矩阵类， 邻接矩阵类的根是它，所以从它开始
//最终版本
#ifndef AdjacencyWDigraph_
#define AdjacencyWDigraph_

#include <cstdlib>
#include <iostream>
#include "fchain.h"
#include "network.h"
#include "citer.h"
#include "wnetwork.h"
#include "swap.h"
#include "make2db.h"//调用里面的函数为二维数组a分配空间
#include "del2d.h"//供类的析构函数 调用里面的函数进行释放
using namespace std;

template <class T> class AdjacencyWGraph;

template<class T>
class AdjacencyWDigraph : virtual public Network, virtual public WNetwork<T> {//最终版派生于两个更抽象的虚拟基类
   friend AdjacencyWGraph<T>;
   friend class AdjacencyGraph;
   public:
      AdjacencyWDigraph (int Vertices = 10, T noEdge = 0);//noEdge表示没有边，这里预设值为0
	  //以下8个操作是根据抽象数据描述所需要的基本操作
      ~AdjacencyWDigraph() {Delete2DArray(a,n+1);}
      bool Exist(int i, int j) const;
      int Edges() const {return e;}
      int Vertices() const {return n;}
      AdjacencyWDigraph<T>& Add(int i, int j, const T& w);
      AdjacencyWDigraph<T>& Delete(int i, int j);
      int OutDegree(int i) const;
      int InDegree(int i) const;

	  //以下函数是最终版为了适应各种需要增加的函数
      void ShortestPaths(int s, T d[], int p[]);//最短路径问题
      void AllPairs(T **c, int **kay);//所有点的最短路径--动态规划算法
      void Output() const;
	  void InitializePos() {pos = new int [n+1];}
      void DeactivatePos() {delete [] pos;}

      int Begin(int i);//Begin和NextVertex是图的遍历函数
      int NextVertex(int i);

      void First(int i, int& j, T& c);
      void Next(int i, int& j, T& c);
      T TSP(int v[]);//旅行商问题--使用回溯算法
      T BBTSP(int v[]);//旅行商问题--使用最小耗费分枝定界算法
   private:
      void tSP(int i);
      T NoEdge;  //用于没有边存在的情况
      int n;     //顶点数目
      int e;     //边数目
      T **a;     //邻接矩阵
      int *pos;  //遍历器用到的记录与顶点i邻接的某个顶点(包括begin,或者next)
      //静态成员 used by 回溯 and 分枝定界算法
      static int *x,     //存储到当前节点的路径
                 *bestx; //迄今为止最优解
      static T cc,       //保存当前节点的局部旅行的耗费
               bestc;    //保存目前最优解得的耗费
};

// 定义这些静态成员 for T = int and float（因为static变量要在外部定义声明）
// 在这里你可以增加你需要的类型。
int  *AdjacencyWDigraph<int>::x,
     *AdjacencyWDigraph<int>::bestx,
      AdjacencyWDigraph<int>::bestc,
      AdjacencyWDigraph<int>::cc;

int  *AdjacencyWDigraph<float>::x,
     *AdjacencyWDigraph<float>::bestx;
float AdjacencyWDigraph<float>::bestc,
      AdjacencyWDigraph<float>::cc;

template<class T>
AdjacencyWDigraph<T>::AdjacencyWDigraph(int Vertices, T noEdge)
{//构造函数
   n = Vertices;
   e = 0;
   NoEdge = noEdge;
   Make2DArray(a, n+1, n+1);
   //初始化为没有边的图
   for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
         a[i][j] = NoEdge;
}

template<class T>
bool AdjacencyWDigraph<T>::Exist(int i, int j) const
{//边(i,j)存在么？
   if (i < 1 || j < 1 || i > n || j > n
       || a[i][j] == NoEdge) return false;
   return true;
}

template<class T>
AdjacencyWDigraph<T>& AdjacencyWDigraph<T>::Add(int i, int j, const T& w)
{//如果边(i,j)不存在，则加入它到这个有向图中。
	if (i < 1 || j < 1 || i > n || j > n || i == j || a[i][j] != NoEdge)
		throw BadInput();
	a[i][j] = w;//权值赋给对应的邻接矩阵元
	e++;//边数+1
	return *this;
}

template<class T>
AdjacencyWDigraph<T>& AdjacencyWDigraph<T>::Delete(int i, int j)
{//删除边（i，j）
	if (i < 1 || j < 1 || i > n || j > n || a[i][j] == NoEdge)
		throw BadInput();
	a[i][j] = NoEdge;
	e--;
	return *this;
}

template<class T>
int AdjacencyWDigraph<T>::OutDegree(int i) const
{//返回顶点i的出度，对每列求和即可
	if (i < 1 || i > n) throw BadInput();
	// count out edges from vertex i
	int sum = 0;
	for (int j = 1; j <= n; j++)
		if (a[i][j] != NoEdge) sum++;
	return sum;
}

template<class T>
int AdjacencyWDigraph<T>::InDegree(int i) const
{//返回顶点的入度，对每行求和
	if (i < 1 || i > n) throw BadInput();
	// count in edges at vertex i
	int sum = 0;
	for (int j = 1; j <= n; j++)
		if (a[j][i] != NoEdge) sum++;
	return sum;
}

template <class T>
void AdjacencyWDigraph<T>::Output() const
{//输出邻接矩阵
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
			cout << a[i][j] << " ";
		cout << endl;
	}
}

template<class T>
int AdjacencyWDigraph<T>::Begin(int i)
{//返回第一个与顶点i邻接的顶点
	
	if (i < 1 || i > n) throw OutOfBounds();
	// 查找第一个邻接顶点
	for (int j = 1; j <= n; j++)
		if (a[i][j] != NoEdge)
		{//j是第一个，赋给pos[i]
			pos[i] = j;
			return j;
		}
	pos[i] = n + 1; //否则，没有邻接顶点，n+1赋给pos[i]
	return 0;//返回0
}

template<class T>
int AdjacencyWDigraph<T>::NextVertex(int i)
{//返回下一个与顶点邻接的顶点
	if (i < 1 || i > n) throw OutOfBounds();
	//查找下一个邻接顶点
	for (int j = pos[i] + 1; j <= n; j++)
		if (a[i][j] != NoEdge)
		{//j是下一个顶点，j的值就赋给pos[i]
			pos[i] = j; return j;
		}
		
	pos[i] = n + 1; // 没有下一个顶点与之邻接
	return 0;
}

template<class T>
void AdjacencyWDigraph<T>::First(int i, int& j, T& c)
{// 返回第一个顶点j 以及(i,j)的权值
	
	if (i < 1 || i > n) throw OutOfBounds();
	//寻找第一个邻接的顶点
	for (j = 1; j <= n; j++)
		if (a[i][j] != NoEdge)
		{//j是第一个
			pos[i] = j;
			c = a[i][j];
			return;
		}
	
	pos[i] = n + 1; //没有邻接的顶点
	j = 0;
}

template<class T>
void AdjacencyWDigraph<T>::Next(int i, int& j, T& c)
{//返回下一个顶点j 以及(i,j)的权值
	if (i < 1 || i > n) throw OutOfBounds();
	
	//寻找下一个邻接的顶点
	for (j = pos[i] + 1; j <= n; j++)
		if (a[i][j] != NoEdge)
		{// j is next vertex
			pos[i] = j;
			c = a[i][j];
			return;
		}
		
	pos[i] = n + 1; // no next vertex
	j = 0;
}

template<class T>
void AdjacencyWDigraph<T>::ShortestPaths(int s, T d[], int p[])
{//寻找从顶点s出发到达图中其他任意目的顶点的最短路径的最短路径，在d中返回最短路径长度，p中返回前继顶点
	if (s < 1 || s > n) throw OutOfBounds();
	Chain<int> L; //使用链表来维护路径可以到达的顶点列表
	ChainIterator<int> I;
	//初始化 d, p, and L
	for (int i = 1; i <= n; i++)
	{
		d[i] = a[s][i];
		if (d[i] == NoEdge) p[i] = 0;
		else {p[i] = s; L.Insert(0,i);}
	}
	
	//更新d和p
	while (!L.IsEmpty())//循环一直到L为空，空了之后，就找完了
	{// more paths exist
		//寻找具有最小d的顶点v
		int *v = I.Initialize(L);
		int *w = I.Next();
		while (w)
		{
			if (d[*w] < d[*v]) v = w;
			w = I.Next();
		}
		
		//从L中删除通向顶点v的下一最短路径并更新d
		int i = *v;
		L.Delete(*v);
		for (int j = 1; j <= n; j++)
		{
			if (a[i][j] != NoEdge && (!p[j] || d[j] > d[i] + a[i][j]))
			{
				//减少d[j]
				d[j] = d[i] + a[i][j];
				// !p[j]为真的话，就表明j不在L中，加入到L,同时置p[j]=i
				if (!p[j]) L.Insert(0,j);
				p[j] = i;
			}
		}
	}
}
    
template<class T>
void AdjacencyWDigraph<T>::AllPairs(T **c, int **kay)
{//所有点的最短路径
 // 对于所有i,j计算c[i][j],和kay[i][j]
	//初始化c[i][j]=c(i,j,0)
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
		{
			c[i][j] = a[i][j];
			kay[i][j] = 0;
		}
	//i=j情况下，c[i][j]=0
	for (i = 1; i <= n; i++)
		c[i][i] = 0;
	
	//计算c[i][j] = c(i,j,k)
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
			{
				T t1 = c[i][k];
				T t2 = c[k][j];
				T t3 = c[i][j];//t3临时存储当前c[i][j]值
				if (t1 != NoEdge && t2 != NoEdge && (t3 == NoEdge || t1 + t2 < t3))
				//如果t1,t2都不为Noedge，也即t1,t2对应的边存在,且t3或者t1+t2比t3小，则将t1+t2赋给c[i][j]
				{
					c[i][j] = t1 + t2;
					kay[i][j] = k;//记录k值
				}
			}
}

/*旅行商问题：n顶点网络（有向或无向），要求找出一个包含所有n个顶点的具有最小耗费的环路。
回溯算法思想：当i=n时，处在排列树的叶节点的父节点上，并且要验证从x[n-1]到x[n]有一条边，
从x[n]到x[1]有一条边.当i<n时，检查当前i-1层节点的孩子节点，并且当且仅当以下情况出现时，
移动到孩子节点之一：有从x[i-1]到x[i]的一条边，路径x[1:i]耗费小于当前最优解的耗费.*/

template<class T>
void AdjacencyWDigraph<T>::tSP(int i)
{//旅行商问题的回溯算法
	if (i == n)
	{//在叶子的父节点
		//通过增加两条边来完成旅行
		if (a[x[n-1]][x[n]] != NoEdge && a[x[n]][1] != NoEdge && (cc + a[x[n-1]][x[n]] + a[x[n]][1] < bestc || bestc == NoEdge))
		{//找到更优的路径
			for (int j = 1; j <= n; j++)
				bestx[j] = x[j];
			bestc = cc + a[x[n-1]][x[n]] + a[x[n]][1];
		}
	}
	else
	{//尝试子树
		for (int j = i; j <= n; j++)//能移动到子树x[j]么？
			if (a[x[i-1]][x[j]] != NoEdge && (cc + a[x[i-1]][x[i]] < bestc || bestc == NoEdge))
			{//可以
				//搜索该子树，通过tSP(i+1)前后两句，回溯
				Swap(x[i], x[j]);
				cc += a[x[i-1]][x[i]];
				tSP(i+1);
				cc -= a[x[i-1]][x[i]];
				Swap(x[i], x[j]);
			}
	}
}

template<class T>
T AdjacencyWDigraph<T>::TSP(int v[])
{//用回溯算法解决旅行商问题，返回最优路径的耗费，最优路径存入v[1:n]中;该函数为实质的解决问题函数
 //tSP进行初始化	
	x = new int [n+1];
	// x is identity 排列
	for (int i = 1; i <= n; i++)
		x[i] = i;
	bestc = NoEdge;
	bestx = v;  // 使用数组v存储最优旅行
	cc = 0;
	
	//搜索 x[2:n] 的排列
	tSP(2);
	
	delete [] x;
	return bestc;
}

#include "minheap.h"
template<class T>
class MinHeapNode {
   friend AdjacencyWDigraph<T>;
   public:
      operator T () const {return lcost;}
   private:
      T lcost,  // lower bound on cost of tours in subtree
        cc,     // cost of partial tour
        rcost;  // min additional cost to complete tour
      int s,    // partial tour is x[0:s]
          *x;   // vertex array, x[s+1:n-1] gives remaining
                // vertices to be added to partial tour x[0:s]
};

/*程序首先生成一个容量为1000的最小堆，用来表示活节点的最小优先队列，活结点按其lcost值从最小堆中取出，接下来
计算有向图中从每个顶点出发的边中耗费最小的边所具有的耗费MinOut（可见这是一个耗费量的数组）。如果某些顶点没
有出边，则证明无法完成旅行，搜索终止，否则可以启动最小耗费分枝定界搜索。根的孩子作为第一个E-节点，在此节点
上，所生成的旅行路径前缀只有一个顶点1，因此s=0,x[0]=1,x[1:n-1]是剩余的顶点（顶点2，3，...，n）旅行路径前缀
1的开销为0（因为实际上此时旅行才开始，没有走任何路），即cc=0，并且rcost=MinOut[i]求和。在程序中bestc给出了
当前能找到的最少耗费值，初始时由于没有找到任何旅行路径，因此bestc的值被设为NoEdge。*/

template<class T>
T AdjacencyWDigraph<T>::BBTSP(int v[])
{//旅行商最小耗费分枝定界算法程序
 //定义一个最多可容纳1000个活节点的最小堆
	MinHeap<MinHeapNode<T> > H(1000);
	
	T *MinOut = new T [n+1];
	// 计算 MinOut[i] = 离开顶点i的最小耗费边的耗费
	T MinSum = 0;  // 离开顶点i的最小耗费边的数目
	for (int i = 1; i <= n; i++)
	{
		T Min = NoEdge;
		for (int j = 1; j <= n; j++)
			if (a[i][j] != NoEdge && (a[i][j] < Min || Min == NoEdge))
				Min = a[i][j];
		if (Min == NoEdge) return NoEdge; //如果Min=NoEdge不会存在旅行路径
		MinOut[i] = Min;
		MinSum += Min;
	}
	
	//把E-节点初始化为树根
	MinHeapNode<T> E;
	E.x = new int [n];
	for (i = 0; i < n; i++)
		E.x[i] = i + 1;
	E.s = 0;           // 局部旅行路径为x[1:0]
	E.cc = 0;          // 其耗费为0
	E.rcost = MinSum;  // will go up by this or more
	T bestc = NoEdge;  // 目前还没找到旅行路径
	
	//搜索排列树
	while (E.s < n - 1)
	{//不是叶子
		if (E.s == n - 2)
		{//叶子的父节点
			//通过添加两条边来完成旅行，检查新的路径是不是更好
			if (a[E.x[n-2]][E.x[n-1]] != NoEdge && a[E.x[n-1]][1] != NoEdge &&
				(E.cc + a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][1] < bestc || bestc == NoEdge))
			{// 找到更优
				bestc = E.cc + a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][1];
				E.cc = bestc;
				E.lcost = bestc;
				E.s++;
				H.Insert(E);
			}
			else delete [] E.x;}  //对本节点的处理结束
		else
		{//产生孩子
			for (int i = E.s + 1; i < n; i++)
				if (a[E.x[E.s]][E.x[i]] != NoEdge)
				{//可行的孩子，限定了路径的耗费
					T cc = E.cc + a[E.x[E.s]][E.x[i]];
					T rcost = E.rcost - MinOut[E.x[E.s]];
					T b = cc + rcost;  //下限
					if (b < bestc || bestc == NoEdge)
					{//子树可能有更好的叶子，把根保存到最小堆中
						MinHeapNode<T> N;
						N.x = new int [n];
						for (int j = 0; j < n; j++)
							N.x[j] = E.x[j];
						N.x[E.s+1] = E.x[i];
						N.x[i] = E.x[E.s+1];
						N.cc = cc;
						N.s = E.s + 1;
						N.lcost = b;
						N.rcost = rcost;
						H.Insert(N);
					}
				}  //结束可行的孩子
				delete [] E.x;
		}  //对本节点的处理结束
		
		try {H.DeleteMin(E);}        //获取下一个E-节点
		catch (OutOfBounds) {break;} //没有处理的节点
	}

	if (bestc == NoEdge) return NoEdge; //没有路径
	//将最优路径复制到v[1:n]
	for (i = 0; i < n; i++)
		v[i+1] = E.x[i];

	while (true)
	{//释放最小堆中的所有节点
		delete [] E.x;
		try {H.DeleteMin(E);}
		catch (OutOfBounds) {break;}
	}
	
	return bestc;
}

#endif