Skip to content

README.md

Latest commit

 

History

History
95 lines (68 loc) · 11.7 KB

README.md

File metadata and controls

95 lines (68 loc) · 11.7 KB
Raw

Задача A1. Задача трёх кругов: Алгоритм, Анализ и Экспериментальные Результаты

1. Постановка задачи и Алгоритм Монте-Карло

Алгоритм Монте-Карло для приближенного вычисления площади пересечения трех кругов реализуется следующим образом:

  1. Определение ограничивающей области (R): Вычисляется минимальный прямоугольник, полностью охватывающий область пересечения трех кругов (R_narrow).
  2. Генерация точек: Случайным образом генерируется $N$ точек $(x, y)$ внутри ограничивающего прямоугольника $R$.
  3. Проверка попадания: Для каждой сгенерированной точки проверяется, попадает ли она в область пересечения всех трех кругов. Счетчик $M$ увеличивается, если точка попадает.
  4. Оценка площади: Площадь пересечения $S_{estimate}$ оценивается по формуле: $S_{estimate} = \frac{M}{N} \times S_{rec}$, где $S_{rec}$ — площадь ограничивающего прямоугольника.

Задача состоит в приближённой оценке площади фигуры, образованной пересечением трёх кругов, с использованием метода Монте-Карло, а также в анализе точности оценки в зависимости от масштаба ограничивающей прямоугольной области (R_wide и R_narrow) и количества сгенерированных точек N.

1.1. Исходные данные и Точное значение площади

Круг Центр (x_i, y_i) Радиус r_i
C1 (1, 1) 1
C2 (1.5, 2) sqrt(5)/2
C3 (2, 1.5) sqrt(5)/2

Точное значение площади (S_exact): Согласно аналитической декомпозиции, предложенной в условии задачи, точное значение площади вычисляется по формуле:

S_exact = 0.25 * PI + 1.25 * asin(0.8) - 1.0;

Численное значение: S_exact ≈ 0.944517

1.2. Ограничивающие прямоугольные области

Для экспериментального анализа используются две области:

Область X_min X_max Y_min Y_max Площадь S_rec
Широкая (R_wide) 0 ≈ 3.118 0 ≈ 3.118 ≈ 9.722
Узкая (R_narrow) 1 2 1 2 1

1.3. Реализация алгоритма

Оценка площади S_estimate вычисляется по формуле:

S_estimate = ( (double)M / N ) * S_rec;

где M — число точек, попавших в область пересечения, N — общее число сгенерированных точек, S_rec — площадь ограничивающего прямоугольника.

Критерий попадания точки (x, y) в область пересечения (должна попасть в каждый круг):

bool is_in_intersection(double x, double y, const Circle circles[3]) {
    // Проверка для каждого круга: (x - x_i)^2 + (y - y_i)^2 <= r_i^2
    return is_inside(x, y, circles[0]) &&
           is_inside(x, y, circles[1]) &&
           is_inside(x, y, circles[2]);
}

2. Экспериментальные результаты

Экспериментальные замеры проводились для N, изменяющегося от 100 до 100000 с шагом 500, для обеих ограничивающих областей. В итоговой программе для задачи A1i используется адаптивное N, которое рассчитывается в зависимости от площади ограничивающего прямоугольника для баланса между точностью и скоростью выполнения, а также фиксированный seed=42 для воспроизводимости результатов.

2.1. График 1: Зависимость оценки площади от числа точек N

График 1: Зависимость оценки площади от числа точек N

Описание: График отображает, как приближённое значение площади S_estimate сходится к точному значению S_exact ≈ 0.944517 при увеличении числа точек N.

Наблюдения:

  • Узкая область: Оценка площади демонстрирует высокую стабильность и быстро сходится к точному значению площади. Это объясняется тем, что площадь ограничивающего прямоугольника (равная 1) близка к точному значению, что максимизирует вероятность попадания в целевую область.
  • Широкая область: Оценка площади имеет значительно большую дисперсию, особенно при малом числе точек. Сходимость к точному значению площади происходит медленнее, что связано с низкой вероятностью попадания в целевую область (площадь ограничивающего прямоугольника ≈ 9.722).

2.2. График 2: Зависимость относительного отклонения от числа точек N

График 2: Зависимость относительного отклонения от числа точек N

Описание: График отображает относительное отклонение Delta в логарифмическом масштабе по оси Y. Относительное отклонение вычисляется по формуле:

Delta = abs(S_estimate - S_exact) / S_exact;

Наблюдения:

  • Сходимость: Для обеих областей наблюдается тенденция к уменьшению относительного отклонения с ростом N, что соответствует теоретическому закону сходимости метода Монте-Карло (Delta пропорциональна 1/sqrt(N)).
  • Эффективность: При всех значениях N узкая область (R_narrow) демонстрирует значительно меньшее относительное отклонение по сравнению с широкой областью (R_wide). Это подтверждает, что выбор ограничивающей области, максимально приближенной к целевой фигуре, является критически важным для повышения эффективности и точности метода Монте-Карло.

3. Выводы

  1. Влияние масштаба области: Использование "узкой" ограничивающей области (R_narrow) существенно повышает эффективность метода Монте-Карло. При S_rec ≈ S_exact вероятность попадания точки в целевую область максимальна, что приводит к быстрой сходимости и низкой дисперсии оценки площади.
  2. Влияние числа точек N: Точность оценки S_estimate для обеих областей растёт с увеличением N, что подтверждает теоретическую зависимость 1/sqrt(N). Однако для достижения одинаковой точности в "широкой" области требуется значительно большее число точек, чем в "узкой".
  3. Рекомендация для реализации: Для практической реализации алгоритма Монте-Карло (например, в задаче A1i) следует стремиться к выбору минимально возможной ограничивающей области, полностью охватывающей целевую фигуру, для минимизации вычислительных затрат при заданной точности.

4. Дополнительные материалы

  1. ID посылки по задаче A1i в системе CodeForces:

    • [Место для ID посылки после загрузки кода A1i_monte_carlo.cpp]

  2. Ссылка на публичный репозиторий с исходными данными:

    • [Место для ссылки на репозиторий с файлом A1_raw_data.csv, A1_Graph1_S_estimate_vs_N.png, A1_Graph2_Relative_Error_vs_N.png и A1_experiment.py]
    • Исходные данные для эксперимента содержатся в файле A1_raw_data.csv.