回溯问题：m点着色、n皇后、tsp递归迭代算法

《回溯问题：m点着色、n皇后、tsp递归迭代算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、m着色回溯法递归//输入n为顶点个数，颜色数m，图的邻接矩阵c[][]//输出n个顶点的着色x[]//递归方法求解#includeusingnamespacestd;boolc[6][6];intx[6];intm=3;intn=5;boolok(intk)//判断对顶点k着色以后是否合法着色{inti;for(i=1;i

2、or(inti=1;i<=n;i++)cout<n)output(x);elsefor(inti=1;i<=m;i++){x[t]=i;if(ok(t))backtrack(t+1);x[t]=0;}}intmain(){inti,j;for(i=1;i<5;i++)for(j=1;j<5;j++)c[i][j]=false;c[1][2]=true;c[1][3]=true;c[2][3]=true;c[2][4]=true;c[2][5]=true;c[3

3、][5]=true;c[4][5]=true;c[2][1]=true;c[3][1]=true;c[3][2]=true;c[4][2]=true;c[5][2]=true;c[5][3]=true;c[5][4]=true;backtrack(1);cout<usingnamespacestd;boolc[6][6];intx[6];intm=3;intn=5;bo

4、olok(intk)//判断对顶点k着色以后是否合法着色{inti;for(i=1;i=1){x[k]++;while(x[k]<=m)if(ok(k)==1)break;elsex[k]++;if(x[k]<=m&&k==n){for(i=1;i<=n;i++)cout<

5、k--;//return;如果只需要一个解可以将上两句去掉，加入返回语句}elseif(x[k]<=m&&k

6、c[5][2]=true;c[5][3]=true;c[5][4]=true;m_coloring(5,3);cout<usingnamespacestd;#defineQ_num4intx[Q_num];//存放每行棋子位置intnumber=0;//存放棋盘解的个数voidoutput(intx[]){cout<<"棋盘放置位置如图:"<

7、printf("%3d",x[i]);elseprintf("%3d",0);}cout<

8、

9、abs(k-i)==abs(x[k]-x[i]))returnfalse;returntrue;}intQueue_backtrack(intt){if(t>Q_num){number++;output(x);}elsefor(inti=1;i<=Q_num;i++){x[t]=i;if(x[t]