Материал: ММвСС. Экзаменационные вопросы и ответы
Следующие ребра — AB и BE с весом 7. Произвольно выбирается ребро AB, выделенное на рисунке. Тем самым вершина B добавляется к первому множеству выбранных вершин (A, B, D, F). Невыбранное ранее ребро BD выделено красным, так как его вершины входят в множество выбранных вершин (A, B, D, F), а, следовательно, уже существует путь (зелёный) между B и D (если бы это ребро было выбрано, то образовался бы цикл ABD).
Следующее ребро может быть выбрано только после нахождения всех циклов.
Аналогичным образом выбирается ребро BE, вес которого равен 7. Так как это ребро имеет вершины в обоих множествах выбранных вершин (A, B, D, F) и (C, E), эти множества объединяются в одно (A, B, C, D, E, F). На этом этапе красным выделено гораздо больше ребер, так как множества выбранных вершин, а, следовательно, и множества выбранных рёбер объединились. Теперь BC создаст цикл BCE, DE создаст цикл DEBA, и FE сформирует цикл FEBAD.
Алгоритм завершается добавлением ребра EG с весом 9. Количество выбранных вершин (A, B, C, D, E, F, G) = 7 соответствует количеству вершин графа. Минимальное остовное дерево построено.
25. Постановка задачи выбора оптимальной структуры сети (минимальной протяженности линий). Алгоритмы поиска кратчайшего остова графа. Алгоритм Прима.
Задача. Из большого числа остовов связного неориентированного графа нужно найти один, у которого сумма весов ребер наименьшая.
Алгоритм Прима. Сначала берётся произвольная вершина и находится ребро, инцидентное данной вершине и обладающее наименьшей стоимостью. Найденное ребро и соединяемые им две вершины образуют дерево. Затем, рассматриваются рёбра графа, один конец которых — уже принадлежащая дереву вершина, а другой — нет; из этих рёбер выбирается ребро наименьшей стоимости. Выбираемое на каждом шаге ребро присоединяется к дереву. Рост дерева происходит до тех пор, пока не будут исчерпаны все вершины исходного графа.
Алгоритм Прима на примере
|
Множество |
|
Множество |
|
Изображение |
выбранных |
Ребро ( , ) |
невыбранных |
Описание |
|
вершин |
|
вершин \ |
|
|
|
|
|
Исходный взвешенный граф. |
|
|
|
|
Числа возле ребер |
|
|
|
|
показывают их веса, |
|
{} |
|
{A,B,C,D,E,F,G} |
которые можно |
|
|
|
|
рассматривать как |
|
|
|
|
расстояния между |
|
|
|
|
вершинами. |
|
|
|
|
В качестве начальной |
|
|
|
|
произвольно выбирается |
|
|
|
|
вершина D. Каждая из |
|
|
(D,A) = 5 V |
|
вершин A, B, E и F |
|
{D} |
(D,B) = 9 |
{A,B,C,E,F,G} |
соединена с D |
|
(D,E) = 15 |
единственным ребром. |
||
|
|
|
||
|
|
(D,F) = 6 |
|
Вершина A — ближайшая к |
|
|
|
|
D, и выбирается как вторая |
|
|
|
|
вершина вместе с ребром |
|
|
|
|
AD. |
|
|
|
|
Следующая вершина — |
|
|
|
|
ближайшая к любой из |
|
|
|
|
выбранных вершин D или A. |
|
|
(D,B) = 9 |
|
B удалена от D на 9 и от A |
|
{A,D} |
(D,E) = 15 |
{B,C,E,F,G} |
— на 7. Расстояние до E |
|
(D,F) = 6 V |
равно 15, а до F — 6. F |
||
|
|
|
||
|
|
(A,B) = 7 |
|
является ближайшей |
|
|
|
|
вершиной, поэтому она |
|
|
|
|
включается в дерево F |
|
|
|
|
вместе с ребром DF. |
|
|
(D,B) = 9 |
|
|
|
{A,D,F} |
(D,E) = 15 |
|
Аналогичным образом |
|
(A,B) = 7 V |
{B,C,E,G} |
выбирается вершина B, |
|
|
|
|||
|
|
(F,E) = 8 |
|
удаленная от A на 7. |
|
|
(F,G) = 11 |
|
|
|
|
|
|
|
|
|
|
|
В этом случае есть |
|
|
(B,C) = 8 |
|
возможность выбрать либо |
|
|
(B,E) = 7 V |
|
C, либо E, либо G. C |
|
{A,B,D,F} |
(D,B) = 9 цикл |
{C,E,G} |
удалена от B на 8, E удалена |
|
(D,E) = 15 |
от B на 7, а G удалена от F |
||
|
|
|
||
|
|
(F,E) = 8 |
|
на 11. E — ближайшая |
|
|
(F,G) = 11 |
|
вершина, поэтому |
|
|
|
|
выбирается E и ребро BE. |
|
|
(B,C) = 8 |
|
|
|
|
(D,B) = 9 цикл |
|
Здесь доступны только |
|
|
(D,E) = 15 цикл |
|
вершины C и G. Расстояние |
|
{A,B,D,E,F} |
(E,C) = 5 V |
{C,G} |
от E до C равно 5, а до G — |
|
|
(E,G) = 9 |
|
9. Выбирается вершина C и |
|
|
(F,E) = 8 цикл |
|
ребро EC. |
|
|
(F,G) = 11 |
|
|
|
|
(B,C) = 8 цикл |
|
Единственная оставшаяся |
|
|
(D,B) = 9 цикл |
|
вершина — G. Расстояние от |
|
{A,B,C,D,E,F} |
(D,E) = 15 цикл |
{G} |
F до неё равно 11, от E — 9. |
|
(E,G) = 9 V |
E ближе, поэтому |
||
|
|
|
||
|
|
(F,E) = 8 цикл |
|
выбирается вершина G и |
|
|
(F,G) = 11 |
|
ребро EG. |
|
|
|
|
|
|
|
(B,C) = 8 цикл |
|
Выбраны все вершины, |
|
|
(D,B) = 9 цикл |
|
минимальное остовное |
|
{A,B,C,D,E,F,G} |
(D,E) = 15 цикл |
{} |
дерево построено (выделено |
|
|
(F,E) = 8 цикл |
|
зелёным). В этом случае его |
|
|
(F,G) = 11 цикл |
|
вес равен 39. |
|
|
|
|
|
26. Постановка задачи оптимального размещения оборудования в сети, заданной графом. Минимум расстояний до всех вершин графа (узлов сети) – поиск центра графа.
Начальные условия. Пусть имеется некоторая структура, заданная, например, расположением населенных пунктов и связывающих их дорог, или зданий и сооружений кабельной канализации между ними, модель которой может быть описана графом.
Задача состоит в том, что требуется найти такую вершину графа, расстояния от которой до других вершин минимальны, например, когда требуется обеспечить минимальную длину абонентской линии (например, при выборе места установки концентратора ADSL).
Тип задачи: минимаксная задача.
Решение может быть получено путем поиска центров графа.
|
|
|
Матрица длин кратчайших путей |
|
|
|||||||
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
max |
|
1 |
0 |
1 |
2 |
1 |
2 |
1 |
2 |
2 |
3 |
2 |
3 |
|
2 |
1 |
0 |
1 |
1 |
2 |
2 |
3 |
2 |
2 |
3 |
3 |
внешнегоЧлены разделения |
8 |
2 |
2 |
2 |
1 |
1 |
2 |
1 |
0 |
2 |
1 |
2 |
|
3 |
2 |
1 |
0 |
2 |
1 |
3 |
2 |
2 |
1 |
2 |
3 |
|
4 |
1 |
1 |
2 |
0 |
1 |
1 |
2 |
1 |
3 |
2 |
3 |
|
5 |
2 |
2 |
1 |
1 |
0 |
2 |
1 |
1 |
2 |
2 |
2 |
|
6 |
1 |
2 |
3 |
1 |
2 |
0 |
1 |
2 |
2 |
1 |
3 |
|
7 |
2 |
3 |
2 |
2 |
1 |
1 |
0 |
1 |
1 |
2 |
3 |
|
9 |
3 |
2 |
1 |
3 |
2 |
2 |
1 |
2 |
0 |
1 |
3 |
|
10 |
2 |
3 |
2 |
2 |
2 |
1 |
2 |
1 |
1 |
0 |
3 |
|
max |
3 |
3 |
3 |
3 |
2 |
3 |
3 |
2 |
3 |
3 |
|
|
|
Члены внутреннего разделения |
|
|
|
|
|||||||
Решение
1. Находим максимальные члены внешнего и внутреннего разделений.
2. Среди них находим минимальные — они же центры графа.
Ответ.
Вершины 5 и 8 — внешние и внутренние центры графа.
27. Постановка задачи оптимального размещения оборудования в сети, заданной графом. Минимум суммы расстояний до всех вершин графа (узлов сети) – поиск медианы графа.
Начальные условия. Пусть имеется некоторая структура, заданная, например, расположением населенных пунктов и связывающих их дорог, или зданий и сооружений кабельной канализации между ними, модель которой может быть описана графом.
Задача состоит в том, что требуется найти такую вершину графа, от которой сумма расстояний до других вершин минимальна, например, когда требуется обеспечить минимальный расход кабеля абонентской сети.
Тип задачи: минисуммная задача.
Решение может быть получено путем поиска медиан графа.
|
|
|
Матрица длин кратчайших путей |
|
|
|||||||
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
|
1 |
0 |
1 |
2 |
1 |
2 |
1 |
2 |
2 |
3 |
2 |
16 |
|
2 |
1 |
0 |
1 |
1 |
2 |
2 |
3 |
2 |
2 |
3 |
17 |
внешнегоЧлены разделения |
8 |
2 |
2 |
2 |
1 |
1 |
2 |
1 |
0 |
2 |
1 |
14 |
|
3 |
2 |
1 |
0 |
2 |
1 |
3 |
2 |
2 |
1 |
2 |
16 |
|
4 |
1 |
1 |
2 |
0 |
1 |
1 |
2 |
1 |
3 |
2 |
14 |
|
5 |
2 |
2 |
1 |
1 |
0 |
2 |
1 |
1 |
2 |
2 |
14 |
|
6 |
1 |
2 |
3 |
1 |
2 |
0 |
1 |
2 |
2 |
1 |
15 |
|
7 |
2 |
3 |
2 |
2 |
1 |
1 |
0 |
1 |
1 |
2 |
15 |
|
9 |
3 |
2 |
1 |
3 |
2 |
2 |
1 |
2 |
0 |
1 |
17 |
|
10 |
2 |
3 |
2 |
2 |
2 |
1 |
2 |
1 |
1 |
0 |
16 |
|
|
16 |
17 |
16 |
14 |
14 |
15 |
15 |
14 |
17 |
16 |
|
|
|
Члены внутреннего разделения |
|
|
|
||||||||
Решение
1. Суммируем члены внешнего и внутреннего разделений.
2. Среди них находим минимальные — они же медианы графа.
Ответ.
Вершины 4, 5 и 8 — внешние и внутренние медианы графа.
28. Кластерный анализ, постановка задачи кластеризации. Алгоритм FOREL.
Кластерный анализ – это способ группировки многомерных объектов, основанный на представлении результатов отдельных наблюдений точками подходящего геометрического пространства с последующим выделением групп как «сгустков» этих точек (кластеров, таксонов).
Кластерный анализ предполагает выделение компактных, удаленных друг от друга групп объектов, отыскивает «естественное» разбиение совокупности на области скопления объектов.
Он используется, когда исходные данные представлены в виде матриц близости или расстояний между объектами, либо в виде точек в многомерном пространстве.
Кластерный анализ ориентирован на выделение некоторых геометрически удаленных групп, внутри которых объекты близки.
Выбор расстояния между объектами является узловым моментом исследования, от него во многом зависит окончательный вариант разбиения объектов на классы при данном алгоритме разбиения.
Дано. Пусть задано множество объектов, которые имеют некоторые характеристики (например, координаты). Задача кластеризации. Состоит в выделении подмножеств объектов – кластеров, таким образом, чтобы в рамках кластера свойства объектов были близки, а между объектами разных кластеров они максимально отличались.
Примером может служит разбиение множества точек на плоскости на подмножества, по признаку близости их координат.
Решение задачи. Заключается в минимизации суммарного отклонения расстояний (метрик) объектов от центров кластеров (центров масс).
FOREL (Формальный Элемент) — алгоритм кластеризации, основанный на идее объединения в один кластер объектов в областях их наибольшего сгущения.
Цель кластеризации: выделить группы максимально близких друг к другу объектов, которые в силу гипотезы схожести и будут образовывать кластеры.
Входные данные |
Выходные данные |
Кластеризуемая выборка |
|
Может быть задана признаковыми описаниями |
|
объектов – линейное пространство либо матрицей |
|
попарных расстояний между объектами. |
Кластеризация на заранее неизвестное число |
Параметр – радиус поиска локальных сгущений |
таксонов. |
Его можно задавать как из априорных соображений |
|
(знание о диаметре кластеров), так и настраивать |
|
скользящим контролем. |
|
|
|
Алгоритм
1. Случайно выбираем текущий объект из выборки.
2. Помечаем объекты выборки, находящиеся на расстоянии менее, чем R от текущего. 3. Вычисляем их центр тяжести, помечаем этот центр как новый текущий объект.
4. Повторяем шаги 2-3, пока новый текущий объект не совпадет с прежним.
5. Помечаем объекты внутри сферы радиуса R вокруг текущего объекта как кластеризованные, выкидываем их из выборки.
6. Повторяем шаги 1-5, пока не будет кластеризована вся выборка.
Принцип работы
На каждом шаге мы случайным образом выбираем объект из выборки, раздуваем вокруг него сферу радиуса , внутри этой сферы выбираем центр тяжести и делаем его центром новой сферы. Таким образом мы на каждом шаге двигаем сферу в сторону локального сгущения объектов выбоки, т.е. стараемся захватить как можно больше объектов выборки сферой фиксированного радиуса. После того как центр сферы стабилизируется, все объекты внутри сферы с этим центром мы помечаем как кластеризованные и выкидываем их из выборки. Этот процесс мы повторяем до тех пор, пока вся выборка не будет кластеризована.
Блок-схема
29. Кластерный анализ, постановка задачи кластеризации. Алгоритм k-средних.
Метод -средних (англ. k-means) — наиболее популярный метод кластеризации.
Действие алгоритма таково, что он стремится минимизировать суммарное квадратичное отклонение точек кластеров от центров этих кластеров.
|
|
|
|
|
|
|
|
Метод -средних на примере |
|
|
|
|
|
|
|||||
|
|
|
|
|
Изображение |
|
|
|
|
|
Описание |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
Шаг 1. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Определим число кластеров, на которое требуется |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
разбить исходное множество = 2. |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
Шаг 2. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Случайным образом выберем две точки, которые |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
будут начальными центрами кластеров. Пусть это |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
будут точки 1 |
= (1,1) и 2 = (2,1). На рисунке |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
они закрашены черным цветом. |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Шаг 3. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Проход 1. |
|
|
|
|
|
|
|
# |
X |
Y |
Расстояние |
|
Расстояние |
Номер |
|
Для каждой точки определим к ней ближайший |
||||||||||
|
|
|
|
|
от |
|
от |
кластера |
|
центр кластера с помощью расстояния Евклида. В |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
A |
1 |
3 |
2.00 |
|
2.24 |
|
1 |
|
|
таблице представлены вычисленные с помощью |
|||||||
|
|
B |
3 |
3 |
2.83 |
|
|
2.24 |
|
2 |
|
|
формулы |
|
|
|
|
|
|
|
|
C |
4 |
3 |
3.61 |
|
|
2.83 |
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
( , ) = √( − |
)2 |
+ ( − |
)2 |
|
||||||||
|
|
D |
5 |
3 |
4.47 |
|
|
3.61 |
|
2 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
E |
1 |
2 |
1.00 |
|
1.41 |
|
1 |
|
|
расстояния между центрами кластеров 1 = |
|||||||
|
|
F |
4 |
2 |
3.16 |
|
|
2.24 |
|
2 |
|
|
(1, 1), 2 = (2, 1) и каждой точкой исходного |
||||||
|
|
G |
1 |
1 |
0.00 |
|
1.00 |
|
1 |
|
|
множества, а также указано, к какому кластеру |
|||||||
|
|
H |
2 |
1 |
1.00 |
|
|
0.00 |
|
2 |
|
|
принадлежит та или иная точка. |
|
|
||||
|
|
Цветом выделено минимальное из двух расстояний |
|
|
Таким образом, кластер 1 содержит точки A, E, G, |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
а кластер 2 – точки B, C, D, F, H. Как только |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
определятся члены кластеров, может быть |
||||||