Освоить алгоритмы с использованием стека
- реализация алгоритма построение выпуклой оболочки методом обхода Грэхема https://en.wikipedia.org/wiki/Graham_scan
- реализация алгоритма Nearest-neighbor chain https://en.wikipedia.org/wiki/Nearest-neighbor_chain_algorithm
- формирование входных и выходных тестовых данных
- тщательное тестирование реализаций
Рамон Антонио Родригес Залепинос
arodriges@hse.ru
Были реализованые алгоритмы Грэхема и Nearest-neighbor представленные функциями Graham_scan и NearestNeighbor Для их тестирования была написана специальные классы с геометрическими функциями, которые лежат в common
Для тестировния алгоритма Грэхема была написона функция checkConvex, ктороая проверяет то что оболочка действительно выпукла и все точки лежат внутри нее
Для тестирования алгоритма Nearest-neighbor была написана функция stupidClustering которая выполняет кластерицацию
глупым и не оптимизированным алгоритмом, который перебирает все пары кластеров и объединяет два ближайших
Этот алгоритм довольно медленный, что сильно сказывается на времени тестирования
Кластера в данном случае я представлял, как множества точек
Результатом же алгоритма Nearest-neighbor у меня является множество всех кластеров,
которые получились во время кластеризации,
Таким образом, если изначально было дано n точек, то алгоритм проведет (n - 1) операцию объединения, в результате
каждой из которых образуется новый кластер и вернет множество их (2*n - 1) кластера
Для запуска тестирования можно перейти в директорию проекта и выполнить следующий набор команд
mkdir build
cd build
cmake ..
cmake --build
./summer_practise