模拟退火算法解决工作指派问题c源程序.doc

/* 模拟退火算法解决工作指派问题输入格式(工作时间)：矩阵行i；工人列j；工作*/#include #include #include #include using namespace std;const int MAXN = 501; /最大约束数nconst double INIT_T =2000; /初始温度const double RATE = 0.95; /温度衰减率const double FINAL_T = 1E-10; /终止温度const int IN_LOOP = 13000; /内层循环次数const int OUT_LOOP = 2000; /外层循环次数struct work /定义工作结构类型 int pMAXN; /工人序号 double time; /时间 ;int N; /工人数量double DMAXNMAXN; /工作时间int xMAXN MAXN; /选择工人与工作work bestwork; /最优的遍历路径void swap(int a,int b) int t; t=a;a=b;b=t; inline double totaldist(work p) /计算总时间 int i,j; double cost = 0,sumi=0, sumj=0;for (j=1; j=N; j+) sumj+= xij; for (i=1; i=N; i+) sumi+= xij;if(sumj=1& sumi=1)for (j=1; j=N; j+)for (i=1; i N; int i,j;for(i=0;i=N;i+) for(j=0;j Dij;for (i=j=1; i=j=N; i+,j+) /最优解的初始状态 bestwork.pi = i; bestwork.time = totaldist(bestwork); /* 产生指派方法*/work getnext(work p) /新解产生函数 int x, y,i,j; work ret; ret = p; do x = rand() % N + 1; y = rand() % N + 1; while(x = y); swap(ret.px, ret.py); /交换两工人位置顺序 ret.time = totaldist(bestwork); return ret; /* 退火和降温过程 */ void sa() double T; /温度 work newwork, curwork; /当前指派和新指派 int i,A_t=0; double delta; T = INIT_T; /赋值初始温度 curwork = bestwork; while(true) for (i=1; i=IN_LOOP; i+) newwork = getnext(curwork); /获取新路径 delta = newwork.time - curwork.time; if (delta rnd) curwork = newwork; A_t+; if ( A_t = OUT_LOOP | T FINAL_T) break; T = T * RATE; /降温 /* 程序主函数 */int main() init(); printf(初始工作指派: %.4fn, bestwork.time);for(int i=0;i, bestwork.pi); printf(n); sa(); printf(最