Untitled

By Gentle Agouti, ago, written in C++.
URL http://pastecode.org/index.php/view/59145768
Download Paste or View RawExpand paste to full width of browser | Change Viewing Options
  1. Виталий Алексеевич Павленко
  2. Отожги мирных ферзей!(OK)
  3. 13
  4.  
  5. #include <stdio.h>
  6. #include <iostream>
  7. #include <cstdlib>
  8. #include <cmath>
  9.  
  10. using namespace std;
  11.  
  12. const int maxn = 300;
  13. const double T0 = 200;
  14. const double alpha = 0.998;
  15.  
  16. struct solution {
  17.         int a[maxn], cost;
  18. };
  19.  
  20. solution curr, next, best;
  21. double T = T0;
  22. int n;
  23.  
  24. void setcost(solution& curr) {
  25.         curr.cost = 0;
  26.         for(int i = 0; i < n; ++i)
  27.                 for(int j = i + 1; j < n; ++j)
  28.                         if (abs(i - j) == abs(curr.a[i] - curr.a[j]))
  29.                                 curr.cost += 1;
  30. }
  31.  
  32. void setnext(solution& next) {
  33.         next = curr;
  34.         int cnt = n * T / T0 + 1;
  35.         for(int i = 0; i < cnt; ++i) {
  36.                 int rnd1 = int(double(rand()) / RAND_MAX * n), rnd2 = int(double(rand()) / RAND_MAX * n);
  37.                 swap(next.a[rnd1], next.a[rnd2]);
  38.         }
  39.         setcost(next);
  40. }
  41.  
  42. bool admit(int dF) {
  43.         return dF < 0 || exp(double(- dF) / T) > (double(rand()) / RAND_MAX / 2);
  44. }
  45.  
  46. void visualize(solution best) {
  47.         for(int i = 0; i < n; ++i) {
  48.                 for(int j = 0; j < best.a[i]; ++j)
  49.                         cout << ".";
  50.                 cout << "#";
  51.                 for(int j = best.a[i] + 1; j < n; ++j)
  52.                         cout << ".";
  53.                 cout << endl;
  54.         }
  55. }
  56.  
  57. int main() {
  58.  
  59.         cin >> n;
  60.  
  61.         for(int i = 0; i < n; i++)
  62.                 curr.a[i] = i;
  63.  
  64.         setcost(curr);         
  65.         best = curr;
  66.  
  67.         while (best.cost > 0) {
  68.                 setnext(next);
  69.                 if (admit(next.cost - curr.cost)) {
  70.                         curr = next;
  71.                         if (next.cost < best.cost) {
  72.                                 best = next;
  73.                         }
  74.                 }
  75.                 T *= alpha;
  76.         }
  77.  
  78.         for(int i = 0; i < n; ++i)
  79.                 cout << best.a[i] + 1 << " ";
  80.  
  81.         cout << endl;   
  82.  
  83. //      visualize(best);
  84.  
  85.         return 0;
  86. }
  87.  

Here you can reply to the paste above

Make Private

   

Feeling clever? Set some advanced options.