3.1 Описание исходных данных
По условию даны абоненты локальной вычислительной сети, и их координаты. Необходимо, с минимальными затратами, соединить абонентов ЛВС по топологии «кольцо»
-
75
0
90
100
50
40
60
60
50
50
50
50
40
30
10
80
100
60
20
50
10
0
50
90
40
60
20
40
80
0
График расположения абонентов представлен на рисунке 4.
Рисунок 4
3.2 Алгоритм поиска оптимального решения
1. Рассчитать расстояния между каждой парой абонентов.
2. Выбрать абонента, с которого начнется построение сети.
3. Определить по таблице (рисунок 5) ближайшего к нему следующего абонента.
4. Соединить их.
5. Определить следующего ближайшего.
6. Последовательно переходя от абонентов к абоненту, определить последнего, и соединить его с первым.
7. Сложить длины все длины кабелей от абонента к абоненту.
3.3 Расчет контура минимальной длины
Рассчитаем расстояния между абонентами :
Рисунок 5
Теперь определим абонента, с которого начнем строить сеть. И соединим его с ближайшим (рисунок 6)
Рисунок 6
Переходим к следующему абоненту (рисунок 7)
Рисунок 7
После прохождения всего алгоритма, общая картина уже построенной сети выглядит так (рисунок 8).
Теперь необходимо вычислить общую длину проложенного кабеля.
25+31,6+ 10 + 10+10+ 22,3 + 14,14+22,3+44,7+64,03+28,28+22,3+51,5+103,07+101,4=560,62
Рис. 8
Несмотря на логику перехода от абонента к абоненту, можно заметить, что конечное решение кажется неоптимальным. Поэтому, опираясь на все тот же эвристический подход, рассмотрим еще один вариант соединения тех же самых абонентов.
Теперь соединять их будем путем только интуитивного перехода, с целью получения конечной схемы именно в виде «кольца» (рисунок 9), затем сравним полученную длину кабеля, таким образом, получим оптимальное решение.
Рис.9
Рассчитаем новую длину кабеля:
25+33,54+51,5+101,4+41,23+50+10+10+44,7+31,6+10+22,36+22,36+28,28=482,27
В итоге получаем разницу в 78,35 метра.
3.4 Описание системы
Рассматриваемую систему можно описать множеством разных способов, и в этой работе они пересекаются и перемешиваются, но в тоже время служат единой цели – максимально полно дать представление о системе.
Сначала использовался вербальный способ описания. Были описаны координаты абонентов и поставленная задача. Далее, построив расположение абонентов в виде графика, система описывается графическим способом. Теоретико-множественный используется, когда построена таблица расстояний между абонентами (рисунок 5). Для соединения абонентов в работе представлен эвристический метод, топологический же способ, то есть когда нам важно взаимное расположение и соединение, можно увидеть на конечной стадии, когда соединены все абоненты. Наконец абстрактно-алгебраический метод описания необходим для расчета длины всего контура.
ЗАКЛЮЧЕНИЕ
В ходе выполнения данной работы мной были рассмотрены различные способы описания системы и способы их реализации, выбран алгоритм поиска оптимального решения – минимального контура локальной вычислительной сети. В итоге построена локальная вычислительная сеть, соединяющая абонентов по топологии «кольцо», и выполнена задача минимизации затрат кабеля. Итоговая длина контура 482,27 метра.
СПИСОК ЛИТЕРАТУРЫ
Свободная энциклопедия [Электронный ресурс].– Режим доступа: http://ru.wikipedia.org
Компьютерные сети. Принципы, технологии, протоколы: Учебник для вузов. 3-е изд. – СПб.: Питер, 2006. – 958с.: ил.