Краткий тест‑план для функции вычисления минимального пути на сетке с препятствиями (BFS — для невзвешенных, Дейкстра — для взвешенных). Сжатый, но полный — разделы: цель, предположения, наборы тестов (корректность и граничные случаи), проверка реконструкции пути, тесты на некорректный ввод, профилирование и критерии покрытия.
Предположения
- Сетка размера $n\times m$.
- Движения: уточнить вариант — 4‑связность (вверх/вниз/влево/вправо) или 8‑связность (включая диагонали). Проводить тесты для каждого варианта отдельно.
- Для Дейкстры веса ребер положительны (> $0$); отрицательные веса должны приводить к ошибке/отказу.
1) Базовые функциональные тесты (корректность)
- Пустая сетка без препятствий:
- вход: сетка $3\times 3$, старт $(0,0)$, цель $(2,2)$; алгоритм BFS; ожидаемая длина пути (число шагов) для 4‑связности: $\text{dist}=4$. Проверить допустимость пути и длину.
- Присутствие препятствий:
- простой барьер с единственным проходом; проверить, что найден путь проходит через проход и длина минимальна.
- Взвешенная сетка (Дейкстра):
- разные положительные веса; сравнить с ожидаемой суммой весов; пример: веса вдоль двух альтернативных путей, один короче по числу шагов, другой — по суммарному весу; убедиться, что Дейкстра выбирает минимальную суммарную стоимость.
- Несколько одинаковых минимальных путей:
- убедиться, что длина/стоимость минимальна; если требуется детерминизм — проверить конкретную политику выбора (например, приоритет по направлению).
- Start == Goal:
- старт равен цели; ожидаемая длина $0$, путь содержит единственный узел.
- Goal недостижим:
- цель полностью окружена препятствиями; алгоритм должен вернуть отсутствие пути (null/empty) и не падать.
2) Граничные случаи и ошибки ввода
- Пустая/нулевая сетка:
- $n=0$ или $m=0$ — корректная обработка (ошибка/пустой результат).
- Некорректные координаты старта/цели (вне границ): выбрасывать ошибку.
- Начало или цель на клетке‑препятствии: ожидается либо ошибка, либо отсутствие пути (в зависимости от спецификации).
- Невалидные веса:
- отрицательные веса для Дейкстры — явная ошибка.
- нулевые веса — допустимо (но проверить корректность).
- Неточные/нецелые веса:
- дробные веса — проверка корректности сумм и сравнения с эпсилоном $\epsilon$ (например, $\epsilon =1e-9$).
3) Структурные/пограничные геометрические случаи
- Однострочная сетка: $1\times m$ и $n\times 1$.
- Большой прямоугольник с длинным узким коридором.
- Полностью заполненная препятствиями сетка: путь отсутствует.
- Старт или цель на краю/углу сетки.
4) Проверка корректности пути (assertions для каждого найденного пути)
- Путь начинается в старте и заканчивается в цели.
- Последовательные клетки в пути смежны по выбранной связности (4 или 8).
- Ни одна клетка пути не является препятствием.
- Для невзвешенных задач длина пути равна числу шагов (количество ребер) — ожидаемое значение.
- Для взвешенных задач суммарный вес пути равен вычисленному значению расстояния (с учётом погрешности для дробных весов).
5) Нефункциональные тесты и профилирование
- Временные сложности (проверка эмпирического соответствия теоретике):
- BFS ожидаемая сложность: $O(V+E)$ (для сетки $V=n\cdot m$; $E\approx 4V$ для 4‑связности).
- Дейкстра с кучей: $O(E+V\log V)$.
- Тесты на масштаб:
- мелкие: $n\times m=10\times 10$ — базовая корректность.
- средние: $n\times m=100\times 100$ — проверка памяти и времени.
- большие: $n\times m=1000\times 1000$ — стресс‑тест (замер времени и пикового потребления памяти). Установить целевые пороги по времени/памяти в зависимости от окружения (например, завершение BFS на $1000\times 1000$ в пределах допустимого времени).
- Профайлинг:
- замерить общее время выполнения, время на извлечение из очереди/кучи, время на посещение смежных узлов, пиковую память.
- собрать профили для лучшего/худшего/среднего случаев (пустая сетка, плотные препятствия, лабиринт).
- Метрики и пороги (примеры):
- среднее время на обработку одной клетки для BFS: установить ориентир $t_{\text{cell}}\le T$ (зависит от языка/железа); приводить относительные сравнения при изменении $V$.
- масштабируемость: при увеличении числа узлов в $k$ раз время должно расти приблизительно линейно для BFS.
6) Покрытие тестами (coverage)
- Цель: покрытие кода не менее $90\%$ строк и $80\%$ ветвлений (при необходимости скорректировать под проект).
- Обязательное покрытие:
- нормальные ветви (путь найден/не найден),
- обработка ошибок ввода,
- разные ветви для структуры данных (пустая очередь, повторная релаксация в Дейкстре),
- ранний выход при достижении цели (если реализован),
- случаи с равными расстояниями (tie).
- Юнит‑тесты:
- тесты на отдельные вспомогательные функции: проверка соседей, проверка валидности координат, суммирование весов, реконструкция пути.
- Автоматизированные property‑tests / fuzzing:
- генерировать случайные сетки и сравнивать результаты BFS vs Дейкстра на невзвешенных версиях (веса $=1$) или сравнивать с эталонной реализацией (наивный Dijkstra/O(N^2) для небольших размеров).
7) Тесты энергонезависимости и детерминизма
- Проверить, что при фиксированном random seed (если используется) результат детерминирован, либо документировать недетерминированность.
- Проверить стабильность поведения при параллельных вызовах (если функция должна быть потокобезопасной).
8) Контроль метрик качества результатов
- Корректность: все основные случаи проходят.
- Временная эффективность: эмпирические замеры не превышают заданных порогов.
- Память: пиковая память не превышает ожидаемую (примерно $O(V)$ для хранения dist/visited/parent).
- Покрытие: целевые проценты по строкам/ветвлениям.
Примеры конкретных тест‑кейсов (коротко)
- 4‑связность, невзвешенная:
- grid:
[[S, 0, 0],
[1, 1, 0],
[0, 0, G]]
где $S=(0,0)$, $G=(2,2)$, препятствие обозначено $1$. Ожидаемая длина $\text{dist}=4$.
- Взвешенная:
- два пути: суммарный вес по пути A = $5$, по пути B = $7$. Ожидаемая стоимость $5$.
- Старт=Цель:
- любая сетка, старт=цель -> длина $0$, путь = [start].
Рекомендации по реализации тестов
- Автоматизировать запуск с отчётом времени и использования памяти.
- Логировать случаи неудач с выводом сетки, найденного пути и ожидаемых значений.
- Использовать сравнение свойств: валидность пути + минимальность стоимости/длины; не полагаться на единственный ожидаемый маршрут, если несколько оптимальных.
Если нужно — могу привести конкретный набор unit‑тестов (матрицы входа, ожидаемые длины/пути) в формате кода на выбранном языке.