Guest User

Untitled

a guest
Jul 17th, 2018
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.88 KB | None | 0 0
  1. #include <algorithm>
  2. #include <numeric>
  3. #include <string>
  4. #include <cstring>
  5. #include <set>
  6. #include <map>
  7. #include <vector>
  8. #include <queue>
  9. #include <iostream>
  10. #include <iterator>
  11. #include <cmath>
  12. #include <cstdio>
  13. #include <cstdlib>
  14. #include <sstream>
  15.  
  16. using namespace std;
  17.  
  18. typedef long long LL;
  19. typedef vector<int> VI;
  20. typedef vector<vector<int> > VVI;
  21. typedef pair<int, int> PII;
  22.  
  23.  
  24. #define FOR(i,x,y) for(LL i=x; i<=y; i++)
  25. #define REP(i,n) for(LL i=0; i<n; i++)
  26.  
  27. #define ALL(c) (c).begin(), (c).end()
  28. #define SORT(c) sort(ALL(c))
  29. #define SZ(c) (int)(c).size()
  30.  
  31. #define pb push_back
  32. #define mp make_pair
  33. #define X first
  34. #define Y second
  35.  
  36.  
  37.  
  38. const double eps = 1.0e-11;
  39. const double pi = acos(-1.0);
  40.  
  41.  
  42. void Print(const vector<double>& x) {
  43. //cout << "(";
  44. REP(i, SZ(x)) {
  45. printf(" %.6llf" + (i == 0), x[i]);
  46. }
  47. printf("\n");
  48. }
  49. vector<double> MakeVector(double x1, double x2) {
  50. vector<double> x(2);
  51. x[0] = x1, x[1] = x2;
  52. return x;
  53. }
  54.  
  55.  
  56.  
  57.  
  58. class Descent {
  59. const double angle;
  60. const double eps;
  61. const double min_derivative_value;
  62. public:
  63. Descent(double ang = 0.0, double e = 0.000001, double mdv = 0.0001) : angle(ang), eps(e), min_derivative_value(mdv) {}
  64. double Himmelblau(const vector<double>& x) {
  65. if (x.size() < 2) {
  66. return 0.0;
  67. }
  68. return pow((x[0] * x[0] + x[1] - 11), 2.0) + 100 * pow(x[0] + x[1] * x[1] - 7, 2.0);
  69. }
  70. double Rosenbrock(const vector<double>& x) {
  71. if (x.size() < 2) {
  72. return 0.0;
  73. }
  74. return pow(1 - x[0], 2.0) + 100 * pow(x[1] - x[0] * x[0], 2.0);
  75. }
  76. double QuadraticForm(const vector<double>& x) {
  77. if (x.size() < 2) {
  78. return 0.0;
  79. }
  80. double rotator[2][2] = {cos(angle), sin(angle), -sin(angle), cos(angle)};
  81. double a[2][2] = {0.1, 0.01, 0.1, 0.5};
  82. double b[2] = {0.0, -0.0};
  83. vector<double> rotated_x(2, 0.0);
  84. REP(i, 2) {
  85. REP(j, 2) {
  86. rotated_x[i] += rotator[i][j] * x[i];
  87. }
  88. }
  89. REP(i, 2) {
  90. REP(j, 2) {
  91. b[i] += a[j][i] * x[i];
  92. }
  93. }
  94. return b[0] * rotated_x[0] + b[1] * rotated_x[1];
  95. }
  96. double UserFunction(double x1, double x2) {
  97. return Rosenbrock(MakeVector(x1, x2));
  98. //return Himmelblau(MakeVector(x1, x2));
  99. //return QuadraticForm(MakeVector(x1, x2));
  100. //return x1 * x1 + x2 * (x2 + 1);
  101. }
  102. double UserFunction(const vector<double>& x) {
  103. return UserFunction(x[0], x[1]);
  104. }
  105. vector<double> Derivative(const vector<double>& x) {
  106. double first = UserFunction(x);
  107. double dx = (UserFunction(x[0] + eps, x[1]) - first) / eps;
  108. double dy = (UserFunction(x[0], x[1] + eps) - first) / eps;
  109. double lenth = sqrt(dx * dx + dy * dy);
  110. vector<double> res = MakeVector(dx / lenth, dy / lenth);
  111. if (abs(res[0]) < min_derivative_value && abs(res[1]) < min_derivative_value) {
  112. return MakeVector(0.0, 0.0);
  113. }
  114. return res;
  115. }
  116. double Dichtomy(const vector<double>& x, const vector<double>& der, double l = -100.0, double r = 100.0) {
  117. double c = (l + r) / 2.0;
  118. double d = c + eps;
  119. if (abs(l - r) < 2 * eps) {
  120. return c;
  121. }
  122. if (UserFunction(x[0] + c * der[0], x[1] + c * der[1]) < UserFunction(x[0] + d * der[0], x[1] + d * der[1])) {
  123. return Dichtomy(x, der, l, c);
  124. } else {
  125. return Dichtomy(x, der, c, r);
  126. }
  127. }
  128. pair<double, vector<double> > FastDescent(const vector<double>& x) {
  129. //if (rand() % 10 == 0)
  130. Print(x);
  131. vector<double> der = Derivative(x);
  132. if (der[0] == 0.0 && der[1] == 0.0) {
  133. return mp(UserFunction(x), x);
  134. }
  135. double best = Dichtomy(x, der);
  136. if (abs(best) < min_derivative_value) {
  137. return mp(UserFunction(x), x);
  138. }
  139. return FastDescent(MakeVector(x[0] + best * der[0], x[1] + best * der[1]));
  140. }
  141. };
  142.  
  143.  
  144. int main() {
  145. //freopen("output.txt", "w", stdout);
  146. Descent test(0.0);
  147. vector<double> d(2, -10.0);
  148. //cout << test.QuadraticForm(d) << endl;
  149. pair<double, vector<double> > res = test.FastDescent(d);
  150. printf("%.5llf\n", res.first);
  151. Print(res.second);
  152. return 0;
  153. }
Add Comment
Please, Sign In to add comment