分支界限法.

武汉理工大学

算法设计与分析论文

题 目：

分支限界法应用研究

目 录

摘 要 . ...................................................... 1 1. 绪 论 . .................................................... 2 2分支限界法的内容 ........................................... 3 2.1 分支限界法基本思想 .................................... 3 2.2 两种分支限界法 ........................................ 3 2.3 分支限界法的设计思路 .................................. 4 2.4分支限界法与回溯法区别 ............... 错误！未定义书签。 3 分支限界法应用 . ............................................ 5 3.1批处理作业问题 ........................................ 5 3.2 旅行售货员问题 ........................................ 6 3.3单源最短路径问题 ..................................... 12 3.4 01背包问题 .......................................... 12 4. 总结 . ..................................................... 24 5. 参考文献 . ................................................. 25

摘 要

分支限界法常以广度优先或以最小耗费优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

本文讲述了分支限界法的含义、基本思路及实现过程，分支限界法的核心、基本性质、特点及其存在的问题。并通过分支限界法的特点，举例列出了以往研究过的几个经典问题，对于实际应用中的问题，也希望通过分支限界法的特点来解决。

关键词：分支限界法；解空间树；最优解；

1. 绪 论

为了解决各种实际问题，计算机算法学得到了飞速的发展，线性规划、动态规划、分支限界法等一系列运筹学模型纷纷运用到计算机算法学中，产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更像是一门艺术而不像是技术 ,但仍然存在一些行之有效的、能够用于解决许多问题的算法设计方法 ,你可以使用这些方法来设计算法 ,并观察这些算法是如何工作的。一般情况下, 为了获得较好的性能, 必须对算法进行细致的调整。但是在某些情况下, 算法经过调整之后性能仍无法达到要求, 这时就必须寻求另外的方法来求解该问题。分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

2分支限界法的内容

2.1 分支限界法基本思想

分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。

此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

2.2 两种分支限界法

（1）队列式(FIFO)分支限界法

按照队列先进先出（FIFO ）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法

按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点

2.3分支限界法的设计思路

设求解最大化问题，解向量为X=(x1,…,xn) ，xi 的取值范围为Si ，|Si|=ri。在使用分支限界搜索问题的解空间树时，先根据限界函数估算目标函数的界[down, up]，然后从根结点出发，扩展根结点的r1个孩子结点，从而构成分量x1的r1种可能的取值方式。对这r1个孩子结点分别估算可能的目标函数bound(x1)，其含义：以该结点为根的子树所有可能的取值不大于bound(x1)，即： bound(x1)≥bound(x1,x2)≥…≥ bound(x1,…,xn)

若某孩子结点的目标函数值超出目标函数的下界，则将该孩子结点丢弃；否则，将该孩子结点保存在待处理结点表PT 中。再取PT 表中目标函数极大值结点作为扩展的根结点，重复上述。直到一个叶子结点时的可行解X=(x1,…,xn) ，及目标函数值bound(x1,…,xn) 。

2.4分支限界法与回溯法区别

（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。

（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

3分支限界法应用

3.1批处理作业问题

（1）问题提出。

给定n 个作业的集合J={J1,J2,…,Jn}。每一个作业Ji 都有2项任务要分别在2台机器上完成。每一个作业必须先由机器1处理，然后再由机器2处理。作业Ji 需要机器j 的处理时间为tji ，i=1,2,…,n ；j=1,2。对于一个确定的作业调度，设是Fji 是作业i 在机器j 上完成处理的时间。则所有作业在机器2上完成处理的时间和

f = 批处理作业调度问题要求对于给定的∑F 2i 称为该作业调度的完成时间和。

i =1n

n 个作业，制定最佳作业调度方案，使其完成时间和达到最小。 （2）算法分析。

在结点E 处相应子树中叶结点完成时间和的下界是：

f ≥∑F 2i +max{S 1, S 2}

i ∈M

注意到如果选择Pk ，使t1pk 在k>=r+1时依非减序排列，S1则取得极小值。同理如果选择Pk 使t2pk 依非减序排列，则S2取得极小值。

f ≥

i ∈M

∑F

2i

ˆ, S ˆ}+max{S 12

这可以作为优先队列式分支限界法中的限界函数。 （3）主要算法介绍。 do {

if (enode.s == n ) { if (enode.sf2

for (int i = 0; i

for (int i = enode.s; i

MyMath.swap(enode.x, enode.s,i); int [] f= new int [3]; int bb=bound(enode,f); if (bb

HeapNode node=new HeapNode(enode,f,bb,n); heap.put(node); } MyMath.swap(enode.x, enode.s,i); }

算法的while 循环完成对排列树内部结点的有序扩展。在while 循环体内算法依次从活结点优先队列中取出具有最小bb 值（完成时间和下界）的结点作为当前扩展结点，并加以扩展。首先考虑enode.s=n的情形，当前扩展结点enode 是排列树中的叶结点。enode.sf2是相应于该叶结点的完成时间和。当enode.sf2

3.2 旅行售货员问题

（1）问题提出。

某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费) 。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费) 最小。

（2）算法分析。

旅行商问题的解空间是一个排列树。

有两种实现的方法：第一种是只使用一个优先队列，队列中的每个元素 中都包含到达根的路径。另一种是保留一个部分解空间树和一个优先队列，优先队列中 的元素并不包含到达根的路径。

以下为第一种方法， 由于我们要寻找的是最小耗费的旅行路径，因此可以使用最小耗费分枝定界法。在实现过程中，使用一个最小优先队列来记录活节点，队列中每个节点的类型为MinHeapNode 。每个节点包括如下区域： x（从1到n 的整数排列，

其中x[0] = 1 ），s （一个整数，使得从排列树的根节点到当前节点的路径定义了旅行路径的前缀x[0:s], 而剩余待访问的节点是x [s + 1 : n - 1 ]），cc （旅行路径前缀，即解空间树中从根节点到当前节点的耗费），lcost （该节点子树中任意叶节点中的最小耗费）， rcost（从顶点x[s : n - 1]出发的所有边的最小耗费之和）。当类型为MinHeapNode( T )的数据被转换成为类型T 时，其结果即为lcost 的值。 程序代码：

#include #include using namespace std;

//---------------------宏定义------------------------------------------ #define MAX_CITY_NUMBER 10 //城市最大数目

#define MAX_COST 10000000 //两个城市之间费用的最大值

//---------------------全局变量---------------------------------------- int City_Graph[MAX_CITY_NUMBER][MAX_CITY_NUMBER]; //表示城市间边权重的数组 int City_Size; //表示实际输入的城市数目 int Best_Cost; //最小费用 int Best_Cost_Path[MAX_CITY_NUMBER];

//最小费用时的路径

//------------------------定义结点--------------------------------------- typedef struct Node{

int lcost; //优先级 int cc; //当前费用

int rcost; //剩余所有结点的最小出边费用的和 int s; //当前结点的深度，也就是它在解数组中的索引位置 int x[MAX_CITY_NUMBER]; //当前结点对应的路径 struct Node* pNext; //指向下一个结点 }Node;

//---------------------定义堆和相关对操作-------------------------------- typedef struct MiniHeap{

Node* pHead; //堆的头 }MiniHeap; //初始化

void InitMiniHeap(MiniHeap* pMiniHeap){ pMiniHeap->pHead = new Node; pMiniHeap->pHead->pNext = NULL; }

//入堆

void put(MiniHeap* pMiniHeap,Node node){ Node* next;

Node* pre;

Node* pinnode = new Node; //将传进来的结点信息copy 一份保存 //这样在函数外部对node 的修改就不会影响到堆了

pinnode->cc = node.cc;

pinnode->lcost = node.lcost; pinnode->pNext = node.pNext; pinnode->rcost = node.rcost; pinnode->s = node.s; pinnode->pNext = NULL;

for(int k=0;kx[k] = node.x[k]; }

pre = pMiniHeap->pHead;

next = pMiniHeap->pHead->pNext; if(next == NULL){

pMiniHeap->pHead->pNext = pinnode; } else{

while(next != NULL){

if((next->lcost) > (pinnode->lcost)){ //发现一个优先级大的，则置于其前面

pinnode->pNext = pre->pNext; pre->pNext = pinnode;

break; //跳出 }

pre = next;

next = next->pNext; }

pre->pNext = pinnode; //放在末尾 } }

//出堆

Node* RemoveMiniHeap(MiniHeap* pMiniHeap){ Node* pnode = NULL;

if(pMiniHeap->pHead->pNext != NULL){ pnode = pMiniHeap->pHead->pNext;

pMiniHeap->pHead->pNext = pMiniHeap->pHead->pNext->pNext; }

return pnode; }

//---------------------分支限界法找最优解-------------------------------- void Traveler(){ int i,j;

int temp_x[MAX_CITY_NUMBER];

Node* pNode = NULL;

int miniSum; //所有结点最小出边的费用和

int miniOut[MAX_CITY_NUMBER];

//保存每个结点的最小出边的索引

MiniHeap* heap = new MiniHeap; //分配堆

InitMiniHeap(heap); //初始化堆

miniSum = 0;

for (i=0;i

miniOut[i] = MAX_COST; //初始化时每一个结点都不可达

for(j=0;j

if (City_Graph[i][j]>0 && City_Graph[i][j]

//从i 到j 可达，且更小

miniOut[i] = City_Graph[i][j];

}

}

if (miniOut[i] == MAX_COST){// i 城市没有出边

Best_Cost = -1;

return ;

}

miniSum += miniOut[i];

}

for(i=0;i

走一遍

Best_Cost_Path[i] = i;

}

Best_Cost = MAX_COST; //初始化的最优费用是一个很大的数

pNode = new Node; //初始化第一个结点并入堆

pNode->lcost = 0; //当前结点的优先权为0 也就是最优

pNode->cc = 0; //当前费用为0（还没有开始旅行）

pNode->rcost = miniSum; //剩余所有结点的最小出边费用和就是初始

化的miniSum

pNode->s = 0; //层次为0

pNode->pNext = NULL;

for(int k=0;k

pNode->x[k] = Best_Cost_Path[k]; //第一个结点所保存的路径也就

是初始化的路径

}

put(heap,*pNode); //入堆

while(pNode != NULL && (pNode->s)

//堆不空 不是叶子

for(int k=0;k

Best_Cost_Path[k] = pNode->x[k] ; //将最优路径置换为当前结点本身所保存的

}

/*

* * pNode 结点保存的路径中的含有这条路径上所有结点的索引

* * x路径中保存的这一层结点的编号就是x[City_Size-2]

* * 下一层结点的编号就是x[City_Size-1] */

if ((pNode->s) == City_Size-2){ //是叶子的父亲

Int edge1 = City_Graph[(pNode->x)[City_Size-2]][(pNode->x)[City_Size-1]];

int edge2 = City_Graph[(pNode->x)[City_Size-1]][(pNode->x)[0]];

if(edge1 >= 0 && edge2 >= 0 && (pNode->cc+edge1+edge2) cc + edge1+edge2;

pNode->cc = Best_Cost;

pNode->lcost = Best_Cost; //优先权为 Best_Cost

pNode->s++; //到达叶子层

}

}

else{ //内部结点

for (i=pNode->s;i

if(City_Graph[pNode->x[pNode->s]][pNode->x[i]] >= 0){

//pNode的层数就是它在最优路径中的位置

Int temp_cc =

pNode->cc+City_Graph[pNode->x[pNode->s]][pNode->x[i]];

int temp_rcost = pNode->rcost-miniOut[pNode->x[pNode->s]];

//下一个结点的剩余最小出边费用和

//等于当前结点的rcost 减去当前这个结点的最小出边费用

if (temp_cc+temp_rcost

//下一个结点的最小出边费用和小于当前的最优解，说明可能存在更优解

for(j=0;j

temp_x[j]=Best_Cost_Path[j];

}

temp_x[pNode->x[pNode->s+1]] = Best_Cost_Path[i];

//将当前结点的编号放入路径的深度为s+1的地方

temp_x[i] = Best_Cost_Path[pNode->s+1];

Node* pNextNode = new Node;

pNextNode->cc = temp_cc;

pNextNode->lcost = temp_cc+temp_rcost;

pNextNode->rcost = temp_rcost;

pNextNode->s = pNode->s+1;

pNextNode->pNext = NULL;

for(int k=0;k

pNextNode->x[k] = temp_x[k];

}

put(heap,*pNextNode);

delete pNextNode;

}

}

}

}

pNode = RemoveMiniHeap(heap);

}

}

int main(){

int i,j;

printf("请输入旅行的节点数");

scanf("%d",&City_Size);

for(i=0;i

printf("请分别输入每个节点与其它节点的路程花费");

for(j=0;j

scanf("%d",&City_Graph[i][j]);

}

}

Traveler();

printf("最小花费""%d\n",Best_Cost);

return 1;

}

实验结果如图：

由于我们要寻找的是最小耗费的旅行路径，因此可以使用最小耗费分枝限界法。在实现过程中，使用一个最小优先队列来记录活节点，队列中每个节点的类型为MinHeapNode 。每个节点包括如下区域： x（从1到n 的整数排列，其中x[0] = 1 ），s （一个整数，使得从排列树的根节点到当前节点的路径定义了旅行路径的前缀x[0:s], 而剩余待访问的节点是x [s + 1 : n - 1 ]），cc （旅行路径前缀，即解空间树中从根节点到当前节点的耗费），lcost （该节点子树中任意叶节点中的最小耗费）， rcost（从顶点x[s : n - 1]出发的所有边的最小耗费之和）。当类型为MinHeapNode( T )的数据被转换成为类型T 时，其结果即为lcost 的值。

3.3单源最短路径问题

（1）问题提出。

下面以一个例子来说明单源最短路径问题：在下图所给的有向图G 中，每一边都有一个非负边权。要求图3-1从源顶点s 到目标顶点t 之间的最短路径。

图3-1 有向图G

（2）算法分析。

下图3-2是用优先队列式分支限界法解有向图G 的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。

图3-2 解空间树

程序代码：

#include

#include

#include

#include

using namespace std;

struct node_info

{

public:

node_info (int i,int w)

: index (i), weight (w) {}

node_info ()

: index(0),weight(0) {}

node_info (const node_info & ni)

: index (ni.index), weight (ni.weight) {}

friend

bool operator rth.weight ; // 为了实现从小到大的顺序 }

public:

int index; // 结点位置

int weight; // 权值

};

struct path_info

{

public:

path_info ()

: front_index(0), weight (numeric_limits::max()) {} public:

int front_index;

int weight;

};

class ss_shortest_paths

武汉理工大学

算法设计与分析论文

题 目：

分支限界法应用研究

目 录

摘 要 . ...................................................... 1 1. 绪 论 . .................................................... 2 2分支限界法的内容 ........................................... 3 2.1 分支限界法基本思想 .................................... 3 2.2 两种分支限界法 ........................................ 3 2.3 分支限界法的设计思路 .................................. 4 2.4分支限界法与回溯法区别 ............... 错误！未定义书签。 3 分支限界法应用 . ............................................ 5 3.1批处理作业问题 ........................................ 5 3.2 旅行售货员问题 ........................................ 6 3.3单源最短路径问题 ..................................... 12 3.4 01背包问题 .......................................... 12 4. 总结 . ..................................................... 24 5. 参考文献 . ................................................. 25

摘 要

分支限界法常以广度优先或以最小耗费优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

本文讲述了分支限界法的含义、基本思路及实现过程，分支限界法的核心、基本性质、特点及其存在的问题。并通过分支限界法的特点，举例列出了以往研究过的几个经典问题，对于实际应用中的问题，也希望通过分支限界法的特点来解决。

关键词：分支限界法；解空间树；最优解；

1. 绪 论

为了解决各种实际问题，计算机算法学得到了飞速的发展，线性规划、动态规划、分支限界法等一系列运筹学模型纷纷运用到计算机算法学中，产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更像是一门艺术而不像是技术 ,但仍然存在一些行之有效的、能够用于解决许多问题的算法设计方法 ,你可以使用这些方法来设计算法 ,并观察这些算法是如何工作的。一般情况下, 为了获得较好的性能, 必须对算法进行细致的调整。但是在某些情况下, 算法经过调整之后性能仍无法达到要求, 这时就必须寻求另外的方法来求解该问题。分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

2分支限界法的内容

2.1 分支限界法基本思想

分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。

此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

2.2 两种分支限界法

（1）队列式(FIFO)分支限界法

按照队列先进先出（FIFO ）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法

按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点

2.3分支限界法的设计思路

设求解最大化问题，解向量为X=(x1,…,xn) ，xi 的取值范围为Si ，|Si|=ri。在使用分支限界搜索问题的解空间树时，先根据限界函数估算目标函数的界[down, up]，然后从根结点出发，扩展根结点的r1个孩子结点，从而构成分量x1的r1种可能的取值方式。对这r1个孩子结点分别估算可能的目标函数bound(x1)，其含义：以该结点为根的子树所有可能的取值不大于bound(x1)，即： bound(x1)≥bound(x1,x2)≥…≥ bound(x1,…,xn)

若某孩子结点的目标函数值超出目标函数的下界，则将该孩子结点丢弃；否则，将该孩子结点保存在待处理结点表PT 中。再取PT 表中目标函数极大值结点作为扩展的根结点，重复上述。直到一个叶子结点时的可行解X=(x1,…,xn) ，及目标函数值bound(x1,…,xn) 。

2.4分支限界法与回溯法区别

（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。

（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

3分支限界法应用

3.1批处理作业问题

（1）问题提出。

给定n 个作业的集合J={J1,J2,…,Jn}。每一个作业Ji 都有2项任务要分别在2台机器上完成。每一个作业必须先由机器1处理，然后再由机器2处理。作业Ji 需要机器j 的处理时间为tji ，i=1,2,…,n ；j=1,2。对于一个确定的作业调度，设是Fji 是作业i 在机器j 上完成处理的时间。则所有作业在机器2上完成处理的时间和

f = 批处理作业调度问题要求对于给定的∑F 2i 称为该作业调度的完成时间和。

i =1n

n 个作业，制定最佳作业调度方案，使其完成时间和达到最小。 （2）算法分析。

在结点E 处相应子树中叶结点完成时间和的下界是：

f ≥∑F 2i +max{S 1, S 2}

i ∈M

注意到如果选择Pk ，使t1pk 在k>=r+1时依非减序排列，S1则取得极小值。同理如果选择Pk 使t2pk 依非减序排列，则S2取得极小值。

f ≥

i ∈M

∑F

2i

ˆ, S ˆ}+max{S 12

这可以作为优先队列式分支限界法中的限界函数。 （3）主要算法介绍。 do {

if (enode.s == n ) { if (enode.sf2

for (int i = 0; i

for (int i = enode.s; i

MyMath.swap(enode.x, enode.s,i); int [] f= new int [3]; int bb=bound(enode,f); if (bb

HeapNode node=new HeapNode(enode,f,bb,n); heap.put(node); } MyMath.swap(enode.x, enode.s,i); }

算法的while 循环完成对排列树内部结点的有序扩展。在while 循环体内算法依次从活结点优先队列中取出具有最小bb 值（完成时间和下界）的结点作为当前扩展结点，并加以扩展。首先考虑enode.s=n的情形，当前扩展结点enode 是排列树中的叶结点。enode.sf2是相应于该叶结点的完成时间和。当enode.sf2

3.2 旅行售货员问题

（1）问题提出。

某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费) 。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费) 最小。

（2）算法分析。

旅行商问题的解空间是一个排列树。

有两种实现的方法：第一种是只使用一个优先队列，队列中的每个元素 中都包含到达根的路径。另一种是保留一个部分解空间树和一个优先队列，优先队列中 的元素并不包含到达根的路径。

以下为第一种方法， 由于我们要寻找的是最小耗费的旅行路径，因此可以使用最小耗费分枝定界法。在实现过程中，使用一个最小优先队列来记录活节点，队列中每个节点的类型为MinHeapNode 。每个节点包括如下区域： x（从1到n 的整数排列，

其中x[0] = 1 ），s （一个整数，使得从排列树的根节点到当前节点的路径定义了旅行路径的前缀x[0:s], 而剩余待访问的节点是x [s + 1 : n - 1 ]），cc （旅行路径前缀，即解空间树中从根节点到当前节点的耗费），lcost （该节点子树中任意叶节点中的最小耗费）， rcost（从顶点x[s : n - 1]出发的所有边的最小耗费之和）。当类型为MinHeapNode( T )的数据被转换成为类型T 时，其结果即为lcost 的值。 程序代码：

#include #include using namespace std;

//---------------------宏定义------------------------------------------ #define MAX_CITY_NUMBER 10 //城市最大数目

#define MAX_COST 10000000 //两个城市之间费用的最大值

//---------------------全局变量---------------------------------------- int City_Graph[MAX_CITY_NUMBER][MAX_CITY_NUMBER]; //表示城市间边权重的数组 int City_Size; //表示实际输入的城市数目 int Best_Cost; //最小费用 int Best_Cost_Path[MAX_CITY_NUMBER];

//最小费用时的路径

//------------------------定义结点--------------------------------------- typedef struct Node{

int lcost; //优先级 int cc; //当前费用

int rcost; //剩余所有结点的最小出边费用的和 int s; //当前结点的深度，也就是它在解数组中的索引位置 int x[MAX_CITY_NUMBER]; //当前结点对应的路径 struct Node* pNext; //指向下一个结点 }Node;

//---------------------定义堆和相关对操作-------------------------------- typedef struct MiniHeap{

Node* pHead; //堆的头 }MiniHeap; //初始化

void InitMiniHeap(MiniHeap* pMiniHeap){ pMiniHeap->pHead = new Node; pMiniHeap->pHead->pNext = NULL; }

//入堆

void put(MiniHeap* pMiniHeap,Node node){ Node* next;

Node* pre;

Node* pinnode = new Node; //将传进来的结点信息copy 一份保存 //这样在函数外部对node 的修改就不会影响到堆了

pinnode->cc = node.cc;

pinnode->lcost = node.lcost; pinnode->pNext = node.pNext; pinnode->rcost = node.rcost; pinnode->s = node.s; pinnode->pNext = NULL;

for(int k=0;kx[k] = node.x[k]; }

pre = pMiniHeap->pHead;

next = pMiniHeap->pHead->pNext; if(next == NULL){

pMiniHeap->pHead->pNext = pinnode; } else{

while(next != NULL){

if((next->lcost) > (pinnode->lcost)){ //发现一个优先级大的，则置于其前面

pinnode->pNext = pre->pNext; pre->pNext = pinnode;

break; //跳出 }

pre = next;

next = next->pNext; }

pre->pNext = pinnode; //放在末尾 } }

//出堆

Node* RemoveMiniHeap(MiniHeap* pMiniHeap){ Node* pnode = NULL;

if(pMiniHeap->pHead->pNext != NULL){ pnode = pMiniHeap->pHead->pNext;

pMiniHeap->pHead->pNext = pMiniHeap->pHead->pNext->pNext; }

return pnode; }

//---------------------分支限界法找最优解-------------------------------- void Traveler(){ int i,j;

int temp_x[MAX_CITY_NUMBER];

Node* pNode = NULL;

int miniSum; //所有结点最小出边的费用和

int miniOut[MAX_CITY_NUMBER];

//保存每个结点的最小出边的索引

MiniHeap* heap = new MiniHeap; //分配堆

InitMiniHeap(heap); //初始化堆

miniSum = 0;

for (i=0;i

miniOut[i] = MAX_COST; //初始化时每一个结点都不可达

for(j=0;j

if (City_Graph[i][j]>0 && City_Graph[i][j]

//从i 到j 可达，且更小

miniOut[i] = City_Graph[i][j];

}

}

if (miniOut[i] == MAX_COST){// i 城市没有出边

Best_Cost = -1;

return ;

}

miniSum += miniOut[i];

}

for(i=0;i

走一遍

Best_Cost_Path[i] = i;

}

Best_Cost = MAX_COST; //初始化的最优费用是一个很大的数

pNode = new Node; //初始化第一个结点并入堆

pNode->lcost = 0; //当前结点的优先权为0 也就是最优

pNode->cc = 0; //当前费用为0（还没有开始旅行）

pNode->rcost = miniSum; //剩余所有结点的最小出边费用和就是初始

化的miniSum

pNode->s = 0; //层次为0

pNode->pNext = NULL;

for(int k=0;k

pNode->x[k] = Best_Cost_Path[k]; //第一个结点所保存的路径也就

是初始化的路径

}

put(heap,*pNode); //入堆

while(pNode != NULL && (pNode->s)

//堆不空 不是叶子

for(int k=0;k

Best_Cost_Path[k] = pNode->x[k] ; //将最优路径置换为当前结点本身所保存的

}

/*

* * pNode 结点保存的路径中的含有这条路径上所有结点的索引

* * x路径中保存的这一层结点的编号就是x[City_Size-2]

* * 下一层结点的编号就是x[City_Size-1] */

if ((pNode->s) == City_Size-2){ //是叶子的父亲

Int edge1 = City_Graph[(pNode->x)[City_Size-2]][(pNode->x)[City_Size-1]];

int edge2 = City_Graph[(pNode->x)[City_Size-1]][(pNode->x)[0]];

if(edge1 >= 0 && edge2 >= 0 && (pNode->cc+edge1+edge2) cc + edge1+edge2;

pNode->cc = Best_Cost;

pNode->lcost = Best_Cost; //优先权为 Best_Cost

pNode->s++; //到达叶子层

}

}

else{ //内部结点

for (i=pNode->s;i

if(City_Graph[pNode->x[pNode->s]][pNode->x[i]] >= 0){

//pNode的层数就是它在最优路径中的位置

Int temp_cc =

pNode->cc+City_Graph[pNode->x[pNode->s]][pNode->x[i]];

int temp_rcost = pNode->rcost-miniOut[pNode->x[pNode->s]];

//下一个结点的剩余最小出边费用和

//等于当前结点的rcost 减去当前这个结点的最小出边费用

if (temp_cc+temp_rcost

//下一个结点的最小出边费用和小于当前的最优解，说明可能存在更优解

for(j=0;j

temp_x[j]=Best_Cost_Path[j];

}

temp_x[pNode->x[pNode->s+1]] = Best_Cost_Path[i];

//将当前结点的编号放入路径的深度为s+1的地方

temp_x[i] = Best_Cost_Path[pNode->s+1];

Node* pNextNode = new Node;

pNextNode->cc = temp_cc;

pNextNode->lcost = temp_cc+temp_rcost;

pNextNode->rcost = temp_rcost;

pNextNode->s = pNode->s+1;

pNextNode->pNext = NULL;

for(int k=0;k

pNextNode->x[k] = temp_x[k];

}

put(heap,*pNextNode);

delete pNextNode;

}

}

}

}

pNode = RemoveMiniHeap(heap);

}

}

int main(){

int i,j;

printf("请输入旅行的节点数");

scanf("%d",&City_Size);

for(i=0;i

printf("请分别输入每个节点与其它节点的路程花费");

for(j=0;j

scanf("%d",&City_Graph[i][j]);

}

}

Traveler();

printf("最小花费""%d\n",Best_Cost);

return 1;

}

实验结果如图：

由于我们要寻找的是最小耗费的旅行路径，因此可以使用最小耗费分枝限界法。在实现过程中，使用一个最小优先队列来记录活节点，队列中每个节点的类型为MinHeapNode 。每个节点包括如下区域： x（从1到n 的整数排列，其中x[0] = 1 ），s （一个整数，使得从排列树的根节点到当前节点的路径定义了旅行路径的前缀x[0:s], 而剩余待访问的节点是x [s + 1 : n - 1 ]），cc （旅行路径前缀，即解空间树中从根节点到当前节点的耗费），lcost （该节点子树中任意叶节点中的最小耗费）， rcost（从顶点x[s : n - 1]出发的所有边的最小耗费之和）。当类型为MinHeapNode( T )的数据被转换成为类型T 时，其结果即为lcost 的值。

3.3单源最短路径问题

（1）问题提出。

下面以一个例子来说明单源最短路径问题：在下图所给的有向图G 中，每一边都有一个非负边权。要求图3-1从源顶点s 到目标顶点t 之间的最短路径。

图3-1 有向图G

（2）算法分析。

下图3-2是用优先队列式分支限界法解有向图G 的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。

图3-2 解空间树

程序代码：

#include

#include

#include

#include

using namespace std;

struct node_info

{

public:

node_info (int i,int w)

: index (i), weight (w) {}

node_info ()

: index(0),weight(0) {}

node_info (const node_info & ni)

: index (ni.index), weight (ni.weight) {}

friend

bool operator rth.weight ; // 为了实现从小到大的顺序 }

public:

int index; // 结点位置

int weight; // 权值

};

struct path_info

{

public:

path_info ()

: front_index(0), weight (numeric_limits::max()) {} public:

int front_index;

int weight;

};

class ss_shortest_paths


    相关文章

    1.比较文学的定义与目标

    绪论 第一章 比较文学的定义与目标 第一节 文学研究的新途径--比较文学 1.文学研究的三种途径--文学理论.文学批评和文学史 2.文学研究的另一种途径--比较文学 3.比较文学起源于了解他人的兴趣 (以上三点源于<比较文学简明教程& ...

    语义学与语用学的区别浅议_齐琳

    语义学与语用学的区别浅议 齐 琳 中国矿业大学(北京)文法学院 [摘 要]语义学和语用学是语言学的两个分支,它们都涉及对语言意义的研究.本文探讨了二者的关系与区别.尽管很难划分语义学与语用学的界限,但是关于这个问题的讨论可以使我们加深对语言 ...

    法理学简答题和论述题复习整理

    1. 马克思主义法学不同于其他法学的基本特色: 1) 客观性.坚持唯物主义的观点,认为法所体现的是由物质社会生活所决定的. 2) 历史性.坚持辩证发展的观点,认为法具有产生.发展和消亡的过程. 3) 阶级性.坚持阶级分析的观点,认为法主要体 ...

    新经济形式下网络金融的发展现状及未来发展趋势

    金融领域 中国市场2010年第22期(总第581期) 新经济形式下网络金融的发展 现状及未来发展趋势 孔繁强 (北京大学 经济学院,北京100871) ［摘要］本文陈述了网络金融的发展态势及其可能对传统金融产业产生的深刻影响,对我国网络金融 ...

    组织理论与组织设计

    12.2影响组织结构的因素 影响组织结构的因素主要有环境的不确定性.技术水平.组织规模.组织战略匹配程度.文化的认同程度等. 12.2.1环境与组织 组织环境是组织边界之外的并对组织具有潜在或者部分影响的某些方面.每个组织可以分析的环境大致 ...

    浅谈对现代数学的理解

    浅淡对现代数学的理解 摘要:数学作为一门基础学科,是各学科领域进行科学研究工作不可或缺的知识.随着工程技术日新月异的发展,对数学的要求愈来愈高,现代数学的观点.方法已渗透到工程技术的各个领域,要求工程技术人员不仅具备经典的数学知识和处理问题 ...

    grasshopper中文版运算器名称对照

    grasshopper 中文版运算器名称对照翻译 Params:参数 Geometry:几何体 Box: 立方体 BRep: 边界表现形式 Circle: 圆 Circular Arc: 圆弧 Curve: 曲线 Geometry: 几何 ...

    会计学的学科属性_管理学还是经济学_陈德刚

    会计学的学科属性:管理学还是经济学?短论 会计学的学科属性:管理学还是经济学? 陈德刚 摘要:本文首先分别阐述会计学具有管理学属性.经济学属性的现实证据,然后提出并论证会计学具有经济学与管理学双重学科属性. 关键词:会计学学科属性经济学管理 ...

    商事案件裁判规则之一

    商事案件裁判规则之一 一.审理公司诉讼案件的一般规则 1.审理公司诉讼案件要注意各方权利的兼顾. 2.公司诉讼案件审理应适用可诉性标准与司法救济的正当性标准. 3.公司修改章程不承担继受而来债务的,应有法律依据或者经债权人同意,否则不能对抗 ...

随机推荐

TAG