Отчёт ко 2 заданию

 1. Описание задачи и выбранных паттернов

Задача: Реализовать систему поиска пути в лабиринте с возможностью сравнения нескольких алгоритмов (BFS, DFS, A*). Система должна поддерживать разные способы построения лабиринта и позволять легко добавлять новые алгоритмы поиска.

Для решения задачи были применены следующие паттерны проектирования:

- Strategy — для инкапсуляции алгоритмов поиска пути (BFS, DFS, A*). Позволяет динамически менять стратегию поиска.
- Builder — для построения лабиринта из файла. Отделяет процесс создания лабиринта от его представления.

Эти паттерны обеспечивают гибкость и расширяемость системы.

 Диаграмма классов (Mermaid)

```mermaid
classDiagram
    class Maze {
        +width: int
        +height: int
        +cells: List~List~Cell~~
        +start: Cell
        +exit: Cell
        +getCell(x, y)
        +getNeighbors(cell)
    }

    class Cell {
        +x: int
        +y: int
        +is_wall: bool
        +is_start: bool
        +is_exit: bool
        +isPassable()
    }

    class PathFindingStrategy {
        <<interface>>
        +findPath(maze, start, exit)
    }

    class BFSStrategy {
        +findPath(maze, start, exit)
    }

    class DFSStrategy {
        +findPath(maze, start, exit)
    }

    class AStarStrategy {
        +findPath(maze, start, exit)
        -heuristic(a, b)
    }

    class MazeSolver {
        -maze: Maze
        -strategy: PathFindingStrategy
        +setStrategy(strategy)
        +solve()
    }

    class MazeBuilder {
        <<interface>>
        +buildFromFile(filename)
    }

    class TextFileMazeBuilder {
        +buildFromFile(filename)
    }

    Maze "1" *-- "many" Cell
    MazeSolver --> PathFindingStrategy
    PathFindingStrategy <|-- BFSStrategy
    PathFindingStrategy <|-- DFSStrategy
    PathFindingStrategy <|-- AStarStrategy
    MazeBuilder <|-- TextFileMazeBuilder
```

 2. Листинги ключевых классов

Ключевые классы (Strategy и MazeSolver):

```python
class PathFindingStrategy:
    def findPath(self, maze, start, exit):
        raise NotImplementedError

class BFSStrategy(PathFindingStrategy):
    def findPath(self, maze, start, exit):
        # реализация BFS
        ...

class DFSStrategy(PathFindingStrategy):
    def findPath(self, maze, start, exit):
        # реализация DFS
        ...

class AStarStrategy(PathFindingStrategy):
    def findPath(self, maze, start, exit):
        # реализация A*
        ...
```

```python
class MazeSolver:
    def __init__(self, maze=None, strategy=None):
        self.maze = maze
        self.strategy = strategy

    def setStrategy(self, strategy):
        self.strategy = strategy

    def solve(self):
        if not self.maze or not self.strategy:
            return None
        # замер времени и вызов стратегии
        ...
```

Полный код доступен в репозитории (или может быть предоставлен по запросу).

 3. Результаты экспериментов

Эксперименты проводились на пяти типах лабиринтов. Ниже представлены ключевые результаты.

Сводная таблица (средние значения):

| 10x10_simple | BFS | 0.1196 | 90 | 0 |
| 10x10_simple | DFS | 0.0526 | 67 | 37 |
| 10x10_simple | AStar | 0.1728 | 86 | 19 |
| 50x50_with_deadends | BFS | 2.2649 | 1621 | 0 |
| 50x50_with_deadends | DFS | 1.5761 | 1124 | 243 |
| 50x50_with_deadends | AStar | 1.1708 | 440 | 99 |
| 100x100_complex | BFS | 0.0184 | 13 | 1 |
| 100x100_complex | DFS | 0.0165 | 13 | 1 |
| 100x100_complex | AStar | 0.0223 | 13 | 1 |
| empty | BFS | 1.3326 | 900 | 0 |
| empty | DFS | 0.821 | 900 | 465 |
| empty | AStar | 2.1481 | 900 | 59 |
| no_exit | BFS | 0.6415 | 488 | 1 |
| no_exit | DFS | 0.6605 | 488 | 1 |
| no_exit | AStar | 1.0716 | 488 | 1 |

Графики (сохранены в папке `results/`):
- `time_comparison.png` — сравнение времени работы алгоритмов
- `visited_comparison.png` — сравнение количества посещённых клеток

 4. Анализ эффективности алгоритмов и применимости паттернов

- BFS показывает стабильную работу и находит кратчайший путь, но посещает больше клеток.
- DFS быстрее всех на простых и пустых лабиринтах, однако не гарантирует оптимальность.
- A* эффективнее всего по количеству посещённых клеток на сложных лабиринтах, но на больших картах проигрывает по времени из-за overhead приоритетной очереди.

Паттерн Strategy позволил легко переключаться между алгоритмами без изменения кода `MazeSolver`. Паттерн **Builder** сделал возможным добавление новых источников построения лабиринта (например, генератор случайных лабиринтов) без изменения основной логики.

 5. Выводы

Использование объектно-ориентированного подхода и паттернов проектирования существенно повысило гибкость и расширяемость кода.

Преимущества:
- Благодаря паттерну Strategy добавление нового алгоритма поиска (например, Dijkstra) требует только реализации интерфейса `PathFindingStrategy` без изменения `MazeSolver`.
- Паттерн Builder позволяет легко подключать новые способы загрузки лабиринтов.
- Код стал более читаемым и поддерживаемым.

Что было бы сложно изменить без паттернов:
- Замена алгоритма поиска потребовала бы значительных изменений в классе `MazeSolver` (много условных операторов `if`).
- Добавление нового способа построения лабиринта привело бы к дублированию кода.
- Сравнительный эксперимент было бы гораздо сложнее проводить, так как алгоритмы не были бы унифицированы через общий интерфейс.

Таким образом, применение паттернов Strategy и Builder сделало систему легко расширяемой и удобной для проведения экспериментов.