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

В данном курсовом проекте для построения минимального остовного дерева используется алгоритм Краскала. Рёбра графа упорядочиваются в порядке не убывания их весов и последовательно добавляются к графу. Если добавление нового ребра приведёт к образованию цикла, то это ребро пропускается. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным лесом минимального веса.

3 Схемы основных алгоритмов

3.1 Пошаговый алгоритм

Шаг 1. Заполнение матрицы весов T .

Шаг 2. Создание матрицы смежности С .

Шаг 2а. Если расстояние между двумя точками s > d , то в матрицу заносится 0, иначе 1.

Шаг 2б. Повторение шага 2 N раз;

Шаг 3. Создание матрицы минимального остовного дерева ТТ ;

Шаг 3а. Если tt_ii = 0, tt_jj = 0, то tt_ij = t_ij , tt_ii = k , tt_jj = k , k = k +1, где t_ij – минимальный положительный элемент матрицы T ;

Шаг 3б. Если tt_ii = 0, tt_jj ≠ 0, то tt_ij = t_ij , tt_ii = tt_jj ;

Шаг 3д. Если tt_ii ≠ 0, tt_jj = 0,то tt_ij = t_ij , tt_jj = tt_ii ;

Шаг 3е. Если tt_ii ≠ 0, tt_jj ≠ 0, tt_ii ≠ tt_jj , то tt_ij = t_ij , tt_ii =l , tt_jj = l , где l – наименьшее из tt_ii иtt_jj ;

Шаг 3ж. Если tt_ii ≠ 0, tt_jj ≠ 0, tt_ii = tt_jj , то t_ij = -1;

Шаг 4. Проверка диагональных элементов матрицы Т T ;

Шаг 4б. Если tt_zz = 1, то повторить шаг 4. Иначе m = 0;

Шаг 5. Повторять алгоритм с шага 3 до тех пор, пока m ≠ 1;

3.2 Схема алгоритма.

Решение данной задачи состоит из нескольких этапов: кластеризации и построения минимального остовного дерева. Схемы этих алгоритмов, изображены на рисунках 2 – 4. Общая схема алгоритма изображена на рисунке 1.

Рисунок 1 – Схема основного алгоритма

Рисунок 2 – Алгоритм кластеризации

Рисунок 3 – Алгоритм построения минимального остовного дерева

Рисунок 4 – Алгоритм построения минимального остовного дерева (продолжение)

4 Результаты тестирования

Было проведено 3 различных эксперимента.

4.1 Тест первый.

Пусть граф содержит 8 вершин, координаты которых заданы случайным образом, а взвешенная матрица Т представлена на рисунке 5. Предельное расстояние d = 5;

Рисунок 5 – Тест первый (часть 1)

Шаг 1. Обнуление матрицы дерева ТТ .