Untitled

Go Back — Change Paste Viewing Options

Виталий Алексеевич Павленко
Отожги мирных ферзей!(OK)
13
 
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
 
using namespace std;
 
const int maxn = 300;
const double T0 = 200;
const double alpha = 0.998;
 
struct solution {
	int a[maxn], cost;
};
 
solution curr, next, best;
double T = T0;
int n;
 
void setcost(solution& curr) {
	curr.cost = 0;
	for(int i = 0; i < n; ++i)
		for(int j = i + 1; j < n; ++j)
			if (abs(i - j) == abs(curr.a[i] - curr.a[j])) 
				curr.cost += 1;
}
 
void setnext(solution& next) {
	next = curr;
	int cnt = n * T / T0 + 1;
	for(int i = 0; i < cnt; ++i) {
		int rnd1 = int(double(rand()) / RAND_MAX * n), rnd2 = int(double(rand()) / RAND_MAX * n);
		swap(next.a[rnd1], next.a[rnd2]);
	}
	setcost(next);
}
 
bool admit(int dF) {
	return dF < 0 || exp(double(- dF) / T) > (double(rand()) / RAND_MAX / 2);
}
 
void visualize(solution best) {
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < best.a[i]; ++j)
			cout << ".";
		cout << "#";
		for(int j = best.a[i] + 1; j < n; ++j)
			cout << ".";
		cout << endl;
	}
}
 
int main() {
 
	cin >> n;
 
	for(int i = 0; i < n; i++)
		curr.a[i] = i;
 
	setcost(curr);		
	best = curr;
 
	while (best.cost > 0) {
		setnext(next);
		if (admit(next.cost - curr.cost)) {
			curr = next;
			if (next.cost < best.cost) {
				best = next;
			}
		}
		T *= alpha;
	}
 
	for(int i = 0; i < n; ++i)
		cout << best.a[i] + 1 << " ";
 
	cout << endl;	
 
//	visualize(best);
 
	return 0;
}
 			

Go Back