前言

  • 思路来源, 这篇文章里介绍的真的是非常详细, 文章中有大连理工大学的pdf, 也可也学到很多

  • 蚁群算法属于智能算法, 并不一定收敛到最优解, 但对75点一下规模的问题能很好的解决

  • 代码参考

思路

  • tsp问题的思路在前言中的文章里已经有了详细的介绍, 所以只介绍我解决不闭合tsp问题的思路

tsp问题的解决

  • 原理见前言文章与code, 仅展示下结果和逻辑图

  • 30个点感觉并不是很好

  • 50点

不闭合tsp问题的解决

  • 与tsp问题类似, 但主要差别只遍历所有的点但不返回原点.

  1. 第一阶段

    1. 在随机的城市生成蚂蚁, 蚂蚁的总数量与城市数量相等
    2. 每一只蚂蚁通过由信息素与能见度共同决定的规则产生前往不同城市的概率, 并以这个概率随机决定下一个城市
    3. 所有蚂蚁回到原点后更新每条路径上的信息素含量
    4. 达到遍历次数后进入第二阶段

  2. 第二阶段

    1. 在随机的城市生成SUPER蚂蚁, SUPER蚂蚁的总数量与城市数量相等
    2. 每一只SUPER蚂蚁通过由信息素与能见度共同决定的规则产生前往不同城市的概率, 并以这个概率随机决定下一个城市
    3. 所有SUPER蚂蚁遍历过除了不闭合tsp问题的起点外的所有的点前往不闭合tsp问题的起点
    4. 计算并不断更新最短路径的SUPER蚂蚁
    5. 达到迭代次数后输出最短路径的SUPER蚂蚁
    • 第一阶段
    • 第二阶段

  • 与简单贪心的比较

    • 30 点
    • 50 点

  • code

/*************************************************************************
	> File Name: YiQun_Tsp.cpp
	> Author: Wqr_
	> Mail: xueduanwei@126.com
	> Created Time: Sun Oct 14 22:56:12 2018
 ************************************************************************/

// 这个是返回的
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
#define random(x)(rand()%x)
const int NUM = 30; // 城市的数量以及蚂蚁的数量
const int ANT_NUM = NUM; // 蚂蚁的数量
const int CITY_NUM = NUM; // 城市
double dis[NUM][NUM];
double info[NUM][NUM];
const double mmax = 1 << 21;
double tanXindis;

#define TNUM 2000
#define ALPHA 1
#define BETA 4

//返回指定范围内的随机整数
int rnd(int nLow, int nUpper)
{
	return nLow + (nUpper - nLow)*rand() / (RAND_MAX + 1);
}

//返回指定范围内的随机浮点数
double rnd(double dbLow, double dbUpper)
{
	double dbTemp = rand() / ((double)RAND_MAX + 1.0);
	return dbLow + dbTemp * (dbUpper - dbLow);
}

// 蚁群的语句

struct Ant
{

	int Path[CITY_NUM];  //路径顺序
	double length;  //路径长度
	int visit[CITY_NUM]; //记录城市是否被访问过
	int now;   //当前城市
	int visitNo;    //第几个城市
	//初始化
	void Init()
	{
		memset(visit, 0, sizeof(visit));
		length = 0;
		now = rnd(0, CITY_NUM);//随机选择一个出发城市
		Path[0] = now;
		visit[now] = 1;
		visitNo = 1;
	}
	//选择下一个城市
	int chooseNextCity()
	{
		int next = -1; //下一个城市的编号
		//计算当前城市和没去过的城市之间的信息素总和
		double dbTotal = 0.0;
		double gaiLv[CITY_NUM]; //各个城市被选中的概率
		for (int i = 0; i < CITY_NUM; i++)
		{
			if (!visit[i])
			{
				gaiLv[i] = pow(info[now][i], ALPHA)
					*pow(1.0 / dis[now][i], BETA);
				dbTotal += gaiLv[i];
			}
			else
			{
				gaiLv[i] = 0;
			}
		}
		//进行轮盘赌博 (随缘
		double dbTemp = 0.0;
		if (dbTotal > 0.0)
		{
			dbTemp = rnd(0.0, dbTotal);
			for (int i = 0; i < CITY_NUM; i++)
			{
				if (!visit[i])
				{
					dbTemp -= gaiLv[i];
					if (dbTemp < 0.0)
					{
						next = i;
						break;
					}
				}
			}
		}

		// 如果信息素含量很小, 就选出现的第一个

		if (next == -1)
		{
			for (int i = 1; i < CITY_NUM; i++)
			{
				if (!visit[i])
				{
					next = i;
					break;
				}
			}
		}

		return next;
	}

	void Move()
	{
		int next = chooseNextCity();
		Path[visitNo] = next;
		visit[next] = 1;
		now = next;
		// 计算新的距离
		length += dis[Path[visitNo - 1]][Path[visitNo]];
		visitNo++;

	}

	// 搜索
	void Search()
	{
		Init();
		// 经过所有城市
		while (visitNo < CITY_NUM)
		{
			Move();
		}
		// 回到起始点
		length += dis[Path[CITY_NUM - 1]][Path[0]];
	}
};


struct TSP
{
	Ant ants[ANT_NUM];  //一群蚂蚁
	Ant bestAnt; // 路径最短的蚂蚁
	void Init()
	{
		//初始化环境信息素
		for (int i = 0; i < CITY_NUM; i++)
		{
			for (int j = 0; j < CITY_NUM; j++)
			{
				info[i][j] = ANT_NUM * 15 / tanXindis;
			}
		}
	}

	void Updateinfo()
	{
		double tmpinfo[CITY_NUM][CITY_NUM];
		memset(tmpinfo, 0, sizeof(tmpinfo));
		int m = 0;
		int n = 0;
		//遍历每只蚂蚁
		for (int i = 0; i < ANT_NUM; i++) {
			for (int j = 1; j < CITY_NUM; j++)
			{
				m = ants[i].Path[j];
				n = ants[i].Path[j - 1];
				tmpinfo[n][m] = tmpinfo[n][m] + 3 * ANT_NUM / ants[i].length;
				tmpinfo[m][n] = tmpinfo[n][m];
			}
			//最后城市和开始城市之间的信息素
			n = ants[i].Path[0];
			tmpinfo[n][m] = tmpinfo[n][m] + 3 * ANT_NUM / ants[i].length;
			tmpinfo[m][n] = tmpinfo[n][m];
		}

		//更新环境信息素
		for (int i = 0; i < CITY_NUM; i++)
		{
			for (int j = 0; j < CITY_NUM; j++) {
				//最新的环境信息素 = 留存的信息素 + 新留下的信息素
				info[i][j] = info[i][j] * 0.5 + tmpinfo[i][j];

			}
		}
	}
	//寻找路径，迭代TNUM次
	void Search()
	{
		bestAnt.length = 1 << 21;
		for (int i = 0; i < TNUM; i++) {
			for (int j = 0; j < ANT_NUM; j++) {
				ants[j].Search();
			}
			for (int j = 0; j < ANT_NUM; j++) {
				if (bestAnt.length > ants[j].length) {
					bestAnt = ants[j];
				}
			}
			Updateinfo();
		}

		for (int i = 0; i < CITY_NUM; i++) {
			if (i) cout << "->";
			cout << bestAnt.Path[i];
		}
		cout << "->" << bestAnt.Path[0];
		cout << endl;
		cout << "距离为 : ";
		cout << bestAnt.length << endl;
	}
};



// 贪心法的语句
double TanXin(int from, int* visit, double sum, int* shunXv, int pointNum) {
	int flag = true;
	for (int i = 0; i < NUM; i++) {
		if (visit[i] == 0) {
			flag = false;
			break;
		}
	}

	if (flag) return sum;

	double min = 1000000;
	int to;
	for (int i = 0; i < NUM; i++) {
		if (dis[from][i] < min && visit[i] == 0) {
			min = dis[from][i];
			to = i;
		}
	}
	sum += dis[from][to];
	visit[to] = 1;
	shunXv[pointNum++] = to;
	return TanXin(to, visit, sum, shunXv, pointNum);
}

double qiujv(int x1, int y1, int x2, int y2) {
	return sqrt((double)(x1 - x2)*(x1 - x2) + (double)(y1 - y2)*(y1 - y2));
}

struct point {
	int x;
	int y;
};

// 主函数
int main() {
	// fanWei 代表范围
	// chuShi 代表起始位置, 即0
	int fanWei;
	int chuShi = 0;
	cout << "请输入范围 : ";
	cin >> fanWei;
	point point[NUM];
	for (int i = 0; i < NUM; i++) {
		point[i].x = random(fanWei);
		point[i].y = random(fanWei);
	}
	for (int i = 0; i < NUM; i++) {
		for (int j = 0; j < NUM; j++) {
			dis[i][j] = qiujv(point[i].x, point[i].y, point[j].x, point[j].y);
		}
	}
	double min = 100000; // 最小值
	int to; //要去的
	double sum = 0; //总数
	int shunXv[NUM] = { 0 }; // 顺序
	int visit[NUM] = { 0 }; // 储存访问过的点
	for (int i = 1; i < NUM; i++) {
		if (dis[0][i] < min) {
			min = dis[0][i];
			to = i;
		}
	}
	sum += dis[0][to];
	shunXv[1] = to;
	visit[0] = 1;
	visit[to] = 1;
	tanXindis = TanXin(to, visit, sum, shunXv, 2);
	tanXindis += dis[shunXv[49]][0];
	cout << endl;
	cout << "*********** 贪心的结果 **********" << endl;
	for (int i = 0; i < NUM; i++) {
		if (i) cout << "->";
		cout << shunXv[i];
	}
	cout << "->" << 0;
	cout << endl;
	cout << "距离为 : " << tanXindis << endl;
	cout << endl;
	cout << "*********** 蚁群的结果 **********" << endl;
	TSP tsp;
	tsp.Init();
	tsp.Search();
	return 0;
}
/*************************************************************************
	> File Name: YiQun.cpp
	> Author: Wqr_
	> Mail: xueduanwei@126.com
	> Created Time: Sun Oct 14 22:56:12 2018
 ************************************************************************/
// 这个是不返回起点的
#include"pch.h"
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
#define random(x)(rand()%x)
const int NUM = 30; // 城市的数量以及蚂蚁的数量
const int ANT_NUM = NUM; // 蚂蚁的数量
const int CITY_NUM = NUM; // 城市
double dis[NUM][NUM];
double info[NUM][NUM];
const double mmax = 1 << 21;
double tanXindis;

#define TNUM 2000
#define ALPHA 1
#define BETA 4

//返回指定范围内的随机整数
int rnd(int nLow, int nUpper)
{
	return nLow + (nUpper - nLow)*rand() / (RAND_MAX + 1);
}

//返回指定范围内的随机浮点数
double rnd(double dbLow, double dbUpper)
{
	double dbTemp = rand() / ((double)RAND_MAX + 1.0);
	return dbLow + dbTemp * (dbUpper - dbLow);
}

// 蚁群的语句

struct Ant
{

	int Path[CITY_NUM];  //路径顺序
	double length;  //路径长度
	int visit[CITY_NUM]; //记录城市是否被访问过
	int now;   //当前城市
	int visitNo;    //第几个城市
	//初始化
	void Init()
	{
		memset(visit, 0, sizeof(visit));
		length = 0;
		now = rnd(1, CITY_NUM);//随机选择一个除0的城市出发城市
		Path[0] = now;
		visit[now] = 1;
		visitNo = 1;
	}
	//选择下一个城市
	int chooseNextCity()
	{
		int next = -1; //下一个城市的编号
		//计算当前城市和没去过的城市之间的信息素总和
		double dbTotal = 0.0;
		double gaiLv[CITY_NUM]; //各个城市被选中的概率
		// 因为0点作为起点, 所以不计入循环
		for (int i = 1; i < CITY_NUM; i++)
		{
			if (!visit[i])
			{
				gaiLv[i] = pow(info[now][i], ALPHA)
					*pow(1.0 / dis[now][i], BETA);
				dbTotal += gaiLv[i];
			}
			else
			{
				gaiLv[i] = 0;
			}
		}
		//进行轮盘赌博 (随缘
		double dbTemp = 0.0;
		if (dbTotal > 0.0)
		{
			dbTemp = rnd(0.0, dbTotal);
			// 因为0点作为起点, 所以不计入循环
			for (int i = 1; i < CITY_NUM; i++)
			{
				if (!visit[i])
				{
					dbTemp -= gaiLv[i];
					if (dbTemp < 0.0)
					{
						next = i;
						break;
					}
				}
			}
		}

		// 如果信息素含量很小, 就选出现的第一个

		if (next == -1)
		{
			for (int i = 1; i < CITY_NUM; i++)
			{
				if (!visit[i])
				{
					next = i;
					break;
				}
			}
		}

		return next;
	}

	void Move()
	{
		int next = chooseNextCity();
		Path[visitNo] = next;
		visit[next] = 1;
		now = next;
		// 计算新的距离
		length += dis[Path[visitNo - 1]][Path[visitNo]];
		visitNo++;

	}

	// 搜索
	void Search()
	{
		Init();
		// 经过除去零点的所有城市
		while (visitNo < CITY_NUM - 1)
		{
			Move();
		}
		// 回到0点
		Path[CITY_NUM - 1] = 0;
		visit[0] = 1;
		length += dis[Path[CITY_NUM - 1 - 1]][Path[CITY_NUM - 1]];
	}

};

// 从零点出发的超级蚂蚁
struct SuperAnt {

	int Path[CITY_NUM];  //路径顺序
	double length;  //路径长度
	int visit[CITY_NUM]; //记录城市是否被访问过
	int now;   //当前城市
	int visitNo;    //第几个城市
	//初始化
	void Init()
	{
		memset(visit, 0, sizeof(visit));
		length = 0;
		now = 0; // 以0为起始城市
		Path[0] = now;
		visit[now] = 1;
		visitNo = 1;
	}

	int chooseNextCity()
	{
		int next = -1;
		double dbTotal = 0.0;
		double gaiLv[CITY_NUM];
		// 因为 0 已经被选中 , 不再重复选择
		for (int i = 1; i < CITY_NUM; i++)
		{
			if (!visit[i])
			{
				gaiLv[i] = pow(info[now][i], ALPHA)
					*pow(1.0 / dis[now][i], BETA);
				dbTotal += gaiLv[i];
			}
			else
			{
				gaiLv[i] = 0;
			}
		}
		//进行轮盘赌博 (随缘
		double dbTemp = 0.0;
		if (dbTotal > 0.0)
		{
			dbTemp = rnd(0.0, dbTotal);
			// 因为 0 已经被选中 , 不再重复选择
			for (int i = 1; i < CITY_NUM; i++)
			{
				if (!visit[i])
				{
					dbTemp -= gaiLv[i];
					if (dbTemp < 0.0)
					{
						next = i;
						break;
					}
				}
			}
		}

		if (next == -1)
		{
			for (int i = 1; i < CITY_NUM; i++)
			{
				if (!visit[i]) //城市没去过
				{
					next = i;
					break;
				}
			}
		}
		return next;
	}

	void Move()
	{
		int next = chooseNextCity();
		Path[visitNo] = next;
		visit[next] = 1;
		now = next;
		length += dis[Path[visitNo - 1]][Path[visitNo]];
		visitNo++;

	}
	//搜索
	void Search()
	{
		Init();
		// 让超级蚂蚁经过所有城市
		while (visitNo < CITY_NUM)
		{
			Move();
		}
	}
};

struct TSP
{
	Ant ants[ANT_NUM];  //一群蚂蚁
	SuperAnt SuperAnts[ANT_NUM]; //一群超级蚂蚁
	SuperAnt bestSuperAnt; // 路径最短的超级蚂蚁
	void Init()
	{
		//初始化环境信息素
		for (int i = 0; i < CITY_NUM; i++)
		{
			for (int j = 0; j < CITY_NUM; j++)
			{
				info[i][j] = ANT_NUM * 15 / tanXindis;
			}
		}
	}

	void Updateinfo()
	{
		//puts("update info");
		double tmpinfo[CITY_NUM][CITY_NUM];
		memset(tmpinfo, 0, sizeof(tmpinfo));
		int m = 0;
		int n = 0;
		//遍历每只蚂蚁
		for (int i = 0; i < ANT_NUM; i++) {
			//puts("");
			for (int j = 1; j < CITY_NUM; j++)
			{
				m = ants[i].Path[j];
				n = ants[i].Path[j - 1];
				//printf("%d %d\n", m, n);
				tmpinfo[n][m] = tmpinfo[n][m] + 3 * ANT_NUM / ants[i].length;
				tmpinfo[m][n] = tmpinfo[n][m];
			}
			//最后城市和开始城市之间的信息素
			n = ants[i].Path[0];
			tmpinfo[n][m] = tmpinfo[n][m] + 3 * ANT_NUM / ants[i].length;
			tmpinfo[m][n] = tmpinfo[n][m];
		}

		//更新环境信息素
		for (int i = 0; i < CITY_NUM; i++)
		{
			for (int j = 0; j < CITY_NUM; j++) {
				//最新的环境信息素 = 留存的信息素 + 新留下的信息素
				info[i][j] = info[i][j] * 0.5 + tmpinfo[i][j];

			}
		}
	}
	//寻找路径，迭代TMAC次
	void Search()
	{

		for (int i = 0; i < TNUM; i++) {
			for (int j = 0; j < ANT_NUM; j++) {
				ants[j].Search();
			}
			//更新环境信息素
			Updateinfo();
		}
		bestSuperAnt.length = 1 << 21;
		// 从起点出发多只蚂蚁
		for (int j = 0; j < TNUM; j++) {
			for (int i = 0; i < ANT_NUM; i++) {
				SuperAnts[i].Search();
				if (SuperAnts[i].length < bestSuperAnt.length) {
					bestSuperAnt = SuperAnts[i];
				}
			}

		}
		for (int i = 0; i < CITY_NUM; i++) {
			if (i) cout << "->";
			cout << bestSuperAnt.Path[i];
		}
		cout << endl;
		cout << "距离为 : ";
		cout << bestSuperAnt.length << endl;
	}
};



// 贪心法的语句
double TanXin(int from, int* visit, double sum, int* shunXv, int pointNum) {
	int flag = true;
	for (int i = 0; i < NUM; i++) {
		if (visit[i] == 0) {
			flag = false;
			break;
		}
	}

	if (flag) return sum;

	double min = 1000000;
	int to;
	for (int i = 0; i < NUM; i++) {
		if (dis[from][i] < min && visit[i] == 0) {
			min = dis[from][i];
			to = i;
		}
	}
	sum += dis[from][to];
	visit[to] = 1;
	shunXv[pointNum++] = to;
	return TanXin(to, visit, sum, shunXv, pointNum);
}

double qiujv(int x1, int y1, int x2, int y2) {
	return sqrt((double)(x1 - x2)*(x1 - x2) + (double)(y1 - y2)*(y1 - y2));
}

struct point {
	int x;
	int y;
};

// 主函数
int main() {
	// fanWei 代表范围
	// chuShi 代表起始位置, 即0
	int fanWei;
	int chuShi = 0;
	cout << "请输入范围 : ";
	cin >> fanWei;
	point point[NUM];
	for (int i = 0; i < NUM; i++) {
		point[i].x = random(fanWei);
		point[i].y = random(fanWei);
	}
	for (int i = 0; i < NUM; i++) {
		for (int j = 0; j < NUM; j++) {
			dis[i][j] = qiujv(point[i].x, point[i].y, point[j].x, point[j].y);
		}
	}
	double min = 100000; // 最小值
	int to; //要去的
	double sum = 0; //总数
	int shunXv[NUM] = { 0 }; // 顺序
	int visit[NUM] = { 0 }; // 储存访问过的点
	for (int i = 1; i < NUM; i++) {
		if (dis[0][i] < min) {
			min = dis[0][i];
			to = i;
		}
	}
	sum += dis[0][to];
	shunXv[1] = to;
	visit[0] = 1;
	visit[to] = 1;
	tanXindis = TanXin(to, visit, sum, shunXv, 2);
	cout << endl;
	cout << "*********** 贪心的结果 **********" << endl;
	for (int i = 0; i < NUM; i++) {
		if (i) cout << "->";
		cout << shunXv[i];
	}
	cout << endl;
	cout << "距离为 : " << tanXindis << endl;
	cout << endl;
	cout << "*********** 蚁群的结果 **********" << endl;
	TSP tsp;
	tsp.Init();
	tsp.Search();
	return 0;
}
瞎搞
算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！

WSL 下 vim 的系统间复制 上一篇
poj-2253 poj-1797 最短路变形 下一篇