例题四单源最短路径问题分支限界算法的数据结构 #include #include #include using namespace std; class Graphic{ int n;//图中顶点的个数 int e;//边的数目 int **adjmatrix;//邻接矩阵，存储图 int *dist;//dist[n],存储单元点到其他n-1个顶点的最短路的长度 int prev;//prev[i]=j 存储顶点i 的前驱结点为j , 利用这些前驱结点可以找到源点到顶点i的最短路 int start;//源点 public: Graphic(int n, int e); void ShortPath(); void display(); }; class PathNode{ //放入优先队列中的节点,解空间中的结点 int i; //解空间中结点的编号。一个结点对应于一条路 int length;//路的长度。 friend class Graphic; public: PathNode(int a=0, int b=0):i(a),length(b){} bool operator <(PathNode b) const {//定义优先关系函数 return length>b.length; } }; Graphic::Graphic(int n, int e){ this->n=n; this->e=e; adjmatrix=new int[n+1]; dist=new int[n+1]; prev=new int[n+1]; for(int i=1;i<=n;i++) adjmatrix[i]=new int[n+1]; cout<<“输入源点编号：”; cin>>start; cout<<“请输入e条边”<<endl; for(i=1;i<=n;i++){ //邻接矩阵初始化 for(int j=1;j<=n;j++) adjmatrix[i][j]=-1; //两个顶点之间没有边 adjmatrix[i][i]=0; } for( i=0;i<e;i++) { int a, b,length; cin>>a>>b>>length; //输入一条边所依附的两个顶点和这条边的长度 adjmatrix[a][b]=length; //有向图 dist[i]=99999; //最短路赋初值 prev[i]=start; } };
例题六装载问题 #define NUM 100 int n; //集装箱的数量 int c; //轮船的载重量 int w[NUM]; //集装箱的重量数组 int MaxLoading(){ queue Q; Q.push(-1); int i = 0; //层号 int Ew = 0; //当前的装载重量 int bestw = 0;//最优装载重量 int r = 0; //剩余货物的总重量 for(int j=1; j<n; j++) r += w[j]; while (true) {//搜索子空间树 //检查左子树 int wt = Ew+w[i]; if (wt<=c){ //检查约束条件 if (wt>bestw) bestw = wt; if (i<n-1) Q.push(wt); //加入活结点队列 } if (Ew+r>bestw && i<n-1) //检查右子树， 检查上界条件 Q.push(Ew); Ew = Q.front(); //从队列中取出活结点 Q.pop(); if (Ew==-1) { //判断同层的尾部 if (Q.empty()) return bestw; Q.push(-1); //同层结点尾部标志 Ew = Q.front(); //从队列中取出活结点 Q.pop(); i++; r -= w[i]; } } return bestw; }
例题七 0－1背包问题 优先队列元素的类 #define NUM 100 class object { friend int knapsack(int *,int *,int ,int); public: //排序运算符重载 int operator < (object a)const { return (ratio>a.ratio); } private: int ID; //物品编号 double ratio; //单位重量价值 }; class queueNode{ //优先队列中的结点 friend class knap; public: //优先队列以uprofit为优先级参数 friend bool operator < (queueNode a,queueNode b) { if(a.uprofit<b.uprofit) return true; else return false; } private: int uprofit; //结点的价值上界 int profit; //结点相应的价值 int weight; //结点相应的重量 int level; //活结点在子集树中所处的层序号 node *ptr; //指向活结点在子集树中相应结点的指针 }; 解空间树的类 class knap{ friend int knapsack (int *,int *,int ,int); public: int maxKnapsack(); private: priority_queue H; //创建优先队列 int bound(int i); //计算未装入背包中的剩余物品的价值上界函数 void addLiveNode (int up,int cp,int cw,bool ch,int level); //增加活结点到子集树中，并将其插入优先队列 node *E; //指向子集树中的正在扩展的结点的指针 int c; //背包容量 int n; //物品总数 int w[NUM]; //物品重量数组 int p[NUM]; //物品价值数组 int cw; //当前装包重量 int cp; //当前装包价值 int bestx[NUM]; //最优解
例题八旅行商问题 #include #include using namespace std;
class Traveling{ int n;//图中顶点的个数 int e;//边的数目 int **a;//邻接矩阵（无向图的邻接矩阵） int cc;//当前路径（子路径，非完整路径）的长度 int bestc;//当前最小费用 int NoEdge; public: int BBTSP(); Traveling(); }; struct node{ //优先队列以lcost为优先级参数 friend bool operator < (const node& a,const node& b){ if(a.lcost > b.lcost) return true; else return false; } int lcost; //子树费用的下界 int rcost; //从x[s]～x[n-1]顶点的最小出边和 int cc; //当前费用。截止到当前城市的路径长度 int s; //当前结点的编号。结点的层次编号。已经经过的城市的数目 int *x; //需进一步搜索的路径x[s+1:n]。全排列 }; priority_queue H; int minOut[NUM]; //各个顶点的最小出边费用 int minSum = 0; //最小出边费用之和 //计算各个顶点的最小出边费用 int i, j; for(i=1; i<=n; i++) { int Min = NoEdge; for(j=1; j<=n; j++) if( a[i][j]!=NoEdge && (a[i][j]<Min || MinNoEdge)) Min = a[i][j]; if (MinNoEdge) return NoEdge; //无回路 minOut[i] = Min; minSum += Min; } while (E.s<n) { //非叶结点 if (E.sn-1) { //当前扩展结点是叶结点的父结点 //再加2条边构成回路 //所构成的回路是否优于当前最优解 if (a[E.x[n-1]][E.x[n]]!=NoEdge && a[E.x[n]][1]!=NoEdge && (E.cc+a[E.x[n-1]][E.x[n]]+a[E.x[n]][1]<bestc || bestcNoEdge)) { //费用更小的回路 bestc = E.cc+a[E.x[n-1]][E.x[n]]+a[E.x[n]][1]; E.cc = bestc; E.lcost = bestc; else delete[ ] E.x; //舍弃扩展结点 }
