- •1 РЕФЕРАТ
- •2 НОРМАТИВНЫЕ ССЫЛКИ
- •3 ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ
- •4 ВВЕДЕНИЕ
- •5 ОСНОВНАЯ ЧАСТЬ
- •5.1 Постановка задачи
- •5.1.1 Задача оптимального управления
- •5.1.2 Предположения
- •5.1.3 Уравнение Беллмана
- •5.1.4 Классические характеристики уравнения Беллмана
- •5.1.5 Обобщенное решение уравнения Беллмана
- •5.1.6 Репрезентативная формула функции цены
- •5.1.7 Необходимые и достаточные условия оптимальности
- •5.1.8 Оптимальный синтез
- •5.1.9 Ослабленные предположения
- •5.1.10 Свойства гладкости функции цены
- •5.1.11 Супердифференциал функции цены
- •5.2 Анализ поставленной задачи
- •5.2.1 Алгоритм построения аппроксимации функции цены
- •5.2.2 Оценка численной аппроксимации функции цены
- •5.2.3 Алгоритм построения сеточного оптимального синтеза
- •5.3 Результаты работы
- •5.3.1 Основные функции
- •5.3.2 Примеры численного построения функции цены
- •6 ЗАКЛЮЧЕНИЕ
6 ЗАКЛЮЧЕНИЕ
Разработанная программа может применяться для решения достаточно ши рокого класса задач управления, а также задачи Коши для уравнения Гамиль тона-Якоби-Беллмана для случаев фазового пространства 1, 2, 3. Предпола гается выполненными условия существования, единственности и продолжимости классических характеристик.
Изучена библиотека параллельных вычислений OpenMP. Распараллелены ал горитмы попятного интегрирования и поиска пересечений характеристик.
Получены численные решения ряда модельных задач. Для задач построены оптимальные процессы, функция цены и сеточный оптимальный синтез.
Возможными направлениями развития работы являются повышение размер ности решаемых задач, вопросы оптимального подбора параметров, а также оп тимизация программы по времени счета.
Поставленная задача решена полностью.
84
Благодарности
Работа выполнена при финансовой поддержке Российского фонда фундамен тальных исследований (проект №11–01–00214).
85
7 СПИСОК ИСПОЛЬЗОВАННЫХ
ИСТОЧНИКОВ
1.Subbotina N. N. The method of characteristics for Hamilton–Jacobi equations and applications to dynamical optimization. NY: Springer, 2006. Vol. 135. Pp. 2955–3091.
2.www.gnu.org/software/gsl.
3.www.cgal.org.
4.www.openmp.org.
5.Понтрягин Л. С., Болтянский В. Г., Гамкрелидзе Р. В., Мищенко Е. Ф. Мате матическая теория оптимальных процессов. Москва: Наука, 1961.
6.Bellman R. Dynamic Programming. Princeton: Univ. Press, 1957.
7.Красовский Н. Н. Теория управления движением. Москва: Наука, 1968.
8.Красовский Н. Н., Субботин А. И. Позиционные дифференциальные игры. Москва: Наука, 1974.
9.Петровский И. Г. Лекции по теории обыкновенных дифференциальных урав нений. Москва: Изд–во МГУ, 1984.
10.Курант Р. Уравнения с частными производными. Москва: Мир, 1964.
11.Clarke F. H., Vinter R. The relationship between the maximum principle and dynamic programming // S.I.A.M. J. Contr. Optimiz. 1987. Vol. 5. Pp. 1291–1311.
12.Barron E. N., Jensen R. The Pontryagin maximum principle from dynamic pro gramming and viscosity solutions to first–order partial differential equations // Trans. Amer. Math. Soc. 1986. Vol. 298, no. 2. Pp. 635–641.
86
13.Mirica S. Extending Cauchy’s method of characteristics for Hamilton–Jacobi equa tions // Stud. Cerc. Mat. 1985. Vol. 37, no. 6. Pp. 555–565.
14.Субботин А. И. Обобщенные решения уравнений в частных производных пер вого порядка. Перспективы динамической оптимизации. Москва; Ижевск: Ин ститут компьютерных исследований, 2003.
15.Crandall M. G., Lions P. L. Viscosity solutions of Hamiltion–Jacobi equations // Trans. Amer. Math. Soc. 1983. Vol. 277. Pp. 1–42.
16.Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Москва: Мир, 1989.
17.Crandall M. G., Lions P.-L. Viscosity Solutions of Hamilton–Jacobi Equations // Trans. Am. Math. Soc. 1983. Vol. 277:1. Pp. 1–42.
18.Филиппов А. Ф. О некоторых вопросах теории оптимального регулирова ния // Вестник Моск. Ун.-та. 1959. № 2. С. 25–32.
19.Болтянский В. Г. Математические методы оптимального управления. Москва: Наука, 1969.
20.Пацко В. С. Поверхности переключения в линейных дифференциальных иг рах. Екатеринбург: ИММ УрО РАН, 2004.
21.Субботина Н. Н. Обобщенный метод характеристик в задаче оптимального управления с липшицевыми входными данными // Изв. УрГУ: Математика и механика. 2006. Т. 4. С. 171–176.
22.Токманцев Т. Б. Обобщенный метод характеристик в решении задач опти мального управления с фиксированным моментом окончания: Кандидатская диссертация / ИММ УрО РАН. Екатеринбург, 2011.
87
23.Шолохович Ф. А. Лекции по дифференциальным уравнениям. Екатеринбург: Уральское изд–во, 2005.
24.Варга Д. Оптимальное управление дифференциальными и функциональными уравнениями. Москва: Наука, 1977.
25.Филиппов А. Ф. Дифференциальные уравнения с разрывной правой частью. Москва: Наука, 1985.
88
8 ПРИЛОЖЕНИЕ
//MAIN.CPP
#include "Problem2.h" #include "TSynthes2.h" #include <iostream> #include <time.h>
int main()
{
std::cout <<"Problem - "<<ProblemName<<std::endl <<"Np = "<<NP<<std::endl;
time_t start, end; time(&start);
TBuilder2 :: TPointer VF = Construct(); std::ostringstream DirName;
DirName << "var_" <<ProblemName; system((string("mkdir ") + DirName.str()).c_str()); VF->Instant2Files(DirName.str());
time(&end);
double Time_Clock = difftime(end,start); std::cout<<Time_Clock<<std::endl
<<"Construct completed"<<std::endl; time(&start);
TSynthes2 S(VF); S.BuildTrajectories(SynthesGrid); S.Instant2Files(DirName.str()); S.Instant2MatlabFile(DirName.str()); time(&end);
Time_Clock = difftime(end,start); std::cout<<Time_Clock<<std::endl
<<"Synthes completed"<<std::endl;
return 0;
}
//PROBLEM2.H #pragma once #include <math.h> #include "TBuilder2.h" #include "TFactory2.h"
#include "Definitions2.h"
using namespace std;
namespace SpherPendulum{
extern std::string |
ProblemName; |
const double |
Eps = 1e-4; |
const double |
dt = 0.05; |
const double |
dx = 0.2;//dt*dt; |
const double |
rho = 0; |
const double |
T = 1; |
//extern double |
U; |
const Vector2 |
x1(0,-5), |
|
x2(0,5); |
vector<Vector2> CreateGrid(); extern vector<Vector2> SynthesGrid;
const int XNum = static_cast<int>((x2.x() - x1.x()) / dx); const int TNum = static_cast<int>(T / dt);
double Sigma(const Vector2 &); Vector2 DxSigma(const Vector2 &); int RHS(
89
double tau, const double y[], double result[], void *params
);
double Control(const double t, const Vector2 &x, const Vector2 &p);
Vector2 SynthesControl(const double t, const Vector2 &Point, const Vector2 &Target);
Vector2 f(const double t, const Vector2 &x, const Vector2 &u);//вторая координата u фиктивна double g(const double t, const Vector2 &x, const Vector2 &u);//вторая координата u фиктивна
} |
|
namespace Didona{ |
|
extern std::string |
ProblemName; |
const double |
Eps = 1e-4; |
const double |
dt = 0.1; |
const double |
dx = 0.5;//dt*dt; |
const double |
rho = 0; |
const double |
T = 1; |
//extern double |
U; |
const Vector2 |
x1(-1,-1), |
|
x2(1,1); |
vector<Vector2> CreateGrid(); extern vector<Vector2> SynthesGrid;
const int XNum = static_cast<int>((x2.x() - x1.x()) / dx); const int TNum = static_cast<int>((T+Eps) / dt);
double Sigma(const Vector2 &); Vector2 DxSigma(const Vector2 &); int RHS(
double tau, const double y[], double result[], void *params
);
Vector2 Control(const double t, const Vector2 &x, const Vector2 &p);
Vector2 SynthesControl(const double t, const Vector2 &Point, const Vector2 &Target); Vector2 f(const double t, const Vector2 &x, const Vector2 &u);
double g(const double t, const Vector2 &x, const Vector2 &u);
}
namespace GravityProblem{
static double v_T = -98.0;//!!!
extern std::string |
ProblemName; |
const double |
Eps = 1e-4; |
const double |
dt = 0.1; |
const double |
dx = dt*dt; |
const double |
rho = 0; |
const double |
T = 10; |
extern double |
U; |
const Vector2 |
x1(-1e-1, v_T - 1e-1), |
x2( 1e-1, v_T + 1e-1); const int XNum = static_cast<int>((x2.x() - x1.x()) / dx); const int TNum = static_cast<int>(T / dt);
double y(const double t);
double Integrant(const double t, const Vector2 &x, const double u); double Control(const double t, const Vector2 &x, const Vector2 &p);
Vector2 f(const double t, const Vector2 &x, const Vector2 &p, const double u); double g(const double t, const Vector2 &x, const Vector2 &p, const double u); const Vector2 h(const double t, const Vector2 &x, const Vector2 &p);
90
double Sigma(const Vector2 &); Vector2 DxSigma(const Vector2 &); int RHS(
double tau, const double y[], double result[], void *params
);
}
using namespace SpherPendulum;
TBuilder2 :: TPointer Construct();
//PROBLEM2.CPP
#include"Problem2.h"
#define _USE_MATH_DEFINES #include "math.h"
double sqr(const double x){ return x*x;
}
namespace SpherPendulum
{
vector<Vector2> SynthesGrid; vector<Vector2> CreateGrid()
{
vector<Vector2> result; for(int j = 0; j <= XNum; ++j)
{
const Vector2 y(0, x1.y() + j * dx); result.push_back(y);
}
return result;
}
std::string ProblemName = "Pendulum"; const double grav = 9.8;
double Control(const double t, const Vector2 &x, const Vector2 &p)
{
double u0 = -p.y()*sin(x.x())/Eps; if(abs(u0) <= 1)
return u0; return u0/abs(u0);
}
Vector2 SynthesControl(const double t, const Vector2 &Point, const Vector2 &Target)
{
Vector2 p = Target - Point; if(p.y()*sin(Point.x()) < 0)
return Vector2(-1,0); //вторая координата фиктивна
else
return Vector2(1,0);
}
Vector2 f(const double t, const Vector2 &x, const Vector2 &u)//вторая координата u фиктивна
{
return Vector2(x.y(),(-grav+u.x())*sin(x.x())+2*sin(2*x.x()));
}
double g(const double t, const Vector2 &x, const Vector2 &u)//вторая координата u фиктивна
{
return Eps*u.x()*u.x()/2;
}
const Vector2 h(const double t, const Vector2 &x, const Vector2 &p, const double &u)
{
91
return Vector2(p.y()*((-grav+u)*cos(x.x())+4*cos(2*x.x())), p.x());
}
double Sigma(const Vector2 &x)
{
return x.x()*x.x()/2;
}
Vector2 DxSigma(const Vector2 &x)
{
return Vector2(x.x(),0);
}
int RHS( double tau,
const double y[], double result[], void *params
){
double t = T - tau;
Vector2 x = Vector2(y[0], y[1]); Vector2 p = Vector2(y[2], y[3]); const double u = Control(t,x,p); Vector2 X = f(t,x,Vector2(u,0)); Vector2 P = h(t,x,p,u);
result[0] = -X.x(); result[1] = -X.y(); result[2] = P.x(); result[3] = P.y();
result[4] = g(t,x,Vector2(u,0)); return GSL_SUCCESS;
}
}
namespace Didona
{
vector<Vector2> SynthesGrid; vector<Vector2> CreateGrid()
{
vector<Vector2> result; for(int i = 0; i <= XNum; ++i)
{
for(int j = 0; j <= XNum; ++j)
{
const Vector2 y(x1.x() + i * dx, x1.y() + j * dx); result.push_back(y);
}
}
return result;
}
std::string ProblemName = "Didona";
Vector2 Control(const double t, const Vector2 &x, const Vector2 &p)
{
Vector2 u0(-(p.x()-x.y())/Eps,-(p.y()+x.x())/Eps); double l2 = u0.squared_length();
if(l2 <= 1)
return u0; return u0/sqrt(l2);
}
Vector2 SynthesControl(const double t, const Vector2 &Point, const Vector2 &Target)
{
double l = sqrt((Target-Point).squared_length()); return (Target-Point)/l;
}
Vector2 f(const double t, const Vector2 &x, const Vector2 &u)
{
92
return u;
}
double g(const double t, const Vector2 &x, const Vector2 &u)
{
return (x.x()*u.y() - x.y()*u.x()) + Eps*u.squared_length()/2;
}
const Vector2 h(const double t, const Vector2 &x, const Vector2 &p, const Vector2 &u)
{
return Vector2(u.y(), -u.x());
}
double Sigma(const Vector2 &)
{
return 0;
}
Vector2 DxSigma(const Vector2 &x)
{
return Vector2(0,0);
}
int RHS( double tau,
const double y[], double result[], void *params
){
double t = T - tau;
Vector2 x = Vector2(y[0], y[1]); Vector2 p = Vector2(y[2], y[3]); const Vector2 u = Control(t,x,p); Vector2 X = f(t,x,u);
Vector2 P = h(t,x,p,u); result[0] = -X.x(); result[1] = -X.y(); result[2] = P.x(); result[3] = P.y(); result[4] = g(t,x,u); return GSL_SUCCESS;
}
}
namespace GravityProblem
{
std::string ProblemName = "GravityProblem";
double U = 10;
double y(const double t)
{
const double g = 9.8;
const double h0 = g*10*10/2; return -g*t*t/2 + h0;
}
double Control(const double t, const Vector2 &x, const Vector2 &p)
{
double u0 = -p.y()/Eps; if(fabs(u0) < U)
return u0;
double H1 = p.x()*x.y() + p.y()*U + Integrant(t,x,U); double H2 = p.x()*x.y() + p.y()*(-U) + Integrant(t,x,-U); return H1 < H2 ? U:-U;
}
Vector2 f(const double t, const Vector2 &x, const Vector2 &p, const double u)
{
return Vector2(x.y(),u);
93
}
double Integrant(const double t, const Vector2 &x, const double u)
{
return sqr(x.x() - y(t))/2 + u*u*Eps/2;
}
double g(const double t, const Vector2 &x, const Vector2 &p, const double u)
{
return Integrant(t,x,u);
}
const Vector2 h(const double t, const Vector2 &x, const Vector2 &p)
{
return Vector2(x.x() - y(t), p.x());
}
double Sigma(const Vector2 &)
{
return 0;
}
Vector2 DxSigma(const Vector2 &x)
{
return Vector2(0,0);
}
int RHS(
double tau, const double y[], double result[], void *params
)
{
double t = T - tau;
Vector2 x = Vector2(y[0], y[1]); Vector2 p = Vector2(y[2], y[3]); const double u = Control(t,x,p); Vector2 X = f(t,x,p,u);
Vector2 P = h(t,x,p); result[0] = -X.x(); result[1] = -X.y(); result[2] = P.x(); result[3] = P.y(); result[4] = g(t,x,p,u); return GSL_SUCCESS;
}
}
TBuilder2 :: TPointer Construct()
{
vector<Vector2> Grid = CreateGrid(); SynthesGrid.clear();
for(int i = 0; i <= 2*XNum; ++i)
{
for(int j = 0; j <= 2*XNum; ++j)
{
const Vector2 y(x1.x() + i * dx/2, x1.y() + j * dx/2); SynthesGrid.push_back(y);
}
}
TFactory2 Factory(dt);
TSection2 Section = Factory.Create(T, Grid, Sigma, DxSigma, rho); TBuilder2 Builder(Section);
std::cout<<"0 ";
for(int i = 1; i <= TNum; ++i)
{
std::cout<<i<<endl<<" ";
94
Section = Factory.Create(Section); Builder.AddSection(Section);
}
return Builder.Get();
}
// TSynthes2.h #pragma once #include <assert.h>
#include "TValueFunction2.h" #include "Problem2.h" #include "TBuilder2.h"
#include <CGAL/Delaunay_triangulation_2.h>
#include <CGAL/Triangulation_vertex_base_with_info_2.h>
typedef CGAL::Triangulation_vertex_base_with_info_2<size_t, K> Vb;
typedef CGAL::Triangulation_data_structure_2<Vb> |
Tds; |
typedef CGAL::Delaunay_triangulation_2<K, Tds> |
Triangulation; |
typedef Triangulation::Point Point; |
|
class TSynthes2
{
public:
TSynthes2(const TBuilder2 :: TPointer VF); void BuildTriang();
Vector2 GetNearestPoint(size_t t, const Vector2 &Point);
Vector2 Aim(size_t t, const Vector2 &Point, const Vector2 &Target, Vector2 &u); void BuildTrajectory(Vector2 Point);
void BuildTrajectories(const vector<Vector2> &Array); void Instant2Files(const string &DirName);
void Instant2MatlabFile(const string &DirName);
private:
vector<Triangulation> Triangs; TBuilder2 :: TPointer VF; vector<vector<Vector2> > Trajectories; vector<vector<Vector2> > UControls; vector<double> Values;
};
//TSYNTHES2.CPP #include "TSynthes2.h" #include <omp.h>
void TSynthes2::BuildTriang()
{
#pragma omp parallel for num_threads(NP) for(int t = 0; t < TNum; ++t)
{
vector<Vector2> Array = VF->GetSectionPoints(t); std::vector< std::pair<Point,size_t> > points; for(size_t i=0; i < Array.size();++i)
points.push_back( std::make_pair(CGAL::ORIGIN+Array[i],i) ); Triangulation Triang;
Triang.insert( points.begin(),points.end() ); Triangs[t] = Triang;
}
}
TSynthes2::TSynthes2(const TBuilder2 :: TPointer _VF) :VF(_VF),Triangs(TNum){}
Vector2 TSynthes2::GetNearestPoint(size_t t, const Vector2 &Point)
95
{
Triangulation::Vertex_handle Vertex = Triangs[t].nearest_vertex(CGAL::ORIGIN+Point); return VF->GetSectionPoints(t+1)[Vertex->info()];
}
Vector2 TSynthes2::Aim(size_t t, const Vector2 &Point, const Vector2 &Target, Vector2 &u)
{
assert(t < TNum); if(Point == Target)
u = Vector2(0,0);
else
u = SynthesControl(t*dt, Point, Target); return f(t*dt, Point, u);
}
void TSynthes2::BuildTrajectory(Vector2 Point)
{
Vector2 Target; Vector2 Velocity;
vector<Vector2> Trajectory; vector<Vector2> UControl; double Value=0;
Vector2 u; Trajectory.push_back(Point); for(size_t i = 0; i < TNum; ++i)
{
Target = GetNearestPoint(i,Point); Velocity = Aim(i, Point, Target, u); UControl.push_back(u); Value+=g(i*dt,Point,u);
Point = Point + Velocity * dt; Trajectory.push_back(Point);
}
Value-=g(0,Trajectory[0],UControl[0])/2; Value-=g(T,Trajectory[TNum],UControl[TNum-1])/2; Value*=dt;
Value+=Sigma(Point); Values.push_back(Value); Trajectories.push_back(Trajectory); UControl.push_back(Vector2(0,0)); UControls.push_back(UControl);
}
void TSynthes2::BuildTrajectories(const vector<Vector2> &Array)
{
BuildTriang();
for(size_t i = 0; i < Array.size(); ++i)
{
std::cout<<i<<endl;
BuildTrajectory(Array[i]);
}
}
void TSynthes2::Instant2Files(const string &DirName)
{
assert(!Trajectories.empty());
unsigned int Size = Trajectories[0].size(); for(unsigned int t = 0; t < Size; ++t){
ostringstream FileName;
FileName << DirName+"/s_" << t << ".txt"; ofstream Out(FileName.str().c_str());
Out << 3 << " " << Trajectories.size() << endl;
96
for(unsigned int k = 0; k < Trajectories.size(); ++k){ Out << Trajectories[k][t].x() << " ";
Out << Trajectories[k][t].y() << " "; Out << UControls[k][t].x() << " "; Out << UControls[k][t].y() << " "; Out << Values[k] << endl;
}
Out.close();
}
}
void TSynthes2::Instant2MatlabFile(const string &DirName)
{
ostringstream FileName;
FileName << DirName<<"_Synthes.m"; ofstream MatlabFile(FileName.str().c_str());
unsigned int Size = Trajectories[0].size(); |
|
|
MatlabFile << "X1 = zeros(" << Trajectories.size() |
<< ", " << Size << ");\n"; |
|
MatlabFile << "X2 = zeros(" << Trajectories.size() |
<< ", " << Size << ");\n"; |
|
MatlabFile << "U1 = zeros(" << UControls.size() |
<< ", " << Size << ");\n"; |
|
MatlabFile << "U2 = zeros(" << UControls.size() |
<< ", " << Size << ");\n"; |
|
MatlabFile << "Z |
= zeros(" << Trajectories.size() |
<< ", 1);\n"; |
MatlabFile << "for t=1:" << Size << ";\n"; |
|
|
MatlabFile << " Name = strcat('"+DirName+"/s_',num2str(t-1));\n"; |
||
MatlabFile << " Name = strcat(Name,'.txt');\n"; |
|
|
MatlabFile << " |
File = fopen(Name, 'r');\n"; |
|
MatlabFile << " |
fscanf(File,'%d',1);\n"; |
|
MatlabFile << " N = fscanf(File,'%d',1);\n"; |
|
|
MatlabFile << " |
for i=1:N;\n"; |
|
MatlabFile << " |
X1(i,t) = fscanf(File,'%g',1);\n"; |
|
MatlabFile << " |
X2(i,t) = fscanf(File,'%g',1);\n"; |
|
MatlabFile << " |
U1(i,t) = fscanf(File,'%g',1);\n"; |
|
MatlabFile << " |
U2(i,t) = fscanf(File,'%g',1);\n"; |
|
MatlabFile << " |
Z(i) = fscanf(File,'%g',1);\n"; |
|
MatlabFile << " |
end\n"; |
|
MatlabFile << " |
fclose(File);\n"; |
|
MatlabFile << "end\n";
MatlabFile << "figure(1);\n";
MatlabFile << "Time = 0 : "<<dt<<" : "<<T<<";\n";
MatlabFile << "hold on;\n";
MatlabFile << "for i=1:N;\n";
MatlabFile << "\tplot3(Time, X1(i,:), X2(i,:));\n";
MatlabFile << "end\n";
MatlabFile << "xlabel('t');\n";
MatlabFile << "ylabel('x_1');\n";
MatlabFile << "zlabel('x_2');\n";
MatlabFile << "figure(2);\n";
MatlabFile << "Time = 0 : "<<dt<<" : "<<T-dt<<";\n"; MatlabFile << "hold on;\n";
MatlabFile << "for i=1:N;\n";
MatlabFile << "\tplot3(Time, U1(i,1:"<<Size-1<<"), U2(i,1:"<<Size-1<<"));\n"; MatlabFile << "end\n";
MatlabFile << "xlabel('t');\n"; MatlabFile << "ylabel('u_1');\n"; MatlabFile << "zlabel('u_2');\n";
MatlabFile << "figure(3);\n";
MatlabFile << "Triang = delaunay(X1(:,1),X2(:,1));\n";
97
MatlabFile << "trimesh(Triang,X1(:,1),X2(:,1),Z(:));\n"; MatlabFile << "xlabel('x_1');\n";
MatlabFile << "ylabel('x_2');\n"; MatlabFile << "zlabel('S');\n";
}
// TBuilder2.h #pragma once
#include "TValueFunction2.h" #include "Tree2.h"
#include "../Include/Tree.h" #include "TFactory2.h"
#include <boost/tr1/memory.hpp>
class TBuilder2
{
public:
typedef std::tr1::shared_ptr<TValueFunction2> TPointer; TBuilder2(TSection2 &Section);
TPointer Get();
void AddSection(TSection2 &);
private:
bool FirstTime; TTree Times;
vector<TTree2> Trajectories; vector<TTree> Values; TPointer Ptr;
};
//TBUILDER2.CPP #include "TBuilder2.h"
TBuilder2::TBuilder2(TSection2 &Section) : Times(Section.Time())
{
const vector<Vector2> &X = Section.GetX(); const vector<double> &Z = Section.GetZ(); for(unsigned int i = 0; i < X.size(); ++i)
{
Trajectories.push_back(TTree2(X[i])); Values.push_back(TTree(Z[i]));
}
}
void TBuilder2::AddSection(TSection2 &Section)
{
Section.Formula();
const vector<Vector2> &X = Section.GetX(); const vector<double> &Z = Section.GetZ(); Times.Grow(Section.Time());
for(unsigned int i = 0; i < X.size(); ++i){ Trajectories[i].Grow(X[i]); Values[i].Grow(Z[i]);
}
}
TBuilder2::TPointer TBuilder2::Get()
{
TValueFunction2 * tmp = new TValueFunction2( Times,
98
Trajectories, Values
);
Ptr = TPointer(tmp); return Ptr;
}
//TFACTORY2.H #pragma once
#include "Definitions2.h" #include "TSection2.h" #include "TValueFunction2.h" #include <gsl/gsl_odeiv.h> #include <gsl/gsl_errno.h> #include <gsl/gsl_matrix.h> #include <vector>
using std :: vector;
class TFactory2
{
public:
TFactory2(double _dt); virtual ~TFactory2(void);
TSection2 Create(const TSection2&); TSection2 Create(
const double t,
const vector<Vector2> &X, TBoundaryFunction2 Sigma, TGradientFunction2 DxSigma, const double rho
);
private:
double dt;
};
//TFACTORY2.CPP #include "TFactory2.h" #include "Problem2.h" #include <assert.h> #include <algorithm> using std::transform;
TFactory2::TFactory2(double _dt) :dt(_dt)
{
}
TFactory2::~TFactory2(void){
}
void Integrate(
const double tau1, const double tau2, vector<double> &Y
){
assert(tau1 < tau2);
int Dimension = Y.size(); double *y = &Y[0]; double y_err[16],
dydt_in[16], dydt_out[16];
gsl_odeiv_system sys = { RHS, NULL, Dimension};
99
const gsl_odeiv_step_type *T = gsl_odeiv_step_rk8pd; gsl_odeiv_step * const s = gsl_odeiv_step_alloc(T, Dimension);
GSL_ODEIV_FN_EVAL (&sys, tau1, y, dydt_in);
const double h = 2E-5; double tau = tau1; while (tau < tau2){
int status = gsl_odeiv_step_apply (
s, tau, h, y, y_err, dydt_in, dydt_out, &sys
);
assert (status == GSL_SUCCESS); for(size_t i = 0; i < Dimension; ++i)
{
dydt_in[i] = dydt_out[i];
}
tau += h;
}
gsl_odeiv_step_free(s);
}
#include <time.h> #include <omp.h>
TSection2 TFactory2::Create(const TSection2 &Section){ vector<Vector2> X = Section.GetX(),
P = Section.GetP(); vector<double> Z = Section.GetZ();
double t2 = Section.Time(), t1 = t2 - dt;
int Size = static_cast<int>(X.size()); #pragma omp parallel for num_threads(NP) for(int i = 0; i < Size; ++i)// omp требует int
{
assert(omp_get_num_threads() <= omp_get_num_procs()); assert(omp_get_num_threads() == NP);
vector<double> Y(5); Y[0] = X[i].x();
Y[1] = X[i].y();
Y[2] = P[i].x();
Y[3] = P[i].y(); Y[4] = Z[i];
Integrate(T-t2, T-t1, Y); X[i] = Vector2(Y[0], Y[1]); P[i] = Vector2(Y[2], Y[3]); Z[i] = Y[4];
}
return TSection2(t1, X, P, Z, Section.GetRho());
}
TSection2 TFactory2::Create( const double t,
const vector<Vector2> &X, TBoundaryFunction2 Sigma, TGradientFunction2 DxSigma, const double rho
){
vector<Vector2> P; vector<double> Z;
transform(X.begin(), X.end(), back_inserter(P), DxSigma); transform(X.begin(), X.end(), back_inserter(Z), Sigma); return TSection2(t, X, P, Z, rho);
}
100
//DEFINITIONS.H #pragma once
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h> #include <vector>
using std :: vector; using std :: pair;
struct K : CGAL::Exact_predicates_inexact_constructions_kernel{}; typedef K::Vector_2 Vector2;
typedef Vector2(*TGradientFunction2)(const Vector2&); typedef double (*TBoundaryFunction2)(const Vector2&);
//typedef Vector2(*TFunction2)(const Vector2&, const Vector2&); typedef pair< vector<size_t>::iterator, vector<size_t>::iterator > TRange;
//TREE.H #pragma once #include <deque>
#include <iostream> #include <iomanip> #include <algorithm> #include <string> using std :: deque; using std :: istream; using std :: ostream; using std :: ofstream; using std :: endl; using std :: string;
class TTree{ public:
TTree(const double Root)
:_Branches(1, Root), _Root(_Branches.back()), _Stop(false){
}
TTree(const TTree &Tree) :_Root(Tree._Root),_Branches(Tree._Branches), _Stop(false){
}
TTree(istream &In);
TTree operator = (const TTree &Tree); void Save(ostream &Out) const;
void SaveTo(const string &FileName)const; bool operator <(const TTree &Tree) const; bool operator ==(const TTree &Tree) const; bool operator !=(const TTree &Tree) const;
const double& operator [](const size_t i) const{return _Branches[i];} bool IsCorrect();
bool Empty(){return _Branches.empty();} size_t Size(){return _Branches.size();} void Grow(const double);
void Stop();
private:
deque<double> _Branches; double _Root;
bool _Stop;
};
ostream& operator << (ostream &Out, const TTree &Tree);
//TREE.CPP
#include"Tree.h"
101
#include<assert.h>
#include<string>
#include<iostream>
#include<fstream> using std :: ofstream; using std :: string;
TTree TTree::operator = (const TTree &Tree){
_Branches = Tree._Branches; _Root = _Branches.back(); _Stop = Tree._Stop;
return *this;
}
void TTree::Save(ostream &Out) const{ //Out << "Trajectory = [" << endl;
for(unsigned int i = 0; i < _Branches.size(); ++i){
Out << ' ' << std :: fixed << std :: setprecision(20) << _Branches[i];
}
}
bool TTree::operator <(const TTree &Tree) const{ return _Root < Tree._Root;
}
void TTree::Grow(const double Branch){ if(!_Stop){
_Branches.push_front(Branch);
}
}
void TTree::Stop(){ _Stop = true;
}
bool TTree::operator ==(const TTree &Tree) const{
return !(_Root < Tree._Root) && !(Tree._Root < _Root) && (_Branches.size() == Tree._Branches.size());
}
bool TTree::operator !=(const TTree &Tree) const{ return !(*this == Tree);
}
bool TTree::IsCorrect(){
//?=> Уникальность корней return _Root == _Branches.back();
}
const deque<double> Split(const string &S){ std :: deque<double> Result;
std :: string::size_type PrevPos = 0;
while(true){
std :: string::size_type Pos = S.find(' ', PrevPos);
std :: string Number = S.substr(PrevPos, Pos - PrevPos);
PrevPos = Pos + 1; Result.push_back(atof(Number.c_str())); if(Pos == std :: string :: npos){
break;
}
}
return Result;
}
ostream& operator << (ostream &Out, const TTree &Tree){ Tree.Save(Out);
return Out;
102
}
TTree::TTree(istream &In)
{
std :: string Branches; In.ignore(100, '['); In.ignore(); //' ' getline(In, Branches);
assert(!Branches.empty()); _Branches = Split(Branches); _Root = _Branches.back();
}
void TTree::SaveTo(const string &FileName)const{
ofstream File(FileName.c_str(), std::ios::out|std::ios::binary ); double *Buf = new double [_Branches.size()]; copy(_Branches.begin(), _Branches.end(), Buf);
const char * Buffer = reinterpret_cast<const char*>(&Buf[0]); unsigned int Size = _Branches.size() * sizeof(Buf[0]); File.write(Buffer, Size);
File.close(); delete [] Buf;
}
//TREE2.H #pragma once #include <deque> #include <iostream> #include <iomanip>
#include <algorithm> #include <string> #include <vector> #include "Definitions2.h" using std :: deque;
using std :: istream; using std :: ostream; using std :: ofstream; using std :: endl; using std :: string;
class TTree2
{
public:
TTree2(const Vector2& Root) :_Branches(1, Root){
}
TTree2(const TTree2 &Tree) :_Branches(Tree._Branches){
}
TTree2 operator = (const TTree2 &Tree); void Save(ostream &Out) const;
void SaveTo(const string &FileName)const; bool operator ==(const TTree2 &Tree) const; bool operator !=(const TTree2 &Tree) const;
const Vector2& operator [](const size_t i) const{return _Branches[i];} void Grow(const Vector2&);
inline unsigned int Size(){return _Branches.size();}
friend ostream& operator << (ostream &Out, const TTree2 &Tree); Vector2 GetBranche(size_t i) const {return _Branches[i];}
private:
deque<Vector2> _Branches;
};
//TREE2.CPP
103
#include "Tree2.h" #include <assert.h> #include <string> #include <iostream> #include <fstream> using std :: ofstream; using std :: string;
using std :: ostream_iterator;
TTree2 TTree2::operator = (const TTree2 &Tree){ _Branches = Tree._Branches;
return *this;
}
void TTree2::Save(ostream &Out) const{ //Out << "Trajectory = [" << endl;
for(unsigned int i = 0; i < _Branches.size(); ++i){
Out << ' ' << std :: fixed << std :: setprecision(20) << _Branches[i];
}
}
void TTree2::Grow(const Vector2& Branch){ _Branches.push_front(Branch);
}
bool TTree2::operator ==(const TTree2 &Tree) const
{
return _Branches.size() == Tree._Branches.size();
}
bool TTree2::operator !=(const TTree2 &Tree) const
{
return !(*this == Tree);
}
ostream& operator << (ostream &Out, const TTree2 &Tree){ Tree.Save(Out);
return Out;
}
void TTree2::SaveTo(const string &FileName)const{ const size_t Size = 2*_Branches.size();
ofstream File(FileName.c_str(), std::ios::out|std::ios::binary ); double *Buf = new double [Size];
size_t i = 0;
for(deque<Vector2>::const_iterator it = _Branches.begin(); it != _Branches.end(); ++it)
{
Buf[i++] = it->x(); Buf[i++] = it->y();
}
const char * Buffer = reinterpret_cast<const char*>(&Buf[0]); File.write(Buffer, Size * sizeof(Buf[0]));
File.close(); delete [] Buf;
}
//TSECTION2.H #pragma once #include<vector> #include<iostream> #include "Definitions2.h"
#include "../Include/Functions.h" #include <time.h>
#include <omp.h> using std :: vector; using std :: ostream;
104
using std :: pair;
using std :: make_pair;
#include <CGAL/Delaunay_triangulation_2.h>
#include <CGAL/Triangulation_vertex_base_with_info_2.h>
const int NP = 2;
class TSection2{
friend ostream& operator<< (ostream &, const TSection2&);
public:
//TSection2(void);
TSection2(
const double,
const vector<Vector2>&, const vector<Vector2>&, const vector<double>&, const double _rho
);
const vector<Vector2>& GetX() const; const vector<Vector2>& GetP() const; const vector<double>& GetZ() const;
const TSection2& operator = (const TSection2&); bool operator == (const TSection2&) const; double Time()const{return t;}
void Formula();
const double GetRho()const{return Rho;}
private:
double t; vector<Vector2> X; vector<Vector2> P; vector<double> Z; const double Rho;
typedef CGAL::Triangulation_vertex_base_with_info_2<size_t, K> Vb;
typedef CGAL::Triangulation_data_structure_2<Vb> |
Tds; |
|
typedef CGAL::Delaunay_triangulation_2<K, Tds> |
|
Triangulation; |
typedef Triangulation::Point |
Point; |
|
Triangulation Triangulate(); void FindIntersectionAndMin();
void FindIntersectionAndMin(Triangulation &T);
};
//TSECTION2.CPP #include "TSection2.h"
#include "../Include/Functions.h" #include <math.h> #include<algorithm>
#include <map> #include <functional>
using std :: map; using std :: fill; using std :: swap;
using std :: mem_fun_ref;
ostream& operator<< (ostream &Out, const TSection2 &Section){ Out << "t = " << Section.Time() << '\n';
Out << "X = [\n";
Out << Section.GetX(); Out << "]\n";
Out << "P = [\n";
105
Out << Section.GetP(); Out << "]\n";
Out << "Z = [\n";
Out << Section.GetZ(); Out << "]\n";
return Out;
}
TSection2::TSection2( const double _t,
const vector<Vector2>& _X, const vector<Vector2>& _P, const vector<double>& _Z, const double _Rho
)
:t(_t), X(_X), P(_P), Z(_Z), Rho(_Rho)
{}
const vector<Vector2>& TSection2::GetX()const{ return X;
}
const vector<Vector2>& TSection2::GetP()const{ return P;
}
const vector<double>& TSection2::GetZ()const{ return Z;
}
const TSection2& TSection2 :: operator = (const TSection2 &Section){ t = Section.t;
X = Section.X;
P = Section.P;
Z = Section.Z; return *this;
}
bool TSection2 :: operator == (const TSection2 &Section) const { return X == Section.X
&&P == Section.P
&&Z == Section.Z;
}
TSection2::Triangulation TSection2 :: Triangulate()
{
std::vector< std::pair<Point,size_t> > points; for(size_t i=0; i < X.size();++i)
points.push_back( std::make_pair(CGAL::ORIGIN+X[i],i) ); Triangulation T;
//clock_t timer=clock();
//std::cout<<"Triangulation time: ";//38595 мсек - 1999 точек /// 1390000 мсек - 12500 точек
T.insert( points.begin(),points.end() ); //std::cout<<clock()-timer<<std::endl; return T;
}
void TSection2 :: FindIntersectionAndMin(TSection2::Triangulation &T)
{
vector<pair<size_t,size_t> > OldNewIndex; |
|
|
Triangulation::Finite_vertices_iterator |
it |
= T.finite_vertices_begin(), |
end =
T.finite_vertices_end();
size_t Size = T.number_of_vertices(); Triangulation::Finite_vertices_iterator* ArrayIterators
106
= new Triangulation::Finite_vertices_iterator[Size]; size_t i = 0;
for (; it != end; ++it){ ArrayIterators[i++] = it;
}
omp_lock_t Lock; omp_init_lock(&Lock);
#pragma omp parallel for num_threads(NP) for(int i = 0; i < Size; ++i)
{
assert(omp_get_num_threads() <= omp_get_num_procs()); assert(omp_get_num_threads() == NP);
Triangulation::Vertex_circulator vc = T.incident_vertices(ArrayIterators[i]); if(vc != 0){
Triangulation::Vertex_circulator done = vc; Point p = ArrayIterators[i]->point();
do {
if(T.is_infinite(vc)) continue;
Point p1 = vc->point();
if(vc->info() == ArrayIterators[i]->info())
{
std::cout<<"assert"<<std::endl;
}
CGAL :: Comparison_result Dist = CGAL::compare_squared_distance ( p, p1, Rho
); if (
Dist == CGAL :: SMALLER || Dist == CGAL :: EQUAL
){//если расстояние меньше RhoX if(Z[ArrayIterators[i]->info()] > Z[vc->info()])
{
omp_set_lock(&Lock); OldNewIndex.push_back(make_pair(ArrayIterators[i]-
>info(),vc->info()));
omp_unset_lock(&Lock);
}
}
}while(++vc != done);
}
}
omp_destroy_lock(&Lock); delete []ArrayIterators;
for(size_t i = 0; i < OldNewIndex.size(); ++i)
{
Z[OldNewIndex[i].first] = Z[OldNewIndex[i].second];
P[OldNewIndex[i].first] = P[OldNewIndex[i].second];
}
}
void TSection2 :: FindIntersectionAndMin()
{
vector<double> vMin = Z; for(size_t i = 0; i < X.size(); ++i)
{
for(size_t j = i+1; j < X.size(); ++j)
{
if(X[i] == X[j])
{
if(vMin[i] > Z[j])
{
vMin[i] = Z[j];
107
}
if(vMin[j] > Z[i])
{
vMin[j] = Z[i];
}
}
}
}
Z = vMin;
}
void TSection2 :: Formula()
{
//FindIntersectionAndMin(); Triangulation temp = Triangulate(); FindIntersectionAndMin(temp);
}
//TVALUEFUNCTION.H #pragma once
#include <fstream> #include <iostream> #include <vector> #include <algorithm> #include "TSection2.h" #include "Tree2.h" #include "../Include/Tree.h" using std :: string;
using std :: ofstream; using std :: ifstream; using std :: ostream; using std :: istream; using std :: endl;
class TValueFunction2
{
public:
TValueFunction2
(
const TTree ×,
const vector<TTree2> &Trajectories, const vector<TTree> &values
)
:Times(times), Trajectories(Trajectories), Values(values)
{}
void Instant2Files(const string &FileName); bool operator == (const TValueFunction2 &V1);
friend ostream& operator << (ostream &Out, const TValueFunction2 &VF); vector<Vector2> GetSectionPoints(const size_t SectionNum) const;
private:
TTree Times; vector<TTree2> Trajectories; vector<TTree> Values;
};
//TVALUEFUNCTION.CPP #include "TValueFunction2.h" #include "../Include/Functions.h" #include "Problem2.h"
#include <assert.h> using std :: ofstream; using std :: string;
using std :: ostringstream;
108
bool TValueFunction2::operator == (const TValueFunction2 &V1)
{
return V1.Trajectories == this->Trajectories;
}
ostream& operator << (ostream &Out, const TValueFunction2 &VF)
{
Out << VF.Trajectories; return Out;
}
void TValueFunction2::Instant2Files(const string &DirName){ assert(!Times.Empty());
unsigned int Size = Times.Size(); for(unsigned int t = 0; t < Size; ++t){
ostringstream FileName;
FileName << DirName+"/t_" << t << ".txt"; ofstream Out(FileName.str().c_str());
Out << 3 << " " << Trajectories.size() << endl; for(unsigned int k = 0; k < Trajectories.size(); ++k){
Out << Trajectories[k][t].x() << " "; Out << Trajectories[k][t].y() << " "; Out << Values[k][t] << endl;
}
Out.close();
}
}
vector<Vector2> TValueFunction2::GetSectionPoints(const size_t SectionNum) const
{
vector<Vector2> Result;
for(size_t i = 0; i < Trajectories.size(); ++i)
{
Result.push_back(Trajectories[i].GetBranche(SectionNum));
}
return Result;
}
109