问题描述:
（1）哈密顿环问题：输入是一个无向连通图G=(V,E)；如果G中存在哈密顿环则输出该环。
（2）最小哈密顿环问题：输入是一个无向连通图G=(V,E)，每个节点都没有到自身的边，每对节点间都有一条非负加权边；输出一个权值代价和最小的哈密顿环。注意：事实上输入图是一个完全图，因此哈密顿环是一定存在的。
实现哈密顿环搜索算法
（1）哈密顿环问题：(a)实现基于树的基本搜索算法(BFS,DFS) (b)爬山法
（2）最小哈密顿环问题：(a)实现求解最小哈密顿环问题的分支界限算法。
1.DFS
算法的主要步骤:
2.BFS
算法的主要步骤:
3.ClimbingHill
算法的主要步骤:
4.BranchBound
算法的主要原理:
源码：
Grap.h
~~~
/*
*Tree Search Strategy 15S103182 Ethan
*2015.12.1
*/
#include<iomanip>
#include<limits>
#include<time.h>
#include<stdlib.h>
#include<iostream>
#include<fstream>
using namespace std;
template<class E> //E为图中边的权值的数据类型
class Graph {
private:
int maxVertices; //图中最大顶点数
E **matrix;//邻接矩阵
public:
E maxWeight; //代表无穷大的值
Graph(int sz);//创建SZ大小的基于邻接矩阵的图
~Graph();//析构函数
int NumberOfVertices() {
return maxVertices; //返回最大顶点数
}
E getWeight(int v1, int v2); //取边（v1,v2)上的权值
int getFirstNeighbor(int v);//取顶点v的第一个邻接顶点
int getNextNeighbor(int v, int w);//取顶点v的邻接顶点W的下一个邻接顶点
int Init(istream &in);//根据用户输入，获得图的邻接矩阵
int RandInitN();//随机初始化图(无向图)
int RandInit();//随机初始化图(完全无向图)
int output(ostream &out); //输出图的矩阵到文件
int output(); //输出图的矩阵到控制台
};
template<class E>
Graph<E>::Graph(int sz) { //创建SZ大小的基于邻接矩阵的图
maxWeight = std::numeric_limits<E>::max();
maxVertices = sz;
matrix = new E *[sz];
for (int i = 0; i<sz; i++) {
matrix[i] = new E[sz];
for (int j = 0; j<sz; j++) {
matrix[i][j] = maxWeight;
}
}
}
template<class E>
Graph<E>::~Graph() {
for (int i = 0; i<maxVertices; i++) {
delete matrix[i];
}
}
template<class E>
E Graph<E>::getWeight(int v1, int v2) { //取边（v1,v2)上的权值
if (v1 >= 0 && v1<maxVertices&&v2 >= 0 && v2<maxVertices) {
return matrix[v1][v2];
}
return 0;
}
template<class E>
int Graph<E>::getFirstNeighbor(int v) { //取顶点v的第一个邻接顶点
if (!(v >= 0 && v<maxVertices)) //v不合法
return -1;
for (int col = 0; col<maxVertices; col++) {
if (matrix[v][col] != maxWeight) {
return col; //找到
}
}
return -1; //未找到
}
template<class E>
int Graph<E>::getNextNeighbor(int v, int w) { //取顶点v的邻接顶点W的下一个邻接顶点
if (!(v >= 0 && v<maxVertices) || !(w >= 0 && w<maxVertices)) //v或w不合法
return -1;
for (int col = w + 1; col<maxVertices; col++) {
if (matrix[v][col] != maxWeight) {
return col; //找到
}
}
return -1;//未找到
}
template<class E>
int Graph<E>::Init(istream &fin) { //根据输入文件，获得图的邻接矩阵
int v1, v2;
E edge;
while (fin >> v1 >> v2 >> edge) {
if (v1 >= 0 && v1<maxVertices&&v2 >= 0 && v2<maxVertices) {
matrix[v1][v2] = edge;
matrix[v2][v1] = edge;
}
if (edge == maxWeight) { //当输入边值为无穷大时停止输入
break;
}
}
return 1;
}
template<class E>
int Graph<E>::RandInitN() { //随机初始化图(无向图,非完全)
for (int i = 0; i<maxVertices; i++) {
for (int j = 0; j<maxVertices; j++) {
matrix[i][j] = maxWeight;
}
}
srand((int)time(0));
// int rnd = maxVertices*(maxVertices - 1) / 3;
//// int count = rand() / RAND_MAX*rnd / 4 + 3 * rnd / 4;
// int count = rnd / 2;
// int v1, v2;
// while (count) {
// v1 = rand() % maxVertices;
// v2 = rand() % maxVertices;
// if (v1 != v2&&matrix[v1][v2] == maxWeight) {
// matrix[v2][v1] = matrix[v1][v2] = rand();
// count--;
// }
// }
for(int v1=0;v1<maxVertices;v1++)
for(int v2=0;v2<maxVertices;v2++){
if (v1 != v2&&matrix[v1][v2] == maxWeight){
matrix[v2][v1] = matrix[v1][v2] = rand()%2;
}
}
return 1;
}
template<class E>
int Graph<E>::RandInit() { //随机初始化图(无向完全图)
for (int i = 0; i<maxVertices; i++) {
for (int j = 0; j<maxVertices; j++) {
matrix[i][j] = maxWeight;
}
}
srand((int)time(0));
int count = maxVertices*(maxVertices - 1) / 2;
int v1, v2;
while (count) {
v1 = rand() % maxVertices;
v2 = rand() % maxVertices;
if (v1 != v2&&matrix[v1][v2] == maxWeight) {
if(v1-v2==1||v2-v1==1) matrix[v2][v1] = matrix[v1][v2] = rand()%2000;
else matrix[v2][v1] = matrix[v1][v2] = rand();
count--;
}
}
return 1;
}
template<class E>
int Graph<E>::output(ostream &out) { //输出图的矩阵
for (int i = 0; i<maxVertices; i++) {
for (int j = 0; j<maxVertices; j++) {
out << setw(15) << matrix[i][j] << ",";
}
out << endl;
}
return 1;
}
template<class E>
int Graph<E>::output() { //输出图的矩阵
for (int i = 0; i<maxVertices; i++) {
cout<<"\t";
for (int j = 0; j<maxVertices; j++) {
cout << setw(15) << matrix[i][j] << ",";
}
cout << endl;
}
return 1;
}
~~~
源码：
Graph.cpp
~~~
/*
*Tree Search Strategy 15S103182 Ethan
*2015.12.1
*/
#include"Graph.h"
#include<iostream>
#include<fstream>
#include<sstream>
#include<stack>
#include<queue>
#include<limits>
#include<memory.h>
#include<string.h>
using namespace std;
template<class E>
struct NODE {
int dep; //表示该结点在搜索树的第几层
int *vertices; //该节点包含的各个顶点
E length; //从根到当前结点已经走过的路径长度
NODE(int depth) {
dep = depth;
vertices = new int[dep];
};
void cpy(int *&des) {
for (int i = 0; i<dep; i++) {
des[i] = vertices[i];
}
}
bool find(int v) {
for (int i = 0; i<dep; i++) {
if (vertices[i] == v)
return true;
}
return false;
}
};
template<class E>
int dfs(int start, Graph<E> &myGraph) { //deepFirst 判断图中是否存在哈密顿回路
stack<int> myStack;
myStack.push(start);
int numVertices = myGraph.NumberOfVertices();
bool *visited = new bool[numVertices];
memset(visited, false, numVertices);
int v;
int w = -1;
while (!myStack.empty()) { //栈不为空
v = myStack.top();
visited[v] = true;
if (w == -1) {
w = myGraph.getFirstNeighbor(v);
} else {
w = myGraph.getNextNeighbor(v, w);
}
for (; w != -1 && visited[w] == true; w = myGraph.getNextNeighbor(v, w)) {}
if (w == -1) { //未找到可行的下一个顶点,子节点都在栈中
myStack.pop(); //回溯
w = v;
visited[v] = false;
} else { //找到可行的下一个顶点
myStack.push(w); //放入栈中
if (myStack.size() == numVertices) { //走过所有的顶点
if (myGraph.getWeight(start, w) == std::numeric_limits<E>::max()) { //判断最后一个顶点有没有回到起点的边
myStack.pop();
visited[w] = false;
} else { //成功找到回路
return 1;
}
} else {
w = -1;
}
}
}
return 0;
}
template<class E>
int ch(int start, Graph<E> &myGraph) { //climbingHill 爬山法判断图中是否存在哈密顿回路
stack<int> myStack;
myStack.push(start);
int numVertices = myGraph.NumberOfVertices();
bool *visited = new bool[numVertices];
memset(visited, false, numVertices);
int v;
int w = -1;
while (!myStack.empty()) { //栈不为空
v = myStack.top();
visited[v] = true;
if (w == -1) {
w = myGraph.getFirstNeighbor(v);
} else {
w = myGraph.getNextNeighbor(v, w);
}
for (; w != -1 && visited[w] == true; w = myGraph.getNextNeighbor(v, w)) {}
int greedy = w;//贪心选择子顶点
for (; w != -1 && visited[w] == false; w = myGraph.getNextNeighbor(v, w)) {
if(myGraph.getWeight(v, w) < myGraph.getWeight(v, greedy)) {
greedy = w;
}
}
w = greedy;
if (w == -1) { //未找到可行的下一个顶点
myStack.pop(); //回溯
w = v;
visited[v] = false;
} else { //找到可行的下一个顶点
myStack.push(w); //放入栈中
if (myStack.size() == numVertices) { //走过所有的顶点
if (myGraph.getWeight(start, w) == std::numeric_limits<E>::max()) { //判断最后一个顶点有没有回到起点的边
myStack.pop();
visited[w] = false;
} else { //成功找到回路
return 1;
}
} else {
w = -1;
}
}
}
return 0;
}
template<class E>
int climbingHill(int start, Graph<E> &myGraph, ostream & fout) { //算法解决图的最小哈密顿回路问题 v为回路的起点和终点
stack<int> myStack;
myStack.push(start);
int numVertices = myGraph.NumberOfVertices();
bool *visited = new bool[numVertices];
memset(visited, false, numVertices);
int v;
int w = -1;
while (!myStack.empty()) { //栈不为空
v = myStack.top();
visited[v] = true;
if (w == -1) {
w = myGraph.getFirstNeighbor(v);
} else {
w = myGraph.getNextNeighbor(v, w);
}
for (; w != -1 && visited[w] == true; w = myGraph.getNextNeighbor(v, w)) {}
int greedy = w;//贪心选择子顶点
for (; w != -1 && visited[w] == false; w = myGraph.getNextNeighbor(v, w)) {
if(myGraph.getWeight(v, w) < myGraph.getWeight(v, greedy)) {
greedy = w;
}
}
w = greedy;
if (w == -1) { //未找到可行的下一个顶点
myStack.pop(); //回溯
w = v;
visited[v] = false;
} else { //找到可行的下一个顶点
myStack.push(w); //放入栈中
if (myStack.size() == numVertices) { //走过所有的顶点
if (myGraph.getWeight(start, w) == std::numeric_limits<E>::max()) { //判断最后一个顶点有没有回到起点的边
myStack.pop();
visited[w] = false;
} else { //成功找到回路
stack<int> temp;
while (!myStack.empty()) {
int n = myStack.top();
temp.push(n);
myStack.pop();
}
fout << "哈密顿回路 : ";
E distance = 0;
int n = temp.top();
myStack.push(n);
temp.pop();
int last = n;
fout << n << "--";
while (!temp.empty()) {
n = temp.top();
myStack.push(n);
temp.pop();
distance += myGraph.getWeight(last, n);
last = n;
fout << n << "--";
}
fout << start << endl;
distance += myGraph.getWeight(last, start);
fout << "总长度为:" << distance << endl;
return distance;
}
} else {
w = -1;
}
}
}
return std::numeric_limits<E>::max();
}
template<class E>
int bfs(int start, Graph<E> & myGraph) { //broadFirst 判断图中是否存在哈密顿回路
stack<NODE<E> > myStack; //队列
int s = myGraph.getFirstNeighbor(start);
for (s = myGraph.getNextNeighbor(start, s); s != -1; s = myGraph.getNextNeighbor(start, s)) {
NODE<E> n(2);
n.vertices[0] = start;
n.vertices[1] = s;
n.length = myGraph.getWeight(start, s);
myStack.push(n);
}
while (!myStack.empty()) { //队列不为空
NODE<E> n = myStack.top();
myStack.pop();
int v = n.vertices[n.dep - 1];
if (n.dep + 1 == myGraph.NumberOfVertices()) { //到了最后一层 判断是不是哈密顿回路
int w;
for (w = myGraph.getFirstNeighbor(v); w != -1; w = myGraph.getNextNeighbor(v, w)) {
if (n.find(w) == false)
break;
}
if (w != -1) {
if (myGraph.getWeight(w, start)<std::numeric_limits<E>::max()) {
return 1;
}
}
}
for (int w = myGraph.getFirstNeighbor(v); w != -1; w = myGraph.getNextNeighbor(v, w)) {
if (n.find(w) == false) {
NODE<E> ne(n.dep + 1);
ne.length = n.length + myGraph.getWeight(v, w);
n.cpy(ne.vertices);
ne.vertices[ne.dep - 1] = w;
myStack.push(ne);
}
}
}
return 0;
}
//分支限界法求解最短哈密顿回路问题
template<class E>
int branchBound(int start, Graph<E> & myGraph, ostream & fout) {
stack<NODE<E> > myStack; //队列
E minDistance = climbingHill(start,myGraph,fout);//爬山法获取首界限
int s = start;
for (s = myGraph.getFirstNeighbor(start); s != -1; s = myGraph.getNextNeighbor(start, s)) {//首次分支
NODE<E> n(2);
n.vertices[0] = start;
n.vertices[1] = s;
n.length = myGraph.getWeight(start, s);
myStack.push(n);
}
while (!myStack.empty()) { //队列不为空
NODE<E> n = myStack.top();
myStack.pop();
int v = n.vertices[n.dep - 1];
if (n.dep + 1 == myGraph.NumberOfVertices()) { //到了最后一层 判断是不是哈密顿回路
int w;
for (w = myGraph.getFirstNeighbor(v); w != -1; w = myGraph.getNextNeighbor(v, w)) {
if (n.find(w) == false)//确定最后一个节点
break;
}
if (w != -1) {
if (myGraph.getWeight(w, start)<std::numeric_limits<E>::max()) { //如果找到且存在路径
E tempDistance = n.length + myGraph.getWeight(v, w) + myGraph.getWeight(w, start);
if (minDistance>tempDistance) {
// 形成回路
fout << "哈密顿回路为:";
// cout << "哈密顿回路为:";
for (int i = 0; i<n.dep; i++) {
fout << n.vertices[i] << " ";
// cout << n.vertices[i] << " ";
}
fout << w << " " << start << endl;
// cout << w << " " << start << endl;
fout << "总长度为: " << tempDistance << endl;
// cout << "总长度为: " << tempDistance << endl;
minDistance = tempDistance;
}
}
}
}
for (int w = myGraph.getFirstNeighbor(v); w != -1; w = myGraph.getNextNeighbor(v, w)) {
if (n.find(w) == false) {//存在未遍历顶点
NODE<E> ne(n.dep + 1);
ne.length = n.length + myGraph.getWeight(v, w);
if (ne.length<minDistance) {//剪枝
n.cpy(ne.vertices);
ne.vertices[ne.dep - 1] = w;
myStack.push(ne);
}
}
}
}
return minDistance;
}
int main(int argc, char** argv) {
for(int i=8; i<=20; i+=2) {
cout<<endl<<"节点数:"<<i<<endl;
Graph<int> myGraph(i);
Graph<int> myGraphN(i);
myGraph.RandInit();//随机初始化完全无向图
myGraphN.RandInitN();//随机初始化图
int a = clock();
cout<<"deepFirst:"<<dfs(0,myGraphN)<<"\t\t";
int b = clock();
int st = b - a;
cout<<"dfs time:"<<st<<endl;
int a1 = clock();
cout<<"broadFirst:"<<bfs(0,myGraphN)<<"\t\t";
int b1 = clock();
int st1 = b1 - a1;
cout<<"bfs time:"<<st1<<endl;
int a2 = clock();
cout<<"climbingHill:"<<ch(0,myGraphN)<<"\t\t";
int b2 = clock();
int st2 = b2 - a2;
cout<<"ch time:"<<st2<<endl;
char mat[20];
itoa(i,mat,10);
strcat(mat,"matrix.txt");
ofstream fout2(mat);
myGraph.output(fout2);
char matN[20];
itoa(i,matN,10);
strcat(matN,"matrixN.txt");
ofstream fout3(matN);
myGraphN.output(fout3);
// cout<<"Matrix["<<i<<"]["<<i<<"]:"<<endl;
// myGraph.output();
char bbn[20];
itoa(i,bbn,10);
strcat(bbn,"branchBound.txt");
ofstream fout1(bbn);
int a3 = clock();
cout<<"branchBound:"<<branchBound(0,myGraph,fout1)<<"\t";
int b3 = clock();
int st3 = b3 - a3;
cout<<"branchBound time:"<<st3<<endl;
}
//手动输入图
// Graph<int> myGraphN(4);
// ifstream fin("input.txt");
// myGraphN.Init(fin);
// cout<<"deepFirst:"<<dfs(0,myGraphN)<<endl;
// cout<<"broadFirst:"<<bfs(0,myGraphN)<<endl;
// cout<<"climbingHill:"<<ch(0,myGraphN)<<endl;
// ofstream fout2("matrix.txt");
// myGraphN.output(fout2);
// cout<<"Matrix[4][4]:"<<endl;
// myGraphN.output();
// ofstream fout1("branchBound.txt");
// cout<<"branchBound:"<<branchBound(0,myGraphN,fout1)<<endl;
return 0;
}
~~~
BranchBound的性能曲线如下图：
由性能曲线图可以看出，当输入完全图的点数增加时，算法的运行时间也会成倍增加，造成这种效果的原因主要是为了求解最优解，算法在最坏情况下复杂度是O(n!)，虽然通过剪枝策略能够大大提高效率，但算法时间复杂度依旧很高。
- 前言
- 插入排序
- 归并排序
- 快速排序
- 最长公共子序列
- 斐波那契数列-台阶问题
- 求n*n阶矩阵最大子矩阵阶数
- 01背包
- 整数序列合并问题
- 动态规划算法的一般解题思路
- 01背包-近似算法
- 树搜索策略
- 求数组中的逆序对
- 并行机器最短调度问题
- 随机算法
- 判断两多项式之积是否等于另一多项式
- 顶点覆盖问题
- Apriori算法 (Introduction to data mining)
- 聚类算法-DBSCAN-C++实现
- 聚类算法-K-means-C++实现
- 聚类算法-Hierarchical(MIN)-C++
- 爬山法、分支限界法求解哈密顿环问题
- Best-First求解八数码问题
- Naive Bayesian文本分类器