蚁群算法求解迷宫最优路径问题

本段程序的基本思想是利用蚁群算法中的蚁周模型，来对全局的迷宫图进行信息素的跟新

和为每一仅仅蚂蚁选择下一个方格。 一共会进行RcMax = 2000轮模拟（理论上模拟的次数越多结果

会越接近真实值）。而在每一轮中会排除 M = 10仅仅蚂蚁进行探路。同一时候在算法的回溯思想上採用的

是栈的数据结构来实现的。当栈终于为空时则表示无解。但同一时候这段程序的一缺点就是：因为我没在

算法中对每一轮的每仅仅探路蚂蚁採用多线程的模式，所以总体的执行效率还不是非常高。

如读者有好的

思想或建议，请留言。

#include
#include
#include
using namespace std;
//坐标类
struct Point
{
	int x;
	int y;
};
//地图类
template
class Map
{
public:
	int (*p)[B];//1表示为障碍方格。0表示该方格可通
	bitset<4> (*around)[B];//记录每个方格四周四个方法的可选标记
	int row;//行数
	int col;//列数
	Map()
	{
		p =new int[A][B];
		around = new bitset<4>[A][B];
	}
	Map(Map & B1)
	{
	 p =new int[A][B];
	 around = new bitset<4>[A][B];
	 row = B1.row;
	 col = B1.col;
	 for(int i = 0;i & operator=(Map & B1)
	{
	 row = B1.row;
	 col = B1.col;
	 for(int i = 0;ip[i][j] = B1.p[i][j];
			 around[i][j] = B1.around[i][j];
		 }
	 }
	 return *this;
	}
};

//start起始点， end终止点
template
bool FindPath(Map & map,Point & start,Point & end)
{
	const int N1 =  A;
	const int N2 =  B;
	
	const int M = 10;//每一轮中蚂蚁的个数
	const int RcMax = 2000;//迭代次数
	const int IN = 1;//信息素的初始量

	double add[N1][N2];//每一段的信息素增量数组
	double phe[N1][N2];//每一段路径上的信息素
	double MAX = 0x7fffffff;

	double alphe,betra,rout,Q;//alphe信息素的影响因子，betra路线距离的影响因子，rout信息素的保持度，Q用于计算每仅仅蚂蚁在其路迹留下的信息素增量
	double bestSolution = MAX;//最短距离
	stack Beststackpath;//最优路线

	//初始化变量參数和信息数组
	alphe = betra = 2;
	rout = 0.7;
	Q = 10;

	//先给图的外围加上障碍
	for(int i = 0;i stackpath[M];
	//拷贝障碍地图
	Map Ini_map[M];
	//记录每一仅仅蚂蚁的当前位置
	Point Allposition[M];

	int s = 0;
	while(s=drand)
			  {
			  break;
			  }
			 }
		  }

		   //入栈
		   Allposition[j].x = x;
		   Allposition[j].y = y;
		   stackpath[j].push(Allposition[j]);
		   //设置障碍
		   Ini_map[j].p[Allposition[j].x][Allposition[j].y] = 1;

		  }
		  else//没找到了下一点
		  {   
			  //向后退一步，出栈
			  stackpath[j].pop();
			  //消除入栈时设置的障碍
			  Ini_map[j].p[Allposition[j].x][Allposition[j].y] = 0;
			  if(stackpath[j].empty())
			  {
				  return false;
			  }
			  //设置回溯后的Allposition
			  if(Allposition[j].x == stackpath[j].top().x)
			  {
				  if((Allposition[j].y - stackpath[j].top().y)==1)//向右
				  {
					  (Ini_map[j].around[ stackpath[j].top().x][stackpath[j].top().y])[0] = 1;//标记该方向已訪问
				  }
				  if((Allposition[j].y - stackpath[j].top().y)==-1)//向左
				  {
					  (Ini_map[j].around[ stackpath[j].top().x][stackpath[j].top().y])[2] = 1;//标记该方向已訪问
				  }
			  }
			  if(Allposition[j].y == stackpath[j].top().y)
			  {
			  
				  if((Allposition[j].x - stackpath[j].top().x)==1)//向下
				  {
					  (Ini_map[j].around[ stackpath[j].top().x][stackpath[j].top().y])[1] = 1;//标记该方向已訪问
				  }
				   if((Allposition[j].x - stackpath[j].top().x)==-1)//向上
				  {
					  (Ini_map[j].around[ stackpath[j].top().x][stackpath[j].top().y])[3] = 1;//标记该方向已訪问
				  }
			  }
			  Allposition[j].x = stackpath[j].top().x;
			  Allposition[j].y = stackpath[j].top().y;
		  }

	 }
	 }
	
	//保存最优路线
	double solution = 0;
	for(int i = 0;i20)
		{
			phe[i][j] = 20;
		}
	 }
	}

	s++;
	}//轮

	//找到路径，并输出stackpath
	cout<<"找到最优路径！"<"< map;
	map.col = map.row = 10;
	int p[10][10];
	for(int i =0;i<10;i++)//初始化迷宫
	{
	 for(int j=0;j<10;j++)
	 {
		 p[i][j] = 0;
	 }
	}
	//为迷宫设置障碍
	p[1][3] = 1;p[1][7] = 1;p[2][3] = 1;p[2][7] = 1;
	p[3][5] = 1;p[3][6] = 0;p[4][2] = 1;p[4][3] = 1;
	p[4][4] = 1;p[5][4] = 1;p[6][2] = 1;p[6][6] = 1;
	p[7][2] = 1;p[7][3] = 1;p[7][4] = 1;p[7][6] = 1;
	p[8][1] = 1;
	map.p = p ;
	Point start,end;
	start.x = start.y = 1;
	end.x =8,end.y = 8;
	if(!FindPath<10,10>(map,start,end))
	{
	  cout<<"该迷宫无解！"<