MyException - 我的异常网
当前位置:我的异常网» C语言 » 原创:TSP有关问题解决方案-禁忌搜索算法C实现

原创:TSP有关问题解决方案-禁忌搜索算法C实现

www.MyException.Cn  网友分享于:2013-10-16  浏览:0次
原创:TSP问题解决方案-----禁忌搜索算法C实现
本文着重于算法的实现,对于理论部分可自行查看有关资料可以简略参考该博文:http://blog.csdn.net/u013007900/article/details/50379135
本文代码部分基于C实现,源码如下:
  1 /*****************************************************************************
  2 **    Copyright: NEW NEU laboratory
  3 **    File name: CTSP
  4 **    Description:禁忌搜索算法解决TSP问题
  5 **    Author: 1702-GCJ
  6 **    Version: 1.1  
  7 **    Date: 2017/10/3
  8 **    History: 无 
  9 ** Modification: IsFindTabu(Queue * Q,const Tabu *item) 
 10 *****************************************************************************/
 11 
 12 #include"stdio.h"
 13 #include"stdlib.h"
 14 #include"string.h"
 15 #include "time.h"
 16  
 17 #define CityNum         31       //城市的数量 
 18 #define TabuLength     21     //禁忌表长度(根号下的 种类)
 19 #define Neighbor        400     //邻居个数 
 20 #define MaxNG            400    //迭代次数    
 21 
 22 int currentNG = 0;             //当前迭代次数
 23 int DesireLevel = 0;            //渴望水平 (即最短距离) 
 24 
 25 typedef int ElementType;
 26 ElementType **Distance;        //存储各个城市之间的距离矩阵的指针 数据都是取整的 
 27 
 28 /***************************************************************************************读取数据区******************************************/
 29  
 30 /*************************************************
 31 **Function: MemBlockCity
 32 **Description: 申请存储城市距离空间 
 33 **Calls: 无
 34 **Called By: ReadDataTxt()
 35 **Input: 无
 36 **Output: 无 
 37 **Return: 指向存储城市距离空间的指针 
 38 **Others: 用完需要释放掉相应内存 
 39 *************************************************/
 40 ElementType ** MemBlockCity();
 41 
 42 /*************************************************
 43 **Function: PrintCityDistance
 44 **Description: 显示Distance信息
 45 **Calls: 无
 46 **Called By: main()
 47 **Input: Distance 全局变量的指针  
 48 **Output: 无 
 49 **Return: void 
 50 **Others: 无
 51 *************************************************/
 52 void PrintCityDistance( ElementType **  distance);
 53 
 54 /*************************************************
 55 **Function: ReadDataTxt
 56 **Description: 从txt文档中读取数据
 57 **Calls: MemBlockCity() 
 58 **Called By: main
 59 **Input: 无
 60 **Output: 无 
 61 **Return: void 
 62 **Others: 里面直接用的全局变量 指针Distance 
 63 *************************************************/
 64 void ReadDataTxt();
 65 
 66 /*************************************************
 67 **Function: WriteDataTxt
 68 **Description: 将Distance全局数组数据写到txt文档中去  
 69 **Calls: 无
 70 **Called By: main()
 71 **Input: 无
 72 **Output: 无 
 73 **Return: void 
 74 **Others: 里面用到了宏值CityNum值 
 75 *************************************************/
 76 void WriteDataTxt();
 77 /**********************************************************************************禁忌表操作区*******************************************/
 78 typedef struct _Tabu{
 79     int smallNum;
 80     int bigNum;    //存储数量大的元素 
 81 }Tabu; //禁忌表结构 
 82 
 83 typedef struct _Queue{
 84     Tabu *tabuList;//队列空间指针 
 85     int rear;        //指向尾部 
 86     int front;        //指向队列的头部 
 87     int maxSize;    //记录队列的最大个数 
 88     int count;        //记录资源个数 判断队列空满 
 89     int tabuIndex;    //在禁忌表中找到禁忌元素时 存储该值在禁忌表中的位置 
 90 }Queue;//循环队列的形式 
 91 
 92 /*************************************************
 93 **Function: CreateQueue
 94 **Description: malloc一个禁忌表队列并初始化 
 95 **Calls: 无
 96 **Called By: main()
 97 **Input: tabuLength 禁忌表数据长度 
 98 **Output: 无 
 99 **Return: Queue * 队列变量 
100 **Others: 里面用到了宏值CityNum值 ,用完需要释放掉相应内存 
101 *************************************************/
102 Queue * CreateQueue(int tabuLength);
103 
104 /*************************************************
105 **Function: UpdateTabu
106 **Description: 更新禁忌表 
107 **Calls: IsFindTabu() 
108 **Called By: TSP()
109 **Input: Q 禁忌表队列 item 加入禁忌表的Tabu结构的变量 
110 **Output: 无 
111 **Return: void 
112 **Others:  
113 *************************************************/
114 void UpdateTabu(Queue *Q,Tabu *item);
115 
116 /*************************************************
117 **Function: IsFindTabu
118 **Description: 禁忌表中是否找到这个元素  
119 **Calls: 无  
120 **Called By: UpdateTabu() TSP()
121 **Input: Q 禁忌表队列 item 判断其是否在禁忌表中的Tabu结构的变量的指针 
122 **Output: 无 
123 **Return: 0 没有找到这个元素 1 找到这个元素了 
124 **Others:  
125 *************************************************/
126 static int IsFindTabu(Queue * Q,const Tabu *item);
127 
128 /****************************************************************************2Opt邻域+TSp核心算法*********************************************/
129 //定义解的存储类型 向量形式 
130 typedef struct _Solve{
131     ElementType *initSolution;            //初始解 
132     ElementType *currentSolution;        //当前解 
133     ElementType * optimalSolution;    //最优解 
134     ElementType *tempSolution;            //临时解   
135     ElementType lastdistance;             //上次记录的总距离 
136     ElementType  initdistance;            //定义初始距离 
137 }StrSolve;
138 typedef struct _MotionTable{
139     Tabu  tabu;                                //存储改变的元素 
140     ElementType changedistance;        //改变的距离 
141 }MotionTable;//记录2opt邻域移动信息 
142 
143 StrSolve * SolutionSpace ;             //解空间(包含当前解和初始解)指针 
144 MotionTable *motionTable;                //移动元素信息 (一个表格) 
145 
146 /*************************************************
147 **Function: CreateMotionStruct
148 **Description: 创建并初始化2-Opt 移动信息表格   
149 **Calls: 无  
150 **Called By:  Init2Opt()
151 **Input: neighbor  邻居数量 
152 **Output: 无 
153 **Return: MotionTable *指针变量 
154 **Others: 不用这块内存的时候要释放掉 ! 
155 *************************************************/
156 MotionTable* CreateMotionStruct(int neighbor);
157 
158 /*************************************************
159 **Function: CreateSolutionSpace
160 **Description: 创建并初始化解空间
161 **Calls: 无  
162 **Called By:  Init2Opt()
163 **Input: cityNum  城市数量 
164 **Output: 无 
165 **Return: StrSolve  *指针变量 
166 **Others: 不用这块内存的时候要逐一释放掉 ! 
167 *************************************************/
168 StrSolve *CreateSolutionSpace(int cityNum);
169 
170 /*************************************************
171 **Function: GetInitSolution
172 **Description: 获得初始解
173 **Calls: 无  
174 **Called By:  Init2Opt()
175 **Input: StrSolve * 指针变量 
176 **Output: 无 
177 **Return: StrSolve  *指针变量 
178 **Others: 这里在初始化解的时候可以用其他元启发式算法得出一个较好的解  ! 
179 *************************************************/ 
180 void GetInitSolution(StrSolve * strSolve);
181 
182 /*************************************************
183 **Function: Init2Opt
184 **Description: 初始化TSP需要用的值 
185 **Calls: CreateMotionStruct()  CreateSolutionSpace()  GetInitSolution()
186 **Called By:  main
187 **Input: 无 
188 **Output: 无 
189 **Return: void
190 **Others: 这里在初始化解的时候可以用其他元启发式算法得出一个较好的解  ! 不知道为什么只能在Main函数中调用否则 会出现段错误 
191 *************************************************/ 
192 void Init2Opt();
193 
194 /*************************************************
195 **Function: FindPosition
196 **Description: 在数组中找到指定元素值的位置 
197 **Calls: 
198 **Called By:  Get2OptChangeDistance()  TSP()
199 **Input: solution 一维数组指针  tabu  Tabu结构指针 
200 **Output: 无 
201 **Return: void
202 **Others: 这里是从solution[1]开始查找到的! 
203 *************************************************/ 
204 static void FindPosition(const ElementType * solution,Tabu *tabu);
205 
206 /*************************************************
207 **Function: FindPosition
208 **Description: 获得2邻域变化值 
209 **Calls: FindPosition()
210 **Called By:  Get2optSolution()
211 **Input:  tabu  Tabu结构指针  solution 一维数组指针 
212 **Output: 无 
213 **Return: ElementType 2邻域城市变化值 
214 **Others: 返回的值越小越好 ! 
215 *************************************************/
216 static ElementType Get2OptChangeDistance(Tabu * tabu,const ElementType * solution);
217 
218 /*************************************************
219 **Function: Get2optSolution
220 **Description: 得到1个2邻域解 将移动元素,及其导致路径的变化值 存储到移动表中 
221 **Calls: Get2OptChangeDistance()
222 **Called By:  TSP()
223 **Input:  strSolve 解空间指针  motiontable 移动表指针 
224 **Output: 无 
225 **Return: void 
226 **Others: 随机数要注意! 
227 *************************************************/
228 void Get2optSolution(const StrSolve * strSolve,MotionTable *motiontable );
229 
230 /*************************************************
231 **Function: Insert_Sort
232 **Description: 按从小到大排序 插入排序 将制定的类数组变量 的内容进行排序 
233 **Calls: 无
234 **Called By:  FindBestMotionValue()
235 **Input:    motiontable 移动表指针  n为类数组 元素个数 
236 **Output: 无 
237 **Return: void 
238 **Others: 
239 *************************************************/
240 void Insert_Sort (MotionTable * motiontable,int n);
241 
242 /*************************************************
243 **Function: FindBestMotionValue
244 **Description: 找到移动表中最小的值 即为最优值 
245 **Calls: Insert_Sort()
246 **Called By:  TSP()
247 **Input:    motiontable 移动表指针  
248 **Output: 无 
249 **Return: MotionTable *型的指针 存储移动表中最好值的表格指针 
250 **Others: 
251 *************************************************/
252 MotionTable * FindBestMotionValue( MotionTable * motiontable);
253  
254 /*************************************************
255 **Function: GetInitLevel
256 **Description: 获取初始解的渴望水平 
257 **Calls: 
258 **Called By:  TSP()
259 **Input:    distance 存储城市的矩阵指针 initSolution 初始解指针  
260 **Output: 无 
261 **Return: 初始解的渴望水平 
262 **Others: 
263 *************************************************/
264 int GetInitLevel( ElementType **distance,ElementType * initSolution);
265 
266 /*************************************************
267 **Function: TSP
268 **Description: TSP核心算法 
269 **Calls: GetInitLevel() 
270 **Called By:  TSP()  Get2optSolution()  FindBestMotionValue()  UpdateTabu()  FindPosition()  memcpy()
271 **Input:    distance 存储城市的矩阵指针 solutionSpace 解空间指针 motiontable 移动表 desireLevel 渴望水平 queue 禁忌表队列指针  
272 **Output: 最优解信息 
273 **Return: void  
274 **Others: 
275 *************************************************/
276 void TSP(  ElementType **distance, StrSolve * solutionSpace ,MotionTable *motiontable,int *desireLevel,Queue *queue);
277 
278 /*************************************************
279 **Function: MemFree
280 **Description: 释放申请的动态内存 
281 **Calls: free() 
282 **Called By:  main()
283 **Input: distance 存储城市距离的变量指针  queue 禁忌表队列  motiontable 移动表的指针  strSolve  解空间的指针 
284 **Output: 无 
285 **Return: void
286 **Others: 这里也可以一步一步的释放掉 各自的指针 因为就用一个.c所以释放内存的操作都在这里进行 
287 *************************************************/  
288 void MemFree(ElementType ** distance,Queue *queue,MotionTable *motiontable,StrSolve *strSolve);
289 
290 
291 /*******************************************************************************MAIN函数*************************************/
292 int main(int argc,char *argv[])
293 {
294 //    Tabu item;
295     clock_t start, finish;
296     double  duration;
297     Queue * queue = CreateQueue(TabuLength); //创建一个禁忌表队列 本身就初始化好了 
298     Init2Opt();//初始化相关 
299     // 设置随机数种子 为以后使用rand()做准备 
300    srand((unsigned int)time(0));
301     
302     start = clock();
303     ReadDataTxt(Distance);//必须放在前面  读取数据后 才能操作 
304 //    PrintCityDistance(Distance); //显示二维数组的数据 只显示5X5 
305 // WriteDataTxt(Distance);//将distance 数据写入txt 
306     TSP( Distance,SolutionSpace ,motionTable,&DesireLevel,queue);    
307     
308 ////    //将得到的最优解 从新用TSP算法算 
309 //    memcpy( SolutionSpace->initSolution,SolutionSpace->optimalSolution,sizeof(ElementType)*CityNum ); //将临时解空间值复制到当前解空间 
310 //    printf("\n新初始解的渴望水平:%d  \n",GetInitLevel(Distance,SolutionSpace->optimalSolution));
311 //    TSP( Distance,SolutionSpace ,motionTable,&DesireLevel,queue);
312 //    
313     finish = clock();
314     duration = (double)(finish - start) / CLOCKS_PER_SEC;
315     printf("\n           TSP算法运行时间:%.4f秒       \n",duration);
316     MemFree(Distance, queue,motionTable,SolutionSpace);
317    return 0;  
318 } 
319 
320 
321 /************************************************************************读取数据区***********************************************/ 
322 
323 /*************************************************
324 **Function: MemBlockCity
325 **Description: 申请存储城市距离空间 
326 **Calls: 无
327 **Called By: ReadDataTxt() 在txt文档中读取数据 
328 **Input: 无
329 **Output: 无 
330 **Return: 指向存储城市距离空间的指针 
331 **Others: 无
332 *************************************************/
333 ElementType ** MemBlockCity()
334 {
335     ElementType ** Distance; 
336     int i=0;
337     
338     //动态申请一块内存存储城市之间的数据
339     Distance = (ElementType **)malloc(sizeof(ElementType *)*CityNum);
340     for(i = 0;i< CityNum ; i++){
341         Distance[i] = (ElementType *)malloc(sizeof (ElementType )* CityNum);
342     }
343     return Distance;
344 }
345 
346 /*************************************************
347 **Function: PrintCityDistance
348 **Description: 显示Distance信息 这里仅仅显示了CityNum-25个元素 因为屏幕显示不开 
349 **Calls: 无
350 **Called By: main()
351 **Input: Distance 全局变量的指针  
352 **Output: 无 
353 **Return: void 
354 **Others: 无
355 *************************************************/
356 void PrintCityDistance( ElementType **  distance)
357 {
358     int i,j;
359     for(i = 0; i< CityNum-25;i++){
360         for(j = 0;j<CityNum-25;j++)
361             printf("%d ",distance[i][j]);
362         printf("\n");
363     }
364 }
365 
366 /*************************************************
367 **Function: ReadDataTxt
368 **Description: 从txt文档中读取数据
369 **Calls: MemBlockCity() 
370 **Called By: main()
371 **Input: 无
372 **Output: 无 
373 **Return: void 
374 **Others: 里面直接用的全局变量 指针Distance 
375 *************************************************/
376 void ReadDataTxt()
377 {
378     //     FILE *fpRead=fopen("F:\\GCJ\\Desktop\\智能优化方法作业\\data.txt","r"); 
379     FILE *fpRead=fopen("data.txt","r");  //从data.txt中读取数据 
380     int i,j;
381     if(fpRead==NULL){  
382           printf("open file data.txt failed!\n");
383        exit(1);
384     }
385     Distance = MemBlockCity();    //申请一块存储城市数量空间         
386     for(i=0;i<CityNum;i++){
387         Distance[i][i] = 0;
388         for(j=i+1 ;j < CityNum;j++ ){
389             fscanf(fpRead,"%d",&Distance[i][j]);//自动读取数据 只要自己能够控制好存储位置即可 
390             Distance[j][i] = Distance[i][j];  
391         }
392     } 
393     fclose(fpRead);
394 }
395 
396 /*************************************************
397 **Function: WriteDataTxt
398 **Description: 将Distance全局数组数据写到txt文档中去 
399 **Calls: 无
400 **Called By: main()
401 **Input: 无
402 **Output: 无 
403 **Return: void 
404 **Others: 里面用到了宏值CityNum值 
405 *************************************************/
406 void WriteDataTxt(ElementType **distance)
407 {
408     FILE *fpWrite;
409     int i,j;
410     fpWrite=fopen("F:\\GCJ\\Desktop\\智能优化方法作业\\data.txt","w");  //从data.txt中写数据 
411     for(i = 0;i< CityNum;i++){
412         for(j=0;j<CityNum;j++)
413             fprintf(fpWrite,"%d ",distance[i][j]);//这里%d后面必须要有空格 否则 直接输出连续的数字 
414             fprintf(fpWrite,"\n");
415     }
416     fclose(fpWrite);
417 }
418 
419 /**************************************************************禁忌表操作区*****************************************************/
420 
421 /*************************************************
422 **Function: CreateQueue
423 **Description: malloc一个禁忌表队列并初始化 
424 **Calls: 无
425 **Called By: main()
426 **Input: tabuLength 禁忌表数据长度 
427 **Output: 无 
428 **Return: Queue * 队列变量 
429 **Others: 里面用到了宏值CityNum值 
430 *************************************************/
431 Queue * CreateQueue(int tabuLength)
432 {
433     Queue * queue = (Queue *)malloc(sizeof(struct _Queue));//申请一块队列变量
434     //queue->tabuList =(ElementType *)malloc(sizeof(ElementType)*MaxSize);//申请一块数组空间 
435     queue->tabuList =(Tabu *)malloc(sizeof(Tabu)*tabuLength);//21的长度 
436     queue->front = 0;
437     queue->rear = 0;//头尾 都为0 
438     queue->maxSize = tabuLength;
439     queue->count =0;
440     queue->tabuList[0].smallNum = 0;
441     queue->tabuList[0].bigNum  = 0;
442     return queue;
443 } 
444 
445 /*************************************************
446 **Function: IsFindTabu
447 **Description: 禁忌表中是否找到这个元素  
448 **Calls: 无  
449 **Called By: UpdateTabu() TSP()
450 **Input: Q 禁忌表队列 item 判断其是否在禁忌表中的Tabu结构的变量的指针 
451 **Output: 无 
452 **Return: 0 没有找到这个元素 1 找到这个元素了 
453 **Others:  
454 *************************************************/
455 static int IsFindTabu(Queue * Q,const Tabu *item)
456 {
457     Tabu tabu;
458     int i; 
459     int IsFindFlag = 0 ; 
460     
461     //将要禁忌的值按顺序放在中间变量中 方便加入到禁忌表中 
462     if( (*item).bigNum >= (*item).smallNum ){
463         tabu.bigNum = (*item).bigNum;
464         tabu.smallNum = (*item).smallNum;
465     }    
466     else{
467         tabu.bigNum = (*item).smallNum;
468         tabu.smallNum = (*item).bigNum;
469     } 
470     
471     //查找禁忌表中是否有这个禁忌元素  没有的话 插入元素在头部 否则把这个元素加上惩罚政策加入到禁忌表的头部 其他依次降序    
472     for(i = Q->front; (i%TabuLength)!= Q->rear; ){//这个查找函数有问题了 因为循环队列的话 队列慢点话 rear = front  如何解决? 
473         if( (tabu.smallNum == Q->tabuList[i].smallNum ) && ( tabu.bigNum == Q->tabuList[i].bigNum )  ){ 
474         //说明在禁忌表中找到这个元素了 那么就惩罚这个 放在最前面 
475         //把第一个元素放入 这个值 剩下的依次 递减排列 
476 //            printf("在禁忌表中找到了%d %d\n",tabu.bigNum,tabu.smallNum);
477 
478             //新加     记录位置 
479             Q->tabuIndex = i; 
480             
481             IsFindFlag  = 1;
482             return IsFindFlag ;    //表示不管了 
483         }    
484         if(++i >= TabuLength)//仅仅让i 在 0 - Tabulength范围内遍历 
485             i = 0;
486     }
487     if( Q->count >= TabuLength ){//说明禁忌表满 那么rear值就需要访问了  否则不需要访问 
488         if( i%TabuLength == Q->rear )//因为循环队列寻找的时候 最后一个元素 无法通过for循环遍历到 
489         if( (tabu.smallNum == Q->tabuList[i].smallNum ) && ( tabu.bigNum == Q->tabuList[i].bigNum )  ){ 
490 //            printf("找到了最新的了%d %d\n",tabu.smallNum,tabu.bigNum);    
491             
492             //新加     记录位置 
493             Q->tabuIndex = Q->rear; 
494             
495             IsFindFlag  = 1;
496             return IsFindFlag ;    //表示不管了 
497         }
498     }
499     
500         return IsFindFlag;//之前这里就忘了加了 注意这点    !! 
501 }
502 
503 /*************************************************
504 **Function: UpdateTabu
505 **Description: 更新禁忌表 
506 **Calls: IsFindTabu()  
507 **Called By: TSP()
508 **Input: Q 禁忌表队列 item 加入禁忌表的Tabu结构的变量的指针 
509 **Output: 无 
510 **Return: void 
511 **Others:  
512 *************************************************/
513 void UpdateTabu(Queue *Q,Tabu *item) 
514 {
515     Tabu tabu;
516     Tabu temptabu;
517     int i; 
518 
519     //将要禁忌的值按顺序放在中间变量中 方便加入到禁忌表中 
520     if( (*item).bigNum >= (*item).smallNum ){
521         tabu.bigNum = (*item).bigNum;
522         tabu.smallNum = (*item).smallNum;
523     }    
524     else{
525         tabu.bigNum = (*item).smallNum;
526         tabu.smallNum = (*item).bigNum;
527     }
528         
529     if( !IsFindTabu(Q,item) ){
530         //如果没有找到  那么直接在队列插入这个元素    
531         if( Q->count < TabuLength ){ //说明队列不满 那就直接插入元素
532             Q->count++ ;//最后满的时候为21个元素 
533             Q->tabuList[Q->rear++] = tabu;//在后面插入 然后从前面取出元素 
534             if( Q->rear >= TabuLength)//到了尾部的话 就直接从前面开始存储  尾部先存储后+1 
535                 --Q->rear ;//说明禁忌表满了的时候 让rear指向最后一个元素即可 
536         } 
537         else{//满了的话 就直接头部删除 尾部加入 //不是真正的删除 仅仅是释放掉这块存储空间 
538             if( ++Q->front >= TabuLength )
539                 Q->front  =0;
540             if( ++Q->rear >= TabuLength)//到了尾部的话 就直接从前面开始存储  尾部先存储后+1 
541                 Q->rear = 0;
542             Q->tabuList[Q->rear]  = tabu;
543         }
544     }
545     else{//在禁忌表中找到这个元素的时候 需要进行惩罚 将这个值放在头部,而该值前面的数依次向后排 
546         int j,k;
547         j = Q->tabuIndex ;    //禁忌表中找到的该值的索引
548         k = Q->front;            //禁忌表头部索引
549         
550         if( Q->tabuIndex >= Q->front  ){
551             
552             //说明禁忌表没有满 或者 禁忌表满了 但是移动仅仅在Q->front  到这个索引即可 
553             for( --j ;j >= k ; --j){
554                 Q->tabuList[j+1] = Q->tabuList[j];
555             }/*for end*/
556                 
557         }
558         else{
559             //禁忌表满了且 Q->front 值大于 Q->tabuIndex 
560             for( ;j == Q->front; --j ){
561                 if( j >= 1)
562                     Q->tabuList[j] =Q->tabuList[j-1]; 
563                 else{ //j == 0
564                      j = TabuLength ;
565                     Q->tabuList[0] = Q->tabuList[j-1];
566                 }
567             }/*for ...end */
568         }
569         //惩罚策略 
570         Q->tabuList[Q->front] = tabu;
571         
572     }/*if find .. else ..end*/
573     
574 }
575 
576 /******************************************************************************************2Opt邻域+TSp核心算法***********************************/
577 
578 /*************************************************
579 **Function: CreateMotionStruct
580 **Description: 创建并初始化2-Opt 移动信息表格   
581 **Calls: 无  
582 **Called By:  Init2Opt()
583 **Input: neighbor  邻居数量 
584 **Output: 无 
585 **Return: MotionTable *指针变量 
586 **Others: 不用这块内存的时候要释放掉 ! 
587 *************************************************/
588 MotionTable* CreateMotionStruct(int neighbor)
589 {
590     int i;
591     MotionTable * motiontable = (MotionTable *)malloc(sizeof(MotionTable)*neighbor );
592     for(i = 0;i< neighbor;i++){
593         motiontable->tabu.smallNum  =0;
594         motiontable->tabu.bigNum = 0;
595         motiontable->changedistance = 0;
596     }
597     return motiontable;
598 } 
599 
600 /*************************************************
601 **Function: CreateSolutionSpace
602 **Description: 创建并初始化解空间
603 **Calls: 无  
604 **Called By:  Init2Opt()
605 **Input: cityNum  城市数量 
606 **Output: 无 
607 **Return: StrSolve  *指针变量 
608 **Others: 不用这块内存的时候要逐一释放掉 ! 
609 *************************************************/
610 StrSolve *CreateSolutionSpace(int cityNum)
611 {
612     int i;
613     StrSolve *strSolve = (StrSolve *)malloc( sizeof(StrSolve) ) ;
614     strSolve->initSolution = ( ElementType *)malloc(sizeof(ElementType)*cityNum );
615     strSolve->currentSolution = ( ElementType *)malloc(sizeof(ElementType)*cityNum );
616     strSolve->optimalSolution = ( ElementType *)malloc(sizeof(ElementType)*cityNum );
617     strSolve->tempSolution = ( ElementType *)malloc(sizeof(ElementType)*cityNum );
618     
619     //初始化解空间 
620     for(i = 0;i< cityNum;i++){
621         strSolve->initSolution[i] = (ElementType)0;
622         strSolve->currentSolution[i] = (ElementType)0;
623         strSolve->optimalSolution[i] = (ElementType)0;
624         strSolve->tempSolution[i] = (ElementType)0;
625     }
626     strSolve->lastdistance  = 0;//记录上次迭代获得最好的距离值 
627     return strSolve;
628  } 
629 
630 /*************************************************
631 **Function: GetInitSolution
632 **Description: 获得初始解
633 **Calls: 无  
634 **Called By:  Init2Opt()
635 **Input: StrSolve * 指针变量 
636 **Output: 无 
637 **Return: StrSolve  *指针变量 
638 **Others: 这里在初始化解的时候可以用其他元启发式算法得出一个较好的解  ! 
639 @brief :思路 可以用一个记录初始解的类数组(申请的内存 大小为初始解的元素个数),之后循环 CityNum-1次,不断的产生1-CityNum-1的随机数
640  没产生一个就记录这个值 之后再次产生与上次不同的随机数 ,依次这样循环即可  不过速度上会很慢 
641 *************************************************/ 
642 void GetInitSolution(StrSolve * strSolve)
643 { 
644     int i;
645     
646     //默认从0号城市顺序开始 这里的0是固定不动的 
647     for( i = 0;i<CityNum;i++){
648         strSolve->initSolution[i] = i;
649         strSolve->currentSolution[i] = i;
650         strSolve->optimalSolution[i] = i;
651         strSolve->tempSolution[i] = i;
652     }
653         
654 }
655 
656 /*************************************************
657 **Function: Init2Opt
658 **Description: 初始化TSP需要用的值 
659 **Calls: CreateMotionStruct()  CreateSolutionSpace()  GetInitSolution()
660 **Called By:  main()
661 **Input: 无 
662 **Output: 无 
663 **Return: void
664 **Others: 这里在初始化解的时候可以用其他元启发式算法得出一个较好的解  ! 不知道为什么只能在Main函数中调用否则 会出现段错误 
665 *************************************************/ 
666 void Init2Opt()
667 {
668     motionTable = CreateMotionStruct(Neighbor);//初始化变化表  记录变化邻居值 
669     SolutionSpace = CreateSolutionSpace(CityNum);//创建解空间 
670     GetInitSolution(SolutionSpace);//初始化解 
671 }
672 
673 /*************************************************
674 **Function: MemFree
675 **Description: 释放申请的动态内存 
676 **Calls: 
677 **Called By:  main()
678 **Input: distance 存储城市距离的变量指针  queue 禁忌表队列  motiontable 移动表的指针  strSolve  解空间的指针 
679 **Output: 无 
680 **Return: void
681 **Others: 这里也可以一步一步的释放掉 各自的指针 因为就用一个.c所以释放内存的操作都在这里进行 
682 *************************************************/ 
683 void MemFree(ElementType ** distance,Queue *queue,MotionTable *motiontable,StrSolve *strSolve)
684 {
685     int i=0;
686     int j = 0;
687     
688     //释放矩阵元素存储区 
689     for(i = 0;i < CityNum; i++){
690         free( distance[i] );
691     }
692     free(distance);
693     
694     //释放移动表
695     free(motiontable); 
696     
697     //释放掉队列区 
698     free(queue->tabuList);
699     free(queue);
700     
701     //释放解空间
702     free(strSolve->initSolution);
703     free(strSolve->currentSolution);
704     free(strSolve->optimalSolution);
705     free(strSolve->tempSolution);
706     free(strSolve); 
707 
708 }
709 
710 /*************************************************
711 **Function: FindPosition
712 **Description: 在数组中找到指定元素值的位置 
713 **Calls: 
714 **Called By:  Get2OptChangeDistance()  TSP()
715 **Input: solution 一维数组指针  tabu  Tabu结构指针 
716 **Output: 无 
717 **Return: void
718 **Others: 这里是从solution[1]开始查找到的! 
719 *************************************************/ 
720 static void FindPosition(const ElementType * solution,Tabu *tabu)
721 {
722     int i;
723     Tabu tempTabu;
724     for(i = 1; i< CityNum;i++){
725         if( solution[i] == tabu->smallNum )
726             tempTabu.smallNum = i;
727         if( solution[i] == tabu->bigNum )
728             tempTabu.bigNum = i;
729     }
730     *tabu = tempTabu;//不能直接返回&tempTabu  因为这个是一个局部的变量 会有悬挂指针的后果 
731 }
732 
733 /*************************************************
734 **Function: FindPosition
735 **Description: 获得2邻域变化值 
736 **Calls: FindPosition()
737 **Called By:  Get2optSolution()
738 **Input:  tabu  Tabu结构指针  solution 一维数组指针 
739 **Output: 无 
740 **Return: ElementType 2邻域城市变化值 
741 **Others: 返回的值越小越好 ! 
742 *************************************************/
743 static ElementType Get2OptChangeDistance(Tabu * tabu,const ElementType * solution)
744 {
745     ElementType change1,change2;
746     Tabu tempTabu1 = *tabu;
747     Tabu tempTabu;
748     change1 = change2 = 0;
749     FindPosition(solution,&tempTabu1); //此时这里的tempTabu1存储的就是指定元素在 解空间中的位置 
750     tempTabu.bigNum  = ( tempTabu1.bigNum >tempTabu1.smallNum )? tempTabu1.bigNum: tempTabu1.smallNum;
751     tempTabu.smallNum  = ( tempTabu1.bigNum >tempTabu1.smallNum )? tempTabu1.smallNum: tempTabu1.bigNum;
752     
753     if( tempTabu.smallNum == tempTabu.bigNum-1){//两个元素在解空间中的 位置相差1 
754             if( tempTabu.bigNum == CityNum-1 ){    //最大值位置 在最后一个位置    
755                 change1  = Distance[ solution[tempTabu.smallNum -1] ][ solution[tempTabu.smallNum] ]+\
756                               Distance[ solution[tempTabu.bigNum] ][ solution[ 0] ];
757                 change2 =  Distance[ solution[tempTabu.smallNum -1] ][ solution[tempTabu.bigNum] ] +\
758                               Distance[    solution[tempTabu.smallNum] ][ solution[0] ];
759                 return (change2 - change1);//这个值越小越好 
760             }
761             else{
762                 change1  = Distance[ solution[tempTabu.smallNum -1] ][ solution[tempTabu.smallNum] ] +\
763                               Distance[ solution[tempTabu.bigNum] ][ solution[ tempTabu.bigNum +1] ];
764                 change2 =  Distance[ solution[tempTabu.smallNum -1] ][ solution[tempTabu.bigNum] ]   +\
765                               Distance[    solution[tempTabu.smallNum] ][ solution[tempTabu.bigNum +1] ];
766                               
767                 return (change2 - change1);
768             }
769     }
770     else{//两个元素位置 不挨着 
771         if( tempTabu.bigNum == CityNum-1 ){    //最大值位置 在最后一个位置    
772                 change1 = Distance[ solution[tempTabu.smallNum -1] ][ solution[tempTabu.smallNum] ] +\
773                              Distance[ solution[tempTabu.smallNum] ][ solution[tempTabu.smallNum +1] ] +\
774                              Distance[ solution[tempTabu.bigNum-1] ][ solution[ tempTabu.bigNum ] ]    +\
775                              Distance[ solution[tempTabu.bigNum] ][ solution[ 0] ];
776                 change2 = Distance[ solution[tempTabu.smallNum -1] ][ solution[tempTabu.bigNum] ] +\
777                              Distance[ solution[tempTabu.bigNum] ][ solution[tempTabu.smallNum+1] ]    +\
778                              Distance[ solution[tempTabu.bigNum-1] ][ solution[ tempTabu.smallNum ] ]+\
779                              Distance[ solution[tempTabu.smallNum] ][ solution[0] ];
780                 return (change2 - change1);//这个值越小越好 
781             }
782             else{
783                 
784                 change1 = Distance[ solution[tempTabu.smallNum -1] ][ solution[tempTabu.smallNum] ] +\
785                              Distance[ solution[tempTabu.smallNum] ][ solution[tempTabu.smallNum +1] ] +\
786                              Distance[ solution[tempTabu.bigNum-1] ][ solution[ tempTabu.bigNum ] ]    +\
787                              Distance[ solution[tempTabu.bigNum] ][ solution[ tempTabu.bigNum +1] ];
788                 change2 = Distance[ solution[tempTabu.smallNum -1] ][ solution[tempTabu.bigNum] ] +\
789                              Distance[ solution[tempTabu.bigNum] ][ solution[tempTabu.smallNum+1] ]    +\
790                              Distance[ solution[tempTabu.bigNum-1] ][ solution[ tempTabu.smallNum ] ]+\
791                              Distance[ solution[tempTabu.smallNum] ][ solution[tempTabu.bigNum +1] ];
792                 return (change2 - change1);
793             }
794     }
795 
796 }
797 
798 /*************************************************
799 **Function: Get2optSolution
800 **Description: 得到1个2邻域解 将移动元素,及其导致路径的变化值 存储到移动表中 
801 **Calls: Get2OptChangeDistance()
802 **Called By:  TSP()
803 **Input:  strSolve 解空间指针  motiontable 移动表指针 
804 **Output: 无 
805 **Return: void 
806 **Others: 随机数要注意! 
807 *************************************************/
808 void Get2optSolution(const StrSolve * strSolve,MotionTable *motiontable )
809 {
810     //产生一个1-CityNum-1之间的随机数  因为默认0为初始位置 不能动 
811     ElementType temp;
812     ElementType changeDistance;
813     int rand1,rand2;
814     
815 //    rand1 = (CityNum-1) *rand()/(RAND_MAX + 1.0);
816     rand1 = rand()%(CityNum-1)+1;
817     rand2 = rand()%(CityNum-1)+1;
818     while(  rand2 == rand1 )//必须产生两个不同的随机数 切不能为0 
819         rand2 = rand()%(CityNum-1) +1; 
820             
821     //记录交换的两个元素 (不是位置) 
822     motiontable->tabu.smallNum  = (rand2 >rand1)? rand1:rand2;
823     motiontable->tabu.bigNum =     (rand2 >rand1)? rand2:rand1;
824     motiontable->changedistance = Get2OptChangeDistance( &motiontable->tabu ,strSolve->tempSolution ); 
825          
826 }
827 
828 /*************************************************
829 **Function: Insert_Sort
830 **Description: 按从小到大排序 插入排序 将制定的类数组变量 的内容进行排序 
831 **Calls: 无
832 **Called By:  FindBestMotionValue()
833 **Input:    motiontable 移动表指针  n为类数组 元素个数 
834 **Output: 无 
835 **Return: void 
836 **Others: 
837 *************************************************/
838 void Insert_Sort (MotionTable * motiontable,int n)
839 {
840     //进行N-1轮插入过程
841     int i,k;
842     for(i=1; i<n; i++){
843      //首先找到元素a[i]需要插入的位置
844      
845          int j=0;
846          while( (motiontable[j].changedistance < motiontable[i].changedistance )  && (j <i ) )
847                  j++;
848                  
849          //将元素插入到正确的位置
850          if(i != j){  //如果i==j,说明a[i]刚好在正确的位置
851              MotionTable temp = motiontable[i];
852              for(k = i; k > j; k--){
853                  motiontable[k] = motiontable[k-1];
854              }
855              motiontable[j] = temp;
856          }
857     }
858 }
859 
860 /*************************************************
861 **Function: FindBestMotionValue
862 **Description: 找到移动表中最小的值 即为最优值 
863 **Calls: Insert_Sort()
864 **Called By:  TSP()
865 **Input:    motiontable 移动表指针  
866 **Output: 无 
867 **Return: MotionTable *型的指针 存储移动表中最好值的表格指针 
868 **Others: 
869 *************************************************/
870 MotionTable * FindBestMotionValue( MotionTable * motiontable)
871 {
872     //下面是仅仅找到一个最好的值 不管在不在禁忌表中 
873 //    MotionTable *bestMotion= motiontable;
874 //    MotionTable *start = motiontable;
875 //    MotionTable *end     = motiontable + Neighbor-1;
876 //    while(start++ < end ){
877 //        if( start->changedistance < bestMotion->changedistance){
878 //            bestMotion = start;//保存最好的结构 
879 //        }
880 //    }
881 //    if( start->changedistance < bestMotion->changedistance )
882 //        bestMotion = start; 
883 //    return bestMotion;//f返回最好结构的指针
884     Insert_Sort(motiontable,Neighbor);//选择排序算法 从小到大排    
885      
886     return motiontable;//返回最好元素的地址 
887 } 
888 
889 /*************************************************
890 **Function: GetInitLevel
891 **Description: 获取初始解的渴望水平 
892 **Calls: 
893 **Called By:  TSP()
894 **Input:    distance 存储城市的矩阵指针 initSolution 初始解指针  
895 **Output: 无 
896 **Return: 初始解的渴望水平 
897 **Others: 
898 *************************************************/
899 int GetInitLevel( ElementType **distance,ElementType * initSolution)
900 {
901     int i;
902     int SumLevel = 0;
903     for(i = 0; i < CityNum-2 ; i++){
904         SumLevel += distance[ initSolution[i] ][ initSolution[i+1] ];
905     } 
906     SumLevel+= distance[ initSolution[i] ][0];//最后在加上 最后一个值和初始值的 距离 才是循环的总距离距离 
907     
908     return SumLevel; 
909 }
910 
911 /*************************************************
912 **Function: TSP
913 **Description: TSP核心算法 
914 **Calls: GetInitLevel() 
915 **Called By:  TSP()  Get2optSolution()  FindBestMotionValue()  UpdateTabu()  FindPosition()  memcpy()
916 **Input:    distance 存储城市的矩阵指针 solutionSpace 解空间指针 motiontable 移动表 desireLevel 渴望水平 queue 禁忌表队列指针  
917 **Output: 最优解信息 
918 **Return: void  
919 **Others: 
920 *************************************************/
921 void TSP(  ElementType **distance, StrSolve * solutionSpace ,MotionTable *motiontable,int *desireLevel,Queue *queue)
922 {
923     int i;
924     int temp;
925     int neighborNum = 0;
926     MotionTable * BestMotionStruct;
927     ElementType BestChangeDistance;//最好的改变的值 
928 //    Init2Opt();//初始化相关 
929     *desireLevel = GetInitLevel(distance,solutionSpace->initSolution);
930     solutionSpace->lastdistance = *desireLevel;//初始最优值为上次移动的最好的距离 
931     solutionSpace->initdistance = solutionSpace->lastdistance;//将初始值给初始距离  之后再判断 减少的距离 
932     printf("初始距离:%d ",*desireLevel);
933 //    printf("初始最好的距离是%d,solutionSpace->lastdistance = %d\n",*desireLevel,solutionSpace->lastdistance);
934     printf("城市数量:%d 迭代次数:%d 邻居个数:%d\n",CityNum,MaxNG,Neighbor);
935     //迭代 次数作为停止条件 
936     while( currentNG++ < MaxNG ){
937         //获得邻居最好解
938         for( neighborNum = 0; neighborNum < Neighbor; neighborNum++ ){//循环Neighbor那么多次 
939             Get2optSolution(SolutionSpace,&motionTable[neighborNum] );//将邻域 移动放在移动表中 
940         } 
941         
942         //找到移动表中最小的值 此时解若是 < 渴望水平 则更新最优解 否则找到不在禁忌表中的 最好的解 更新当前解
943         BestMotionStruct = FindBestMotionValue( motiontable);
944         BestChangeDistance = BestMotionStruct->changedistance;
945         
946          if( solutionSpace->lastdistance + BestChangeDistance < *desireLevel){//当前迭代出的最好的解 小于渴望水平 更新最优解T表当前解 
947             int temp;
948             //更新T表
949             UpdateTabu(queue,&BestMotionStruct->tabu); 
950             //更新渴望水平
951             *desireLevel = solutionSpace->lastdistance +BestChangeDistance;
952             //更新上次迭代的最优值
953             solutionSpace->lastdistance = *desireLevel;
954             //更新当前解和最优解 
955             FindPosition(solutionSpace->tempSolution,&BestMotionStruct->tabu);//找到当前解 对应的解空间的位置  
956             temp = solutionSpace->tempSolution[ BestMotionStruct->tabu.smallNum ];
957             solutionSpace->tempSolution[ BestMotionStruct->tabu.smallNum] = solutionSpace->tempSolution[ BestMotionStruct->tabu.bigNum ];
958             solutionSpace->tempSolution[ BestMotionStruct->tabu.bigNum ] = temp;
959             memcpy( solutionSpace->currentSolution,solutionSpace->tempSolution,sizeof(ElementType)*CityNum ); //将临时解空间值复制到当前解空间 
960             memcpy( solutionSpace->optimalSolution,solutionSpace->tempSolution,sizeof(ElementType)*CityNum );
961     
962         }
963         else{//没有小于渴望水平 找到不在禁忌表中最好的移动 
964             //在移动表中找到不在禁忌表中最好元素 因为拍好序了 所以从表的第二个值开始找即可 
965             int i;
966             for(i  = 0;i< Neighbor; i++){
967                 if( !IsFindTabu(queue,&motiontable[i].tabu) ){
968                     int temp;
969                     //不在禁忌表中  则这个值就是目前来说最好的值 
970                     BestMotionStruct = &motiontable[i];
971                     //更新T表
972                     UpdateTabu(queue,&BestMotionStruct->tabu); 
973                     solutionSpace->lastdistance = solutionSpace->lastdistance + BestMotionStruct->changedistance;
974                     //更新当前解
975                     FindPosition(solutionSpace->tempSolution,&BestMotionStruct->tabu);//找到当前解 对应的解空间的位置  
976                     temp = solutionSpace->tempSolution[ BestMotionStruct->tabu.smallNum ];
977                     solutionSpace->tempSolution[ BestMotionStruct->tabu.smallNum] = solutionSpace->tempSolution[ BestMotionStruct->tabu.bigNum ];
978                     solutionSpace->tempSolution[ BestMotionStruct->tabu.bigNum ] = temp;
979                     memcpy( solutionSpace->currentSolution,solutionSpace->tempSolution,sizeof(ElementType)*CityNum ); //将临时解空间值复制到当前解空间 
980                     
981                     break;//跳出循环 
982                 }        
983             }
984         }
985 
986     }
987     currentNG = 0;//将全局迭代次数变量值清零 
988     printf("\n初始值:%d 最优解值:%d 优化距离:%d\n最优解元素:\n\n",\
989         solutionSpace->initdistance,\
990         GetInitLevel(distance,solutionSpace->optimalSolution),solutionSpace->initdistance - *desireLevel); 
991     for(i = 0 ;i< CityNum;i++){
992         printf("%d-> ",solutionSpace->optimalSolution[i]);
993     } 
994     printf( "%d \n",solutionSpace->optimalSolution[0] );
995 } 
View Code

试验结果如下:

 

文章评论

程序员都该阅读的书
程序员都该阅读的书
 程序员的样子
程序员的样子
10个调试和排错的小建议
10个调试和排错的小建议
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
旅行,写作,编程
旅行,写作,编程
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
每天工作4小时的程序员
每天工作4小时的程序员
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
那些争议最大的编程观点
那些争议最大的编程观点
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
为什么程序员都是夜猫子
为什么程序员都是夜猫子
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
一个程序员的时间管理
一个程序员的时间管理
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
编程语言是女人
编程语言是女人
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
Java程序员必看电影
Java程序员必看电影
老程序员的下场
老程序员的下场
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
程序员必看的十大电影
程序员必看的十大电影
我是如何打败拖延症的
我是如何打败拖延症的
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
鲜为人知的编程真相
鲜为人知的编程真相
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
程序员应该关注的一些事儿
程序员应该关注的一些事儿
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
中美印日四国程序员比较
中美印日四国程序员比较
程序员的鄙视链
程序员的鄙视链
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
程序员和编码员之间的区别
程序员和编码员之间的区别
我的丈夫是个程序员
我的丈夫是个程序员
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有