/*
* 2007_12.c
* use the follow command to compile (OS: Ubuntu Linux 7.10 with the 2.6.22 kernel):
* gcc 2007_12.c -Wall -lpthread -lm -o 2007_12
* Need pthread library and math library.
*/
/*
* Below is the algorithm introduced in Simplified Chinese.
* encoding: UTF-8
*
* 2007.12 房间分配
* 使用模拟退火算法解决问题
* by cugb_cat
*
* 模拟退火算法的基本步骤:
* STEP1
* 任选一个初始解x[0]; x[1] = x[0]; k = 0; t[0] = tmax(初始温度);
* STEP2
* 若在该温度达到内循环停止条件, 则到STEP3; 否则, 从邻域N(x[i])中随机选一x[j],
* 计算delta f[ij]=f(x[j]) - f(x[i]); 若delta f[ij]<=0, 则x[i]=x[j], 否则,
* 若exp(-1 * delta f[ij] / t[k]) > random(0, 1)时, 则x[i] = x[j]; 重复STEP2;
* STEP3
* t[k+1]=d(t[k]); k = k+1; 若满足停止条件, 终止计算; 否则, 回到STEP2.
*
* 邻域结构的计算方法(即, 新解的产生方法): 随机产生1和N(学生总数)之间的两相异数k和m,
* 若k<m,则将(w1, w2, ..., wk, wk+1, ..., wm, ..., wn) 变为:(w1, w2, ..., wm,
* wm-1, ..., wk+1, wk, ..., wn).
* 如果是k>m，则将(w1, w2, ..., wm, wm+1, ..., wk, ..., wn)
* 变为:(wm, wm-1, ..., w1, wm+1, ..., wk-1, wn, wn-1, ..., wk).
* 并且,在选取新解时, 需注意是否与当前解的效果相同.
*
* 初始温度的选取:t[0]=K*delta, K为充分大的数(取K=10,20,100...等实验值),
* delta=max{f(j)|j属于D} - min{f(j)|j属于D}, D为解空间.
*
* 温度下降方法:t[k+1] = alpha * t[k], k>=0, 其中0 < alpha < 1,
* 本题目中alpha暂定为0.5
*
* 每一温度的迭代长度规则:采用由接受和拒绝的比率来控制迭代步数, 描述为,
* 给定一个接受比率指标R、迭代步长上限U和下限L,
* 每一温度至少迭代L步且记录同一温度迭代的总次数和被接受的次数,
* 当迭代超过L步时, 若接受次数同总次数的比率不小于R时,
* 在这一温度不再迭代而开始温度下降, 否则, 一直迭代到上限步数
*
* 算法终止原则: 采用基于不改进规则的控制法, 即,
* 在指定步数后没有改进该局部最优解, 则程序终止.
*
* 并行策略的选择: 采取协同试验并行策略, 即,
* p个线程同时产生各自的新解并作出判断, 然后,
* 对其中满足接受准则者(通常少于p个甚至没有)按某个法则fai(在本题目中采用最早法则,
* 即, 接受最早通过判断的新解, 同时中断其余线程的运行)选择一个予以接受,
* 再在此基础上进行下一轮试验.
*
* 暂定采用2个线程并发计算(因为测试机为酷睿2双核处理器), 具体使用线程的个数应该和CPU的核心数一致.
*
* 参考: 《非数值并行算法1模拟退火算法》, 《现代优化计算方法》
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <pthread.h>
#define THREAD_NUM 2 //并发线程数, 应取决于CPU的核心数
#define INIT_T(n) (100 * (n) * 20) //初始温度, 100*n 为解空间中最大与最小的解的函数值的差值, 20为上述描述中的K
#define T_DOWN_ALPHA 0.5 //温度下降的比例 Tk+1 = Tk * T_DOWN_ALPHA
#define TERM_STEPS 10240 //在一个温度时, 如果迭代步数超过TERM_STEPS, 并且解没有得到改进, 则终止算法
#define LEAST_STEPS_PER_T 1024 //一个温度时, 最少的迭代步数
#define MOST_STEPS_PER_T 10240 //一个温度时, 最多的迭代步数
/* 一个温度时, 接受比率, 如果(接受的迭代次数/总的迭代次数) >= ACCEPT_RATE, 则停止本温度迭代, 并使温度下降 */
#define ACCEPT_RATE 0.8
/* 以上参数均可根据数据规模以及准确度进行调整 */
typedef char (*ROOMS)[61];
struct thread_data_t
{
ROOMS rooms;
double temperature;
int n;
int index;
/* 以上3个字段由主线程传入, 以下4个字段有并发线程返回 */
int iterations; //单个线程中迭代计算的次数
int k;
int m;
};
int stop;
pthread_mutex_t stop_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t stop_cond = PTHREAD_COND_INITIALIZER;
int thread_index;
void InputDataFromFile(char *rooms, int n);
double EvaluateRooms(char rooms[][61], int n);
void ComputeRoomAssignments(char rooms[][61], int n);
void *thread_fun(void *arg);
void PrintRoomAssignmentToFile(ROOMS rooms, int n);
int main(int argc, char *argv[])
{
char buffer[63];
int n;
ROOMS rooms = NULL;
char *mem = NULL;
double first, final;
time_t start, end;
freopen("Students.in", "r", stdin);
fgets(buffer, sizeof buffer, stdin);
n = strlen(buffer);
if (buffer[n - 1] == '\n') {
buffer[n - 1] = '\0';
}
sscanf(buffer, "%d", &n);
mem = (char *)malloc(n * 61);
InputDataFromFile(mem, n);
rooms = (ROOMS)mem;
first = EvaluateRooms(rooms, n);
printf("The initial Disharmony is %lf\n", first);
start = time(NULL);
ComputeRoomAssignments(rooms, n);
end = time(NULL);
printf("Time to compute room assignments is %ld seconds\n", end - start);
final = EvaluateRooms(rooms, n);
printf("Final Disharmony is %lf\n", final);
PrintRoomAssignmentToFile(rooms, n);
return 0;
}
void PrintRoomAssignmentToFile(ROOMS rooms, int n)
{
char buf[11];
int i;
FILE *fp = NULL;
fp = fopen("Assignments.out", "w");
for (i = 0; i < n; i++) {
memcpy(buf, rooms[i], 10);
buf[10] = '\0';
fprintf(fp, "%s\n", buf);
}
fclose(fp);
}
void InputDataFromFile(char *rooms, int n)
{
char *ptr = rooms;
int i;
char buffer[63];
for (i = 0; i < n; i++) {
fgets(buffer, sizeof buffer, stdin);
if (buffer[61] == '\n')
buffer[61] = '\0';
memcpy(ptr, buffer, 61);
ptr += 61;
}
}
double EvaluateRooms(char rooms[][61], int n)
{
double td = 0.0;
int i, j;
for (i = 0; i < n - 1; i += 2) {
for (j = 10; j < 61; j++) {
td += abs((rooms[i][j] - '0') - (rooms[i + 1][j] - '0'));
}
}
td /= 200.0;
return td;
}
void ComputeRoomAssignments(char rooms[][61], int n)
{
char buffer[61];
int i, j, k = -1, m = -1;
pthread_t thread_id[THREAD_NUM];
struct thread_data_t thread_data[THREAD_NUM];
double temperature = INIT_T(n);
int accept_times = 0, total_times, err;
if (n <= 2)
return;
stop = 1;
for (i = 0; i < THREAD_NUM; i++) {
thread_data[i].rooms = rooms;
thread_data[i].n = n;
thread_data[i].k = -1;
thread_data[i].m = -1;
thread_data[i].index = i;
pthread_create(&thread_id[i], NULL, thread_fun, &thread_data[i]);
}
srand(time(NULL));
for (;; temperature *= T_DOWN_ALPHA) { //温度下降循环
total_times = 0;
accept_times = 0;
for (i = 0; i < THREAD_NUM; i++)
thread_data[i].temperature = temperature;
for (i = 0; i < MOST_STEPS_PER_T; i++) { //每个温度的迭代
if (i >= LEAST_STEPS_PER_T) {
if (accept_times * 1.0 / total_times >= ACCEPT_RATE)
break;
}
if ((err = pthread_mutex_lock(&stop_mutex)) != 0) {
printf("pthread_mutex_lock: %s\n", strerror(err));
}
stop = 0;
thread_index = -1;
pthread_cond_broadcast(&stop_cond);
while (!stop && thread_index == -1) {
if ((err = pthread_cond_wait(&stop_cond, &stop_mutex)) != 0) {
printf("pthread_cond_wait: %s\n", strerror(err));
}
}
/* 经过TERM_STEPS次迭代后结果仍没有改进, 则停止计算, 并将结果写入文件 */
/* 此处取消各线程后不必解锁, 因为后续操作不会再去获得该互斥锁 */
if ((k == thread_data[thread_index].k) &&
(m == thread_data[thread_index].m)) {
for (j = 0; j < THREAD_NUM; j++) {
pthread_cancel(thread_id[j]);
}
goto end;
}
accept_times++;
total_times += thread_data[thread_index].iterations;
k = thread_data[thread_index].k;
m = thread_data[thread_index].m;
for (j = 0; j < THREAD_NUM; j++)
thread_data[j].iterations = 0;
if (k < m) {
for (j = k; j < (m - k + 1) / 2 + k; j++) {
memcpy(buffer, rooms[j], sizeof buffer);
memcpy(rooms[j], rooms[m - (j - k)], sizeof buffer);
memcpy(rooms[m - (j - k)], buffer, sizeof buffer);
}
}
else if (k > m) {
for (j = 0; j < (m + 1) / 2; j++) {
memcpy(buffer, rooms[j], sizeof buffer);
memcpy(rooms[j], rooms[m - j], sizeof buffer);
memcpy(rooms[m - j], buffer, sizeof buffer);
}
for (j = k; j < (n - k) / 2 + k; j++) {
memcpy(buffer, rooms[j], sizeof buffer);
memcpy(rooms[j], rooms[n - 1 - j + k], sizeof buffer);
memcpy(rooms[n - 1 - j + k], buffer, sizeof buffer);
}
}
if ( (err = pthread_mutex_unlock(&stop_mutex)) != 0) {
printf("line %d pthread_mutex_unlock: %s\n", __LINE__, strerror(err));
}
}
}
end:
return;
}
void *thread_fun(void *arg)
{
struct thread_data_t *thread_data = (struct thread_data_t *)arg;
int k, m, j, i, t, n = thread_data->n;
int count = 0, err;
double temperature = thread_data->temperature;
double tmp, tmp2;
double delta;
ROOMS rooms = thread_data->rooms;
pthread_detach(pthread_self());
while (1) {
re_rand:
if ((err = pthread_mutex_lock(&stop_mutex)) != 0) {
printf("pthread_mutex_lock: %s\n", strerror(err));
return NULL;
}
if (stop) {
while (stop)
if ((err = pthread_cond_wait(&stop_cond, &stop_mutex)) != 0) {
printf("pthread_cond_wait: %s\n", strerror(err));
return NULL;
}
if ( (err = pthread_mutex_unlock(&stop_mutex)) != 0) {
printf("line %d pthread_mutex_unlock: %s\n", __LINE__, strerror(err));
}
goto re_rand;
}
if ( (err = pthread_mutex_unlock(&stop_mutex)) != 0) {
printf("line %d pthread_mutex_unlock: %s\n", __LINE__, strerror(err));
}
k = rand();
tmp = k * 1.0 / RAND_MAX;
k = (int)(tmp * (n - 1) + 0.5);
m = rand();
tmp = m * 1.0 / RAND_MAX;
m = (int)(tmp * (n - 1) + 0.5);
delta = 0.0;
if (k < m) {
if (!(k % 2) && (m % 2)) {
k++;
if (k == m)
goto re_rand;
}
i = k;
t = m;
if ((k % 2) && !(m % 2)) {
for (j = 10; j < 61; j++) {
delta += abs((rooms[k - 1][j] - '0') - (rooms[k][j] - '0'));
}
for (j = 10; j < 61; j++) {
delta += abs((rooms[m][j] - '0') - (rooms[m + 1][j] - '0'));
}
for (j = 10; j < 61; j++) {
delta -= abs((rooms[k - 1][j] - '0') - (rooms[m][j] - '0'));
}
for (j = 10; j < 61; j++) {
delta -= abs((rooms[k][j] - '0') - (rooms[m + 1][j] - '0'));
}
}
else if ((k % 2) && (m % 2)) {
for (i = k - 1; i <= m - 1; i += 2) {
for (j = 10; j < 61; j++) {
delta += abs((rooms[i][j] - '0') - (rooms[i + 1][j] - '0'));
}
}
for (i = k; i <= m - 2; i += 2) {
for (j = 10; j < 61; j++) {
delta -= abs((rooms[i][j] - '0') - (rooms[i + 1][j] - '0'));
}
}
for (j = 10; j < 61; j++) {
delta -= abs((rooms[k - 1][j] - '0') - (rooms[m][j] - '0'));
}
}
else if (!(k % 2) && !(m % 2)) {
for (i = k; i <= m; i += 2) {
for (j = 10; j < 61; j++) {
delta += abs((rooms[i][j] - '0') - (rooms[i + 1][j] - '0'));
}
}
for (i = k + 1; i <= m - 1; i += 2) {
for (j = 10; j < 61; j++) {
delta -= abs((rooms[i][j] - '0') - (rooms[i + 1][j] - '0'));
}
}
for (j = 10; j < 61; j++) {
delta -= abs((rooms[k][j] - '0') - (rooms[m + 1][j] - '0'));
}
}
}
else if (k > m) {
if (!(k % 2) && (m % 2)) {
m--;
if (m == 0) {
k++;
if (k == n - 1)
goto re_rand;
}
}
if (!(k % 2) && !(m % 2)) {
for (i = 0; i <= m; i += 2) {
for (j = 10; j < 61; j++) {
delta += abs((rooms[i][j] - '0') - (rooms[i + 1][j] - '0'));
}
}
for (i = m; i >= 2; i -= 2) {
for (j = 10; j < 61; j++) {
delta -= abs((rooms[i][j] - '0') - (rooms[i - 1][j] - '0'));
}
}
for (j = 10; j < 61; j++) {
delta -= abs((rooms[0][j] - '0') - (rooms[m + 1][j] - '0'));
}
}
else if ((k % 2) && (m % 2)) {
for (i = k - 1; i <= n - 2; i += 2) {
for (j = 10; j < 61; j++) {
delta += abs((rooms[i][j] - '0') - (rooms[i + 1][j] - '0'));
}
}
for (i = k; i <= n - 3; i += 2) {
for</
|
