/// <summary>城市数量,N</summary>

 public Int32 NCity { get; set; }

 /// <summary>蚂蚁数量,M</summary>

 public Int32 AntCount { get; set; }

 /// <summary>信息启发式因子a,表征信息素重要程度的参数</summary>

 public Double Alpha { get; set; }

 /// <summary>期望启发式因子b,表征启发式因子重要程度的参数</summary>

 public Double Beta { get; set; }

 /// <summary>信息素蒸发的参数p</summary>

 public Double Rho { get; set; }

 /// <summary>距离数据，不一定是对称矩阵,D=d(ij)</summary>

 public Double[,] Distance { get; set; }

 /// <summary>最大迭代次数NC</summary>

 public Int32 NcMax { get; set; }

 /// <summary>最好的解个数，取最优解列表中个数的数目，可以作为备用方案</summary>

 public Int32 BetterPlanCount { get; set; }

 private List<Ant> planList;

 /// <summary>信息素浓度</summary>

 public double[,] InfoT { get; set; }

 /// <summary>构造函数</summary>

 /// <param name="m">蚂蚁数量</param>

 /// <param name="a">信息启发式因子</param>

 /// <param name="b">期望启发式因子</param>

 /// <param name="p">信息素蒸发的参数</param>

 /// <param name="distance">距离数据</param>

 /// <param name="NCMax">最大迭代次数</param>

 /// <param name="planCount">最优解的个数</param>

 public BaseTspAntSystem(double[,]distance,Int32 m,double a,double b,double p,int NCMax,int planCount=)

 {

     this.AntCount = m;

     this.Alpha = a;

     this.Beta = b;

     this.Rho = p;

     this.Distance = distance;

     this.NcMax = NCMax;

     this.BetterPlanCount = planCount;

     planList = new List<Ant>();

     NCity = Distance.GetLength();//所有的城市个数

     InfoT = new double[NCity, NCity];//初始化信息素矩阵

 }

 public void TspSolution()

 {

     #region 初始化计算

     //计算初始信息素的值，可直接指定，或者贪婪算法计算

     double Cnn = GreedyAlgorithm();

     double t0 = (double)AntCount / Cnn;//信息素初始化

     for (int i = ; i < NCity; i++)

     {

         for (int j = ; j < NCity; j++)

         {

             //每条可行的路径的信息素初始值

             if (Distance[i, j] != ) InfoT[i, j] = t0;

         }

     }

     //为每个蚂蚁随机选择出发城市,List的长度为蚂蚁个数，内部List长度为路径

     List<Int32> allNodes = new List<int>();

     for (int i = ; i < NCity; i++) allNodes.Add(i);//所有路径节点

     //迭代次数

     Int32 NC = ;

     #endregion

     while (NC<NcMax)

     {

         //生成蚂蚁及初始访问城市，并设置对应禁忌表和路径列表

         List<Ant> antList = new List<Ant>();

         for (int i = ; i < AntCount; i++)

             antList.Add(new Ant(i, allNodes.DeepCopy(), false));

         //所有蚂蚁依次寻找下一个节点，直到本轮完成

         antList.ForEach(n => n.NextCityUntilFinished(InfoT,Distance,Alpha,Beta,Rho));

         //统计最优解

         planList.AddRange(antList);//先添加

         planList = planList.OrderBy(n => n.CpathLength).ToList();//排序

         //取出前面指定的几条最短路径

         if (planList.Count > BetterPlanCount)

             planList.RemoveRange(BetterPlanCount, planList.Count - BetterPlanCount);

         NC++;

         //更新信息素的值：循环所有路径，依次进行添加

         //先挥发

         for (int i = ; i < NCity; i++) //挥发过程

         {

             for (int j = ; j < NCity; j++) InfoT[i, j] *= (1.0 - Rho);

         }

         //再增强,循环所有蚂蚁

         foreach (var item in antList)

         {

             var temp =  1.0 / item.CpathLength;

             foreach (var edge in item.Edge) InfoT[edge.Key, edge.Value] += temp;

         }

     }

 }

 public class Ant

 {

     #region 属性

     /// <summary>蚂蚁编号</summary>

     public Int32 Id { get; set; }

     /// <summary>当前蚂蚁已经走过的路径节点列表，也就是禁忌表

     /// 最后1个就是当前所处的位置

     /// </summary>

     public List<Int32> PathNodes { get; set; }

     /// <summary>当前蚂蚁下一步可供选择的节点列表</summary>

     public List<Int32> selectNodes { get; set; }

     /// <summary>该蚂蚁旅行的总长度</summary>

     public Double CpathLength { get; set; }

     /// <summary>当前蚂蚁走过的边，key为起点,value为终点</summary>

     public Dictionary<int, int> Edge;

     private Random rand;

     int N;

     #endregion

     #region 构造函数

     /// <summary>构造函数</summary>

     /// <param name="id">蚂蚁编号</param>

     /// <param name="allNodes">所有节点名称列表</param>

     /// <param name="isFixStart">是否固定起点</param>

     public Ant(Int32 id,List<Int32> allNodes,Boolean isFixStart)

     {

         this.Id = id;

         this.selectNodes = allNodes;

         this.PathNodes = new List<int> ();

         //isFixStart为false给蚂蚁随机1个起点，否则都为0

         if (isFixStart)

         {

             this.PathNodes.Add();

             this.selectNodes.RemoveAt();

         }

         else

         {

             var temp = new Random().Next(, allNodes.Count - );

             this.PathNodes.Add(temp);

             this.selectNodes.RemoveAt(temp);

         }

         this.CpathLength = ;

         rand = new Random();

     }

     #endregion

 }

 #region 蚂蚁行为-依次按概率选择下一个城市，直到走完

 public void NextCityUntilFinished(double[,] info,double[,] distance,double a,double b,double p)

 {

     N = distance.GetLength();

     Edge = new Dictionary<int, int>();//经过的边：起点-终点

     //为空，就不需要计算了

     while(selectNodes.Count >)

     {

         double sumt = ;//分母的和值

         Int32 current = PathNodes.Last();

         //依次计算当前点到其他点可选择点的 值

         Dictionary<Int32, double> dic = new Dictionary<int, double>();

         foreach (var item in selectNodes)

         {

             var temp = Math.Pow(info[current, item], a) * Math.Pow(1.0 / distance[current, item], b);

             sumt += temp;

             dic.Add(item, temp);

         }

         //计算各个点的概率

         var ratio = dic.ToDictionary(n => n.Key, n => n.Value / sumt);

         //产生1个随机数，并按概率确定下一个城市

         Int32 nextCity = GetNextCityByRandValue(ratio, rand.NextDouble());

         //修改列表

         this.PathNodes.Add(nextCity);

         this.selectNodes.Remove(nextCity);

         this.CpathLength += distance[current, nextCity];

         Edge.Add(current, nextCity);//信息素增强辅助计算

     }

     //最后1条路径的问题，额外增加，直接 回原点

     this.CpathLength += distance[PathNodes.Last(), PathNodes.First()];

     Edge.Add(PathNodes.Last(), PathNodes.First());

     this.PathNodes.Add(PathNodes.First());//最后才添加

 }

 /// <summary>按照dic中按照顺序的节点的概率值，和随机数rnd的值，确定哪一个为下一个城市</summary>

 /// <param name="dic"></param>

 /// <param name="rnd"></param>

 /// <returns></returns>

 int GetNextCityByRandValue(Dictionary<Int32,double> dic,double rnd)

 {

     double sum = ;

     foreach (var item in dic)

     {

         sum += item.Value;

         if (rnd < sum) return item.Key;

         else continue;

     }

     throw new Exception("无法选择城市");

 }

 #endregion