原创：TSP问题解决方案-----禁忌搜索算法C实现
2018-06-18 03:58:29来源：未知 阅读 ()
本文着重于算法的实现，对于理论部分可自行查看有关资料可以简略参考该博文: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 }
试验结果如下:
相关资源（源码包以及数据）可在以下网址下载：
http://download.csdn.net/download/geself/10191257
运行环境:windows7
IDE: DEVC++
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
上一篇：实现解一元二次方程（循环）
相关文章
- Android P HIDL demo代码编写 （原创） 2020-05-07
- WDK驱动调试问题点滴 2020-04-21
- 螺旋矩阵问题 2020-04-18
- 用C++实现：完美的代价 2020-04-15
- 用C++实现：FJ的字符串打印 2020-04-04
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
热门词条
最新资讯
热门关注
热门标签