求模擬退火解決指派問題的C++程式，謝謝
uj5u.com熱心網友回復：
我也想問這個問題uj5u.com熱心網友回復：
/*********************************************************************** 模擬退火演算法解決作業指派問題 隨機生成N維作業時間矩陣***********************************************************************/
#include <iostream>
#include <cmath>
#include <time.h>
#include <stdio.h>
using namespace std;
const int MAXN = 50; //最大約束數n
const double INIT_T =2000; //初始溫度
const double RATE = 0.95; //溫度衰減率
const double FINAL_T = 0; //終止溫度
const int IN_LOOP = 13000; //內層回圈次數
const int OUT_LOOP = 20000; //外層回圈次數
struct work { //定義作業結構型別
int p[MAXN]; //工人序號
double time; //時間
};
int N; //工人數量
double D[MAXN][MAXN]; //作業時間
int x[MAXN][ MAXN]; //選擇工人與作業
work bestwork; //最優的遍歷路徑
void swap(int &a,int &b) //注意&a和&b 我們要的p[]里存盤的資料
{
int t;
t=a;a=b;b=t;
}
inline double totaldist(work q) //計算總時間
{
int a,i,j;
double cost = 0;
for(i=0,j=0;i<N;i++,j++)
{
a=q.p[i];
cost=D[a][j];
}
return cost;
}
void init() //讀入資料，并初始化//輸入時間矩陣D[i][j] 格式：工人i 作業j
{ cout<<"input N"<<endl;
cin>>N;
int i=0,j=0;
for(i=0;i<N;i++)
{
for(j=0;j< N;j++)
D[i][j]=rand()%100;
}
for (i=0; i<N; i++) //最優解的初始狀態
{
bestwork.p[i] = i;
}
bestwork.time = totaldist(bestwork);
}
/*********************************************************************** 產生指派方法
***********************************************************************/
work getnext(work p) //新解產生函式
{
int x, y;
work ret;
ret = p;
do {
x = rand() % 4;
y = rand() % 4 ;//x,y產生0-3的亂數
}while(x == y);
swap(ret.p[x], ret.p[y]); //交換兩工人位置順序
ret.time = totaldist(ret);
return ret;
}
/*********************************************************************** 退火和降溫程序
**********************************************************************/
work sa()
{
double T; //溫度
work curwork,newwork; //當前指派和新指派
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 < 0.0)
{
curwork = newwork;
}
else
{
double rnd = rand()%1001/1000; //隨機產生0-1的浮點數
double p = exp(-delta/T);
if (p > rnd)
curwork = newwork;
else
curwork=curwork;
}
A_t++;
}
T = T * RATE; //降溫
if ( A_t >= OUT_LOOP || T < FINAL_T) break; //外回圈停止條件
}
return newwork;
}
/*********************************************************************** 程式主函式
*********************************************************************/
int main()
{
init();
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
cout<<D[i][j]<<" ";
cout<<endl;
}
printf("初始作業指派: %.4f\n", bestwork.time);
for(int i=0;i<N;i++)
{
printf(" %d->", bestwork.p[i]+1);
}
printf("\n");
bestwork=sa();
printf("最優作業指派: %.4f\n", bestwork.time);
for(int j=0;j<N;j++)
{
printf(" %d->",bestwork.p[j]+1);
}
printf("\n");
system("pause");
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/54958.html
標籤：基礎類
上一篇：如何使用gcc_clang進行C語言的編譯_編譯的流程是什么？
下一篇：哪位大俠幫忙指點下C語言的代碼