3. Алгоритм Прима

С помощью алгоритма Прима минимальное остовное дерево порождается посредством разрастания одного поддерева от выбранной вершины. Алгоритм реализуется путем прибавления ребер, причем добавляемое ребро должно иметь наименьший вес. Процедура выполняется на сети G с n вершинами и m ребрами до тех пор, пока число ребер в сети T не станет равным n-1.

Алгоритм реализует следующие основные шаги:

Шаг 0. [Инициализация] Помечаем все вершины «невыбранными». Создаем сеть T с n вершинами, но без ребер. Выбираем произвольную вершину и помечаем ее «выбранной».

Шаг 1. [Цикл] До тех пор, пока существуют «невыбранные» вершины, выполнять шаг 2, в противном случае – STOP.

Шаг 2. [Отыскание ребра с наименьшим весом] Пусть (u,v) – ребро с наименьшим весом между произвольно выбранной вершиной u и произвольной невыбранной вершиной v. Помечаем v как «выбранную» и добавляем ребро (u,v) в сеть T.

На рис. 7 представлен пример построения с помощью алгоритма Прима минимального остовного дерева T для исходной сети G, изображенной на рис. 5. Порядок добавления ребер указан цифрами в квадратах на соответствующих ребрах порождаемой сети T. Выбранные вершины также помечены квадратами. Заметим, что исходные сети G для работы алгоритмов Крускала и Прима не обязательно ограничивать только классом полных сетей. Отсутствующим ребрам следует приписать бесконечный вес. Рис. 7. Построение минимального остовного дерева с помощью алгоритма Прима

0 1 2

T[0] ¹

T[1] ¹

T[2] ¹

5 2 5

₂ 5 _{7 2} 2

₆ ¹ 6 ¹

4 ³ 4 3 4 ³

3 ₁ 4 ₁

T[3] T[4]

4

11

5 _{7 2}

₉ 3

₆ 1

² 5 _{7 2} 2

₉ 3

₆ 1

3. Содержание работы и рабочее задание

В данной лабораторной работе предлагается программно реализовать один из алгоритмов кластерного анализа при помощи среды разработки Borland Delphi, а также, в соответствии с заданными вариантами предметной области, осуществить компьютерное проведение самого кластерного анализа.

В ходе работы необходимо выполнить следующее рабочее задание:

1. Изучить различные виды алгоритмов кластерного анализа, отличающиеся подалгоритмами построения минимального остовного дерева.

2. Изучить заданный вариант предметной области кластеризации, представленный в виде таблиц данных.

3. Выполнить следующие этапы программной реализации алгоритма кластерного анализа:

• составить алгоритм работы программы;

• создать интерфейс программы, позволяющий реализовать кластерный анализ (см. раздел 5);

• в соответствии с заданным вариантом предметной области программно реализовать один из алгоритмов кластерного анализа;

• ввести исходные данные предметной области в программу;

• получить результаты компьютерного проведения кластерного анализа при разных значениях исходных данных.

7. Варианты заданий

1. Вариант 1. Сортировочная станция. Признаки к варианту 1:

   1. Вагонооборот (ваг/год);

   2. Затраты на переработку и накопление (вагоно-часы/год);

   3. Транзит без переработки (ваг/год);

   4. Транзит с переработкой (ваг/год);

   5. Количество сортировочных путей.

Таблица 1. Условные значения признаков к варианту 1

Наименование станции	Вагонооборот (тыс. ваг/год)	Затраты на накопление и переработку (тыс.вагоно- часов/год)	Транзит без переработки (тыс. ваг/год)	Транзит с переработкой (тыс. ваг/год)	Количество сортировочных путей
Лянгасово	49850	3450	1965	2540	20
Егоршино	42361	2985	1788	2394	18
Орехово	13428	905	2136	1521	14
Пермь	37694	3054	1323	1447	15
Войновка	22748	1985	984	840	17
Инская	20016	2130	1980	1922	14
Омск	44689	3169	1562	1065	17
Екатеринбург	39460	4126	650	2008	14
Бердяуш	23164	2674	2654	651	9
Смычка	10748	798	846	2013	7
Чусовская	29710	3012	1654	654	10
Агрыз	11547	1065	764	1024	11
Нижний Новгород	38155	3316	1545	1985	15
Юдино	17568	897	862	331	5
Челябинск	40036	3155	2560	606	14
Богданович	23757	2581	1035	1654	9
Каменск-Уральский	14692	964	1876	1065	4
Курган	19864	2379	1654	1689	8
Алтайская	13000	988	2985	1986	12

2. Вариант 2. Станционный перегон. Признаки к варианту 2:

   1. Длина (км);

   2. Время с последнего капитального ремонта (дней);

   3. Электрификация перегона;

   4. Пропускная способность (ваг/год);

   5. Количество путей.

Таблица 2. Условные значения признаков к варианту 2

Наименование перегона	Длина (км)	Время с последнего капитального ремонта (дней)	Электрификация перегона	Пропускная способность (ваг/год)	Количество путей
Березники-Чусовская	376	904	Да	1985	3
Смычка-Егоршино	285	1032	Да	655	2
Омск-Войновка	136	844	Нет	3204	2
Алтайская-Курган	582	642	Нет	654	1
Омск-Курган	42	165	Нет	4510	2
Лянгасово-Нижний Новгород	390	640	Да	1645	1

Таблица 2. (Продолжение)

Санкт-Петербург- Лянгасово	489	564	Нет	5413	2
Лянгасово-Пермь	376	846	Нет	584	2
Пермь-Агрыз	109	1002	Да	1534	3
Агрыз-Екатеринбург	110	455	Да	3520	2
Смычка-Гороблагодатская	143	1364	Нет	1104	1
Войновка-Богданович	122	99	Нет	1246	2
Орехово-Юдино	316	961	Да	854	1
Омск-Алтайская	262	156	Да	3510	3
Богданович-Каменск- Уральский	328	246	Нет	946	3
Серов-Егоршино	561	1062	Да	1581	2
Челябинск-Каменск- Уральский	109	346	Да	796	3
Серов-Гороблагодатская	161	964	Нет	779	1

3. Вариант 3. Вагонный парк. Признаки к варианту 3:

   1. Пробег вагона (км);

   2. Грузовладелец (ОАО «РЖД», физическое или юридическое лицо);

   3. Время после ремонта (дней);

   4. Тоннаж (т);

   5. Вид вагона (пассажирский, полувагон, цистерна, рефрижератор). Таблица 3. Условные значения признаков к варианту 3

Номер вагона	Пробег вагона (км)	Грузовладелец	Время после ремонта (дней)	Тоннаж (т)	Вид вагона
2210511	32100	ООО «АЗОТ»	1620	50	Пассажирский
8005924	5200	ОАО «РЖД»	206	34	Рефрижератор
8011456	16958	ОАО «РЖД»	6589	34	рефрижератор
7940061	20695	Иванов А.А.	10264	50	цистерна
6980469	36599	ОАО «РЖД»	11336	46	полувагон

4. Вариант 4. Студенческий состав. Признаки к варианту 4:

   1. Рост (см);

   2. Вес (кг);

   3. Возраст (лет);

   4. Уровень интеллекта (IQ);

   5. Образование (среднее, высшее, ученая степень). Таблица 4. Условные значения признаков к варианту 4

Фамилия	Рост (см)	Вес (кг)	Возраст (лет)	Уровень интеллекта	Образование
Иванов	165	65	18	70	Среднее
Петров	182	112	65	142	Уч. степень
Сидоров	169	95	27	100	Высшее
Степанов	176	74	32	94	Высшее
Фѐдоров	189	82	40	82	Среднее

5. Вариант 5. Кредитная информация. Признаки к варианту 5:

   1. Возраст (лет);

   2. Заработок (руб);

   3. Кредитная история;

   4. Семейное положение;

   5. Образование (среднее, высшее, ученая степень). Таблица 5. Условные значения признаков к варианту 5

Фамилия	Возраст (лет)	Заработок (руб)	Кредитная история	Семейное положение	Образование
Иванов	23	15000	Нет	Женат	Высшее
Петров	50	40000	Есть	Женат	Высшее
Сидоров	34	16000	Есть	Холост	Среднее
Федоров	29	20000	Нет	Холост	Среднее
Яковлев	42	18000	Есть	Холост	Уч. степень