跪求 用禁忌搜索算法解组合优化，5个城市走一遍最优路径，有没有C或c++的源代码

>

从一个省开始，给它涂上任意一种颜色1，遍历它旁边的省份，涂上与已经涂色并于他相邻的省份不同的颜色就行了。

理论上4种颜色就够了地图的四色问题嘛!

可能会有多组解。用递归（dfs)就可以输出所有解了。

地图着色算法C语言源代码

前面我写了一个地图着色（即四色原理）的C源代码。

写完以后想了一下，感觉还不完善，因为从实际 *** 作的角度来考虑，四种可用的颜色放在旁边，不同的人可能会有不同的选择顺序，另外，不同的人可能会选择不同的城市作为着色的起点，而当时的程序没有考虑这个问题。于是，把程序修改为下面的样子，还请同行分析并指出代码中的不足之处：

＃i nclude <stdioh>

#define N 21

int allcolor[4];/可用的颜色/

int ok(int metro[N][N],int r_color[N],int current)

{/ok函数和下面的go函数和原来的一样,保留用来比较两种算法/

int j;

for(j=1;j<current;j++)

if(metro[current][j]==1&&r_color[j]==r_color[current])

return 0;

return 1;

}

void go(int metro[N][N],int r_color[N],int sum,int current)

{

int i;

if(current<=sum)

for(i=1;i<=4;i++)

{

r_color[current]=i;

if(ok(metro,r_color,current))

{

go(metro,r_color,sum,current+1);

return;

}

}

}

void color(int metro[N][N],int r_color[N],int sum,int start)

{

int i,j,k;

r_color[start]=allcolor[0];

for(i=start+1;i!=start;i=(i+1)%(sum+1))/把所有编号看作一个环/

if(i==0)/城市号从1开始编号,故跳过0编号/

continue;

else

for(j=0;j<4;j++)

{

r_color[i]=allcolor[j];/选取下一种颜色,根据allcolor中颜色顺序不同，结果不同/

for(k=1;k<i;k++)/检查是否有冲突，感觉还可以改进，如使用禁忌搜索法/

if(metro[i][k]==1&&r_color[k]==r_color[i])

break;

if(k>=i)

break;

}

}

void main()

{

int r_color[N]={0};

int t_color[N]={0};

int i;

int start;/着色的起点/

int metro[N][N]={{0},

{0,1,1,1,1,1,1},

{0,1,1,1,1},

{0,1,1,1,0,0,1},

{0,1,1,0,1,1},

{0,1,0,0,1,1,1,0,0,1,0,0,0,0,0,0,1},

{0,1,0,1,0,1,1,1,1,1},

{0,0,0,0,0,0,1,1,1},

{0,0,0,0,0,0,1,1,1,1,0,0,1},

{0,0,0,0,0,1,1,0,1,1,0,0,1,1,1,0,1},

{0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,1,0,0,0,1},

{0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1},

{0,0,0,0,0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,1,1},

{0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1},

{0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,1},

{0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1,1,0,1},

{0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,1,1},

{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1},

{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1},

{0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,1,0,0,1,1,1},

{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1}};

allcolor[0]=1;allcolor[1]=2;allcolor[2]=3;allcolor[3]=4;/选色顺序，顺序不同，结果不同/

start=1;

/ clrscr();/

printf("\nAll color is:\n");

for(i=0;i<4;i++)/当前选色顺序/

printf("%d ",allcolor[i]);

go(metro,r_color,20,1);

printf("\nFirst method:\n");

for(i=1;i<=20;i++)

printf("%3d",r_color[i]);

color(metro,t_color,20,start);

printf("\nSecond method:\n");

printf("\nAnd the start metro is:%d\n",start);

for(i=1;i<=20;i++)

printf("%3d",t_color[i]);

}

说是人性化着色，其实还有一个问题没有考虑，那就是 *** 作员跳跃式着色，就像大家玩“扫雷”游戏一样。其实也容易实现，可以像定义选色顺序一样定义着色顺序。

禁忌搜索算法过时了。

禁忌搜索仍出现循环。因此，必须给定停止准则以避免出现循环。当迭代内所发现的最好解无法改进或无法离开它时，算法停止，所以禁忌搜索算法过时了。

禁忌搜索是一种现代启发式算法，由美国科罗拉多大学教授FredGlover在1986年左右提出的。

局部领域搜索是基于贪婪思想持续地在当前解的领域中进行搜索，虽然算法通用易实现，且容易理解，但其搜索性能完全依赖于领域结构和初解，尤其窥陷入局部极小而无法保证全局优化性。针对局部领域搜索，为了实现全局优化，可尝试的途径有：以可控性概率接受劣解来逃逸局部极小，如模拟退火算法；扩大领域搜索结构，如TSP的2opt扩展到k-opt；多点并行搜索，如进化计算；变结构领域搜索（ Mladenovic et al,1997）；另外，就是采用TS的禁忌策略尽量避免迂回搜索，它是一种确定性的局部极小突跳策略。

禁忌搜索是人工智能的一种体现，是局部领域搜索的一种扩展。禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象，并在进一步的迭代搜索中尽量避开这些对象（而不是绝对禁止循环），从而保证对不同的有效搜索途径的探索。禁忌搜索涉及到邻域（neighborhood）、禁忌表（tabu list）、禁忌长度（tabu length）、候选解（candidate）、藐视准则（aspiration criterion）等概念;

以上就是关于跪求 用禁忌搜索算法解组合优化，5个城市走一遍最优路径，有没有C或c++的源代码全部的内容，包括:跪求 用禁忌搜索算法解组合优化，5个城市走一遍最优路径，有没有C或c++的源代码、启发式算法、地图着色问题源程序C++语言（算法设计与分析）急求等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！