欢迎来到天天文库
浏览记录
ID:15953516
大小:67.50 KB
页数:6页
时间:2018-08-06
《回溯算法最大团和m着色问题java源程序》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、实验报告12课程数据结构与算法实验名称回溯法第页班级11计本学号105032011130姓名风律澈实验日期:2013年5月27日报告退发(订正、重做)一、实验目的掌握回溯法的原理和应用。二、实验环境1、微型计算机一台2、WINDOWS操作系统,JavaSDK,Eclipse开发环境三、实验内容必做题:1、编写程序,采用回溯法求解最大团问题。2、编写程序,采用回溯法实现m着色问题。四、实验步骤和结果(附上代码和程序运行结果截图)1最大团publicclassMaxclique{/***@paramargs*/static
2、grapha;staticintn;//顶点数目staticintnowanswer[];//当前解staticintnowpointn;//当前顶点数量staticintnowmostpointn;//当前最多顶点子图staticintnowbestanswer[];//当前可能最优解publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubintx[][]={{1,1,0,1,1},{1,1,1,0,1},{0,1,1,0,1},{1,0,0,
3、1,1},{1,1,1,1,1}};//初始化变量n=5;a=newgraph(x,n);nowanswer=newint[n];nowpointn=0;nowmostpointn=0;nowbestanswer=newint[n];nowbestanswer=a.getpoint(1).getreach();nowanswer[0]=1;//进入算法backtrack(0);//输出解System.out.println(nowmostpointn);for(inti=0;i4、){System.out.print(nowanswer[i]+"");}}privatestaticvoidbacktrack(inti){//TODOAuto-generatedmethodstubif(i>n-1){for(intj=0;j5、ack(i+1);nowpointn--;}elseif(nowpointn+n-i>nowmostpointn){nowanswer[i]=0;backtrack(i+1);}}}——————————————————————————————————publicclassgraph{privatepointp[];publicgraph(intx[][],intn){p=newpoint[x.length];for(inti=0;i6、npointnumber(){returnp.length;}publicintcheck(inti,int[]x){//TODOAuto-generatedmethodstubintok=1;for(intj=0;j7、blicclasspoint{privateintreach[];publicpoint(intx[]){this.reach=x;};publicintreachornot(intj){returnreach[j];}publicint[]getreach(){returnreach;}}———————————————————————————————————————2,m着色问题publicclassColoring{/***@paramargs*/staticintn,m;staticint[][]a;static8、int[]x;staticlongsum;publicstaticlongmColoring(intmm){m=mm;sum=0;backtrack(1);returnsum;}privatestaticvoidbacktrack(intt){//TODOAuto-generatedmethodstubif(t>n){sum++;
4、){System.out.print(nowanswer[i]+"");}}privatestaticvoidbacktrack(inti){//TODOAuto-generatedmethodstubif(i>n-1){for(intj=0;j5、ack(i+1);nowpointn--;}elseif(nowpointn+n-i>nowmostpointn){nowanswer[i]=0;backtrack(i+1);}}}——————————————————————————————————publicclassgraph{privatepointp[];publicgraph(intx[][],intn){p=newpoint[x.length];for(inti=0;i6、npointnumber(){returnp.length;}publicintcheck(inti,int[]x){//TODOAuto-generatedmethodstubintok=1;for(intj=0;j7、blicclasspoint{privateintreach[];publicpoint(intx[]){this.reach=x;};publicintreachornot(intj){returnreach[j];}publicint[]getreach(){returnreach;}}———————————————————————————————————————2,m着色问题publicclassColoring{/***@paramargs*/staticintn,m;staticint[][]a;static8、int[]x;staticlongsum;publicstaticlongmColoring(intmm){m=mm;sum=0;backtrack(1);returnsum;}privatestaticvoidbacktrack(intt){//TODOAuto-generatedmethodstubif(t>n){sum++;
5、ack(i+1);nowpointn--;}elseif(nowpointn+n-i>nowmostpointn){nowanswer[i]=0;backtrack(i+1);}}}——————————————————————————————————publicclassgraph{privatepointp[];publicgraph(intx[][],intn){p=newpoint[x.length];for(inti=0;i6、npointnumber(){returnp.length;}publicintcheck(inti,int[]x){//TODOAuto-generatedmethodstubintok=1;for(intj=0;j7、blicclasspoint{privateintreach[];publicpoint(intx[]){this.reach=x;};publicintreachornot(intj){returnreach[j];}publicint[]getreach(){returnreach;}}———————————————————————————————————————2,m着色问题publicclassColoring{/***@paramargs*/staticintn,m;staticint[][]a;static8、int[]x;staticlongsum;publicstaticlongmColoring(intmm){m=mm;sum=0;backtrack(1);returnsum;}privatestaticvoidbacktrack(intt){//TODOAuto-generatedmethodstubif(t>n){sum++;
6、npointnumber(){returnp.length;}publicintcheck(inti,int[]x){//TODOAuto-generatedmethodstubintok=1;for(intj=0;j
7、blicclasspoint{privateintreach[];publicpoint(intx[]){this.reach=x;};publicintreachornot(intj){returnreach[j];}publicint[]getreach(){returnreach;}}———————————————————————————————————————2,m着色问题publicclassColoring{/***@paramargs*/staticintn,m;staticint[][]a;static
8、int[]x;staticlongsum;publicstaticlongmColoring(intmm){m=mm;sum=0;backtrack(1);returnsum;}privatestaticvoidbacktrack(intt){//TODOAuto-generatedmethodstubif(t>n){sum++;
此文档下载收益归作者所有