\documentclass[a4paper,12pt]{article}
\usepackage[left=2cm,right=2cm,
    top=2cm,bottom=2cm,bindingoffset=0cm]{geometry}
\usepackage{amsmath, amssymb}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{cite}
\usepackage{listings}
\lstset{extendedchars=\true, inputencoding=utf8}
\usepackage{color}
\usepackage{float}
\usepackage{caption}

\definecolor{mygreen}{rgb}{0,0.6,0}
\definecolor{mygray}{rgb}{0.5,0.5,0.5}
\definecolor{mymauve}{rgb}{0.58,0,0.82}

\lstset{
    language=C++,
    aboveskip=3mm,
    belowskip=3mm,
    showstringspaces=false,
    columns=flexible,
    basicstyle={\small\ttfamily},
    numbers=left,
    numberstyle=\tiny\color{mygray},
    keywordstyle=\color{blue},
    commentstyle=\color{mygreen},
    stringstyle=\color{mymauve},
    breaklines=true,
    breakatwhitespace=true,
    tabsize=4
}

\begin{document}

\begin{titlepage}
    \begin{center}
        \vspace*{2cm}
        \Large{\textbf{Расчёт оптимального маршрута \\ \small Программа поиска оптимального маршрута по времени}}\\[1.5cm]
        
        \normalsize
        \textbf{Выполнил:} Давыдов Даниил Андреевич\\
        \textbf{Проверил:} Малыхин Дмитрий Андреевич\\[2cm]
        
        \textbf{Дата:} \today
    \end{center}
\end{titlepage}

\tableofcontents
\newpage

\section{Введение}
Цель данной работы заключается в разработке программы для расчёта оптимального по времени полёта движения летательного аппарата. Для достижения этой цели была создана программа на языке C++, которая рассчитывает матрицы времени для различных манёвров: разгона, подъёма и их комбинации (разгон-подъём). Эти матрицы используются для определения оптимального маршрута полёта, минимизирующего общее время достижения заданных высоты и скорости.

\section{Алгоритм расчёта}
Для нахождения оптимального маршрута используется динамическое программирование. Основные шаги алгоритма включают:
\begin{enumerate}
    \item \textbf{Разбиение пространства}: Плоскость полёта делится на элементарные разбиения по высоте и скорости.
    \item \textbf{Заполнение матриц времени}: Для каждого разбиения рассчитываются времена выполнения манёвров разгона, подъёма и разгон-подъёма, формируя матрицы $Tr$, $Tp$, $Tpr$.
    \item \textbf{Расчёт матрицы минимальных времён $S$}: Используется обратный проход от целевого узла, выбирая на каждом шаге минимальное время из возможных переходов.
    \item \textbf{Восстановление оптимального пути $Path$}: По матрице маршрутов $Path$ восстанавливается последовательность действий, приводящих к минимальному общему времени.
\end{enumerate}

\section{Реализация программы}
Программа реализована на языке C++ и включает несколько ключевых компонентов:
\begin{itemize}
    \item \textbf{Функции расчёта времени манёвров}: `Razgon`, `Podyom`, `RazgPod`.
    \item \textbf{Функции для расчёта физических параметров}: `ro`, `a`, `Cy`, `Cx`, `P`.
    \item \textbf{Функции вывода для отладки}: `printDebugInfo`, `printTimeMatrices`.
    \item \textbf{Основная функция}: Содержит логику заполнения матриц, расчёта матрицы минимальных времён и восстановления оптимального пути.
\end{itemize}

\subsection{Пример кода функции расчёта разгона}
\begin{lstlisting}
double Razgon(double H1, double V1, double V2, double mass, double S_area)
{
    double a_H = a(H1);
    double ro_H = ro(H1);
    double g = 9.81;

    double V = (V1 + V2) / 2.0;
    double M = V / a_H;

    double P_M = P(M) * engineCount;

    double numerator = mass * g - P_M / 57.3 - cy0 * ro_H * V * V * S_area / 2.0;
    double denominator = P_M / 57.3 + cy1 * ro_H * V * V * S_area / 2.0;

    if (denominator == 0.0)
    {
        std::cerr << "Ошибка: Деление на ноль в функции Razgon.\n";
        return 1e9;
    }

    double alpha_deg = numerator / denominator;
    double alpha = alpha_deg * M_PI / 180.0;

    double Cx_alpha = Cx(alpha_deg);

    double cos_alpha = cos(alpha);
    double sin_alpha = sin(alpha);

    double denominator_time = P_M * cos_alpha - Cx_alpha * ro_H * pow(V, 2) / 2.0 * S_area * sin_alpha;

    if (denominator_time == 0.0)
    {
        std::cerr << "Ошибка: Деление на ноль при расчете времени разгона.\n";
        return 1e9;
    }

    double traz = (mass * (V2 - V1)) / denominator_time;
    return traz;
}
\end{lstlisting}

\subsection{Функция восстановления оптимального пути}
\begin{lstlisting}
int main()
{
    // ... [Инициализация и заполнение матриц Tr, Tp, Tpr] ...

    // Создание и инициализация матрицы S (минимальные времена)
    std::vector<std::vector<double>> S(m, std::vector<double>(n, 1e9)); // Инициализация большим значением

    // Создание матрицы Path для восстановления пути
    std::vector<std::vector<int>> Path(m, std::vector<int>(n, -1));

    // Установка целевого узла (верхний правый угол) в 0
    S[m - 1][n - 1] = 0.0;
    Path[m - 1][n - 1] = -1; // Целевой узел

    // Заполнение правого столбца (j = n - 1)
    for (int i = m - 2; i >= 0; --i)
    {
        S[i][n - 1] = S[i + 1][n - 1] + Tp[n - 1][i];
        Path[i][n - 1] = 1; // Подъем
    }

    // Заполнение нижней строки (i = m - 1)
    for (int j = n - 2; j >= 0; --j)
    {
        S[m - 1][j] = S[m - 1][j + 1] + Tr[m -1][j];
        Path[m - 1][j] = 0; // Разгон
    }

    // Заполнение оставшейся части матрицы S
    for (int i = m - 2; i >= 0; --i)
    {
        for (int j = n - 2; j >= 0; --j)
        {
            // Возможный переход через Разгон (0) - изменение скорости
            double option1 = S[i][j + 1] + Tr[i][j];

            // Возможный переход через Подъем (1) - изменение высоты
            double option2 = S[i + 1][j] + Tp[j][i];

            // Возможный переход через Разгон-Подъем (2) - изменение и высоты и скорости
            double option3 = S[i + 1][j + 1] + Tpr[j][i];

            // Находим минимальное из трех вариантов
            double min_time = option1;
            int path_choice = 0; // Разгон

            if (option2 < min_time)
            {
                min_time = option2;
                path_choice = 1; // Подъем
            }

            if (option3 < min_time)
            {
                min_time = option3;
                path_choice = 2; // Разгон-Подъем
            }

            // Обновляем матрицу S и Path
            if (min_time < S[i][j])
            {
                S[i][j] = min_time;
                Path[i][j] = path_choice;
            }
        }
    }

    // Восстановление оптимального пути
    std::ofstream outfile("output.txt");
    if (!outfile.is_open()) {
        std::cerr << "Не удалось открыть файл для записи.\n";
        return -1;
    }

    // Запись матрицы S в файл
    outfile << "Матрица минимальных времён (S) [время в сек]:\n";
    for (int i = 0; i < m; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            outfile << std::setw(10) << S[i][j] << " ";
        }
        outfile << "\n";
    }

    // Запись матрицы Path в файл
    outfile << "\nМатрица маршрутов (Path):\n";
    for (int i = 0; i < m; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            outfile << std::setw(3) << Path[i][j] << " ";
        }
        outfile << "\n";
    }

    // Восстановление оптимального пути и запись в файл
    outfile << "\nОптимальный маршрут по времени:\n";
    int current_i = 0; // Начинаем с начального узла (низкая высота, низкая скорость)
    int current_j = 0;
    double total_time = S[current_i][current_j];
    outfile << "Общее время: " << total_time << " сек\n";
    outfile << "Последовательность действий (начиная с H=" << Hn << ", V=" << Vn * 3.6 << " км/ч):\n";

    // Создадим секцию с координатами для удобства чтения в Python
    outfile << "\nКоординаты оптимального пути (H_start, V_start, H_end, V_end, Action):\n";
    outfile << "H_start,V_start,H_end,V_end,Action\n";

    while (Path[current_i][current_j] != -1)
    {
        int action = Path[current_i][current_j];
        double H_current = Hn + current_i * Hel;
        double V_current = Vn + current_j * Vel;
        double H_next, V_next;
        std::string action_str;

        switch (action)
        {
            case 0: // Разгон - изменение скорости
                H_next = H_current;
                V_next = V_current + Vel;
                action_str = "Разгон";
                current_j += 1;
                break;
            case 1: // Подъем - изменение высоты
                H_next = H_current + Hel;
                V_next = V_current;
                action_str = "Подъем";
                current_i += 1;
                break;
            case 2: // Разгон-Подъем - изменение высоты и скорости
                H_next = H_current + Hel;
                V_next = V_current + Vel;
                action_str = "Разгон-Подъем";
                current_i += 1;
                current_j += 1;
                break;
            default:
                std::cerr << "Неизвестное действие в Path[" << current_i << "][" << current_j << "]: " << action << "\n";
                outfile << "0,0,0,0,Unknown\n"; // Запись неизвестного действия
                break;
        }

        // Запись текущего действия в файл
        outfile << H_current << "," << V_current * 3.6 << "," << H_next << "," << V_next * 3.6 << "," << action_str << "\n";
    }

    outfile.close();

    std::cout << "Данные успешно записаны в файл 'output.txt'.\n";

    return 0;
}
\end{lstlisting}

\section{Результаты}
В результате выполнения программы были получены матрицы времени $S$, $Tr$, $Tp$, $Tpr$ и оптимальный маршрут полёта, минимизирующий общее время достижения заданных высоты и скорости. Пример вывода матрицы $S$ и матрицы маршрутов $Path$ приведён ниже:

\subsection{Пример матрицы минимальных времён (S)}
\begin{verbatim}
Матрица минимальных времён (S) [время в сек]:
                 H\V             310-505             505-700             700-895
            300-3150              187.35              160.31              269.88
           3150-6000              179.56              152.51              125.22
           6000-8850               52.18               27.59                0.00
\end{verbatim}

\subsection{Пример матрицы маршрутов (Path)}
\begin{verbatim}
Матрица маршрутов (Path):
  0   2   1 
  0   0   1 
  0   0  -1 
\end{verbatim}

\subsection{Оптимальный маршрут}
\begin{verbatim}
Общее время: 187.35 сек
Последовательность действий (начиная с H=300.00, V=310.00 км/ч):

Координаты оптимального пути (H_start, V_start, H_end, V_end, Action):
H_start,V_start,H_end,V_end,Action
300.00,310.00,300.00,505.00,Разгон
300.00,310.00,300.00,505.00,Разгон
300.00,505.00,3150.00,700.00,Разгон-Подъем
300.00,505.00,3150.00,700.00,Разгон-Подъем
3150.00,700.00,6000.00,700.00,Подъем
3150.00,700.00,6000.00,700.00,Подъем
\end{verbatim}

\section{Построение графика маршрута}
Для визуализации оптимального маршрута был разработан Python-скрипт, который считывает данные из файла `output.txt` и строит график полёта, деля плоскость на элементарные разбиения по высоте и скорости. Каждое действие (разгон, подъём, разгон-подъём) отображается разными цветами и стилями линий.

\subsection{Пример Python-скрипта для построения графика}
\begin{lstlisting}[language=Python]
import matplotlib.pyplot as plt
import csv

H = []
V = []
actions = []

with open('output.txt', 'r', encoding='utf-8') as file:
    reader = csv.reader(file)
    path_section = False
    for row in reader:
        if not row:
            continue
        if row[0].strip() == 'H_start':
            path_section = True
            continue
        if path_section:
            if len(row) < 5:
                continue
            try:
                H_start, V_start, H_end, V_end, Action = row
                H.append(float(H_start))
                V.append(float(V_start))
                actions.append(Action)
            except ValueError:
                continue

plt.figure(figsize=(12, 8))

unique_H = sorted(list(set(H)))
unique_V = sorted(list(set(V)))

if len(unique_H) > 1:
    Hel = unique_H[1] - unique_H[0]
else:
    Hel = 1  
if len(unique_V) > 1:
    Vel = unique_V[1] - unique_V[0]
else:
    Vel = 1 

plt.xlim(min(H) - Hel, max(H) + Hel)
plt.ylim(min(V) - Vel, max(V) + Vel)

plt.xticks(unique_H)
plt.yticks(unique_V)
plt.grid(True, which='both', linestyle='--', linewidth=0.5)

action_styles = {
    "Разгон": {'color': 'blue', 'linestyle': '-'},
    "Подъем": {'color': 'green', 'linestyle': '--'},
    "Разгон-Подъем": {'color': 'red', 'linestyle': '-.'}
}

# print(actions)
for i in range(len(H) - 1):
    x = [H[i], H[i+1]]
    y = [V[i], V[i+1]]
    action = actions[i]
    style = action_styles.get(action, {'color': 'gray', 'linestyle': ':'})
    plt.plot(x, y, color=style['color'], linestyle=style['linestyle'], marker='o', label=action)

handles, labels = plt.gca().get_legend_handles_labels()
by_label = dict(zip(labels, handles))
plt.legend(by_label.values(), by_label.keys())

plt.title('Оптимальный Маршрут')
plt.xlabel('Высота (м)')
plt.ylabel('Скорость (км/ч)')

plt.show()
\end{lstlisting}

\subsection{Пример полученного графика}
\begin{figure}[H]
    \centering
    \includegraphics[width=1\textwidth]{route_plot.png}
    \caption{График оптимального маршрута полёта}
    \label{fig:route_plot}
\end{figure}

\section{Заключение}
В ходе выполнения данной работы была разработана программа на языке C++ для расчёта матриц времени разгона, подъёма и разгон-подъёма летательного аппарата. Программа успешно определяет оптимальный маршрут полёта, минимизирующий общее время достижения заданных высоты и скорости. Дополнительно был создан Python-скрипт для визуализации маршрута, что значительно облегчает анализ полученных результатов.

\end{document}
