模拟退火实验报告

算法报告一、课题名称一种用于生物网络中最多公共边子图检测的模拟退火算法二、实验目的介绍了一种用于多重最多公共边子图问题的启发式算法，它能够有效地检测出在多个真实世界大小的网络上共享的大型公共子结构。三、实验环境现代C++编译器支持C++11和OpenMPmakeCMake=2.8Boost标题help2man（可选，用于手册页生成）四、实验主要步骤安装所有以上环境后，运行以下命令：gitclone--recursive或者，您可以安装二进制文件和文档：sudomakeinstall要对齐三个图表，运行600秒：sailmcs-t600-gmcs.gw-oalignment.txtgraph1.gwgraph2.gwgraph3.gw最大公共子图将被写入文件mcs.gw，顶点对齐表将被写入alignment.txt。五、实验核心代码#includesailmcs/ls/Best.hpp#includealgorithm#includerandom#includesailmcs/ls/Common.hppnamespaceublas=boost::numeric::ublas;namespacesailmcs{namespacels{voidBest::localSearch(conststd::vectorGraph&graphs,Solution&solution){size_tm=solution.alignment.size1();size_tn=solution.alignment.size2();//Createreversealignmentmappingstd::vectorstd::vectorsize_tmap;create_map(graphs,solution,map);//Countnumberofgraphseachedgeiscoveredinedge_count_matrixedges;count_edges(graphs,map,solution,edges);//Buildneighborlistsstd::vectorneighbor_listneighbors;create_neighbor_lists(graphs,map,solution,neighbors);//Activeindexmapstd::vectorintactive(m,0);std::random_devicerd;std::minstd_randrand_gen(rd());intiteration=0;boolrepeat;do{repeat=false;for(size_tg=0;gn-1;++g){intbest_delta=0;size_tbest_i=0;size_tbest_j=0;#pragmaompparallel{intprv_best_delta=0;size_tprv_best_i=0;size_tprv_best_j=0;#pragmaompforschedule(static,1)for(size_ti=0;im;++i){for(size_tj=i+1;jm;++j){if(active[i]iteration&&active[j]iteration)continue;intdelta=get_delta(i,j,g,neighbors,edges);if(delta0){active[i]=iteration+1;active[j]=iteration+1;}if(deltaprv_best_delta){prv_best_delta=delta;prv_best_i=i;prv_best_j=j;}}}#pragmaompcritical{if(prv_best_deltabest_delta){best_delta=prv_best_delta;best_i=prv_best_i;best_j=prv_best_j;}}}if(best_delta0){repeat=true;swap(best_i,best_j,g,iteration,neighbors,edges,solution,active);}}iteration++;}while(repeat);//ExtractLCSandsolutionqualityfinalize(edges,solution);}}}六、实验数据部分数据如下：50个顶点的数据LEDA.GRAPHstringstring-250|{0}||{1}||{2}||{3}||{36}||{37}||{6}||{33}||{41}||{10}||{7}||{12}||{16}||{22}||{29}||{30}||{31}||{48}||{4}||{5}||{40}||{43}||{34}||{19}||{23}||{24}||{26}||{27}||{25}||{11}||{44}||{14}||{15}||{17}||{46}||{47}||{32}||{8}||{9}||{42}||{13}||{18}||{20}||{35}||{38}||{21}||{28}||{45}||{49}||{39}|70120|{?}|130|{?}|140|{?}|150|{?}|160|{?}|170|{?}|180|{?}|190|{?}|1100|{?}|1110|{?}|1120|{?}|1130|{?}|1140|{?}|1150|{?}|1160|{?}|1170|{?}|230|{?}|240|{?}|2120|{?}|2130|{?}|2180|{?}|2190|{?}|2200|{?}|2210|{?}|2220|{?}|2230|{?}|2240|{?}|2250|{?}|2260|{?}|2270|{?}|2280|{?}|3290|{?}|4190|{?}|4200|{?}|7190|{?}|7420|{?}|8190|{?}|10440|{?}|11200|{?}|11260|{?}|13140|{?}|13190|{?}|13200|{?}|14200|{?}|15410|{?}|19200|{?}|19250|{?}|19300|{?}|19310|{?}|19320|{?}|19330|{?}|19340|{?}|19350|{?}|19360|{?}|20240|{?}|20260|{?}|20370|{?}|20380|{?}|20390|{?}|20400|{?}|20410|{?}|20420|{?}|20430|{?}|24260|{?}|26470|{?}|27480|{?}|28490|{?}|28500|{?}|32450|{?}|42460|{?}|七、实验结果实验部分数据输出如下：（含截图）八、实验中的问题