Топология компьютерной сети это схема соединения и физическое расположение сетевых устройств, включая компьютеры, по отношению к друг другу.

Топология компьютерной сети позволяет увидеть всю сеть, вернее ее структуру, а также проанализировать связь всех устройств входящих в сеть. Теория Интернет технологий выделяет несколько видов топологий сети: физическую, информационную, логическую и топологию управления обменом. В этой статье нас будет интересовать только физическая топология сети.

Нужно понимать, что теоретически количество способов соединения устройств в сети может быть бесконечно много. И чем больше устройств будет входить в сеть, тем больше будет способов соединения. Но это не значит, что нельзя классифицировать типы физических соединений, а, следовательно, выделить основные типы топологии сети.

Различают три основных и два дополнительных вида топологии :

1. Топология сети типа Звезда;
2. Кольцевая топология;
3. Шинная топология сети;
4. Ячеистая топология;
5. Смешанная топология сети.

Рассмотрим все типы топологий.

Топология компьютерной сети — основные виды

Топология компьютерной сети типа Звезда

В центре топологии «Звезда», находится сервер. Все устройства сети (компьютеры) подключены к серверу. Запросы от устройств направляются на сервер, где и обрабатываются. Выход из строя сервера, «убивает» всю сеть. Выход из строя одного устройства, не влияет на работу сети.

Кольцевая топология компьютерной сети

Кольцевая топология компьютерной сети предполагает замкнутое соединение устройств. Выход одного устройства соединяется с входом следующего. Данные двигаются по кругу. Отличается такая топология ненадобностью сервера, но выход одного устройства сети, «убивает» всю сеть.

Шинная топология сети

Шинная топология сети это параллельное подключение устройств сети к общему кабелю. Выход одного устройства из строя не влияет на работу сети, однако обрыв кабеля (шины) «вырубает» всю сеть.

Ячеистая топология

Ячеистая топология характерна для крупных сетей. Данную топологию можно охарактеризовать так, «все соединяются со всеми». То есть, каждая рабочая станция соединятся со всеми устройствами сети.

Смешанная топология сети

Принцип работы смешанной топологии понятен из названия. Характерно такая топология, для очень крупных компаний.

Может сложиться впечатление, что понятие топология сети применима только для локальных сетей. Это, конечно же, не так. И как пример, в общем виде разберем топологию глобальной сети сетей – Интернет.

Топология Интернет

Начнем разбор топологии Интернет с «низшего» звена – компьютера пользователя.

Компьютер пользователя, через модем или напрямую, связывается с местным интернет — провайдером. Точка соединения компьютера пользователя с сервером провайдера, называют точкой присутствия или POP — Point of Presence.

В свою очередь, провайдер владеет своей местной сетью, состоящую из линий связи и маршрутизаторов. Пакеты данных получаемые провайдером передаются либо на хост провайдера, либо оператору сетевой магистрали.

В свою очередь, операторы магистралей владеют своими международными магистральными сетями (высокоскоростными). Эти сети связывают между собой местных провайдеров.

Хостинговые компании и крупные Интернет корпорации устраивают свои серверные фермы (дата центры), которые напрямую подключены к магистралям.

Эти центры обрабатывают десятки тысяч запросов к веб-страницам в секунду. Как правило, дата-центры устраиваются в арендуемых помещениях магистральных операторов, где и располагаются магистральные маршрутизаторы.

Все магистрали между собой связаны. Точки соединения называют точками входа в сеть или Network Access Point – NAP. Это допускает перекидывать передаваемый пакет информации с магистрали на магистраль.

Термин «топология», или «топология сети», характеризует физическое расположение компьютеров, кабелей и других компонентов сети. Топология - это стандартный термин, который используется профессионалами при описании основной компоновки сети. Если Вы поймете, как используются различные топологии, Вы сумеете понять, какими возможностями обладают различные типы сетей. Чтобы совместно использовать ресурсы или выполнять другие сетевые задачи, компьютеры должны быть подключены друг к другу. Для этой цели в большинстве сетей применяется кабель. Однако просто подключить компьютер к кабелю, соединяющему другие компьютеры, не достаточно. Различные типы кабелей в сочетании с различными сетевыми платами, сетевыми операционными системами и другими компонентами требуют и различного взаимного расположения компьютеров. Каждая топология сети налагает ряд условий. Например, она может диктовать не только тип кабеля, но и способ его прокладки. Топология может также определять способ взаимодействия компьютеров в сети. Различным видам топологий соответствуют различные методы взаимодействия, и эти методы оказывают большое влияние на сеть.

Базовые топологии

Все сети строятся на основе трех базовых топологий:

• шина (bus);
• звезда (star);
• кольцо (ring).

Если компьютеры подключены вдоль одного кабеля [сегмента (segment)], топология называется шиной. В том случае, когда компьютеры подключены к сегментам кабеля, исходящим из одной точки, или концентратора, топология называется звездой. Если кабель, к которому подключены компьютеры, замкнут в кольцо, такая топология носит название кольца. Хотя сами по себе базовые топологии несложны, в реальности часто встречаются довольно сложные комбинации, объединяющие свойства нескольких топологий.

Шина

Топологию «шина» часто называют «линейной шиной» (linear bus). Данная топология относится к наиболее простым и широко распространенным топологиям. В ней используется один кабель, именуемый магистралью или сегментом, вдоль которого подключены все компьютеры сети.

Взаимодействие компьютеров

В сети с топологией «шина» компьютеры адресуют данные конкретному компьютеру, передавая их по кабелю в виде электрических сигналов. Чтобы понять процесс взаимодействия компьютеров по шине, Вы должны уяснить следующие понятия:

передача сигнала;

отражение сигнала; терминатор.

Передача сигнала

Данные в виде электрических сигналов передаются всем компьютерам сети; однако информацию принимает только тот, адрес которого соответствует адресу получателя, " зашифрованному в этих сигналах. Причем в каждый момент времени только один компьютер может вести передачу.Так как данные в сеть передаются лишь одним компьютером, ее производительность зависит от количества компьютеров, подключенных к шине. Чем их больше, т.е. чем больше компьютеров, ожидающих передачи данных, тем медленнее сеть. Однако вывести прямую зависимость между пропускной способностью сети и количеством компьютеров в ней нельзя. Ибо, кроме числа компьютеров, на быстродействие сети влияет множество факторов, в том числе:

характеристики аппаратного обеспечения компьютеров в сети;

частота, с которой компьютеры передают данные;

тип работающих сетевых приложений;

тип сетевого кабеля;

расстояние между компьютерами в сети.

Шина - пассивная топология. Это значит, что компьютеры только «слушают» передаваемые по сети данные, но не перемещают их от отправителя к получателю. Поэтому, если один из компьютеров выйдет из строя, это не скажется на работе остальных. В активных топологиях компьютеры регенерируют сигналы и передают их по сети.

Отражение сигнала

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

Терминатор

Чтобы предотвратить отражение электрических сигналов, на каждом конце кабеля устанавливают терминаторы (terminators), поглощающие эти сигналы. Все концы сетевого кабеля должны быть к чему-нибудь подключены, например к компьютеру или к баррел-коннектору - для увеличения длины кабеля. К любому свободному - неподключенному - концу кабеля должен быть подсоединен терминатор, чтобы предотвратить отражение электрических сигналов.

Нарушение целостности сети

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

Звезда

При топологии «звезда» все компьютеры с помощью сегментов кабеля подключаются к центральному компоненту, именуемому концентратором (hub). Сигналы от передающего компьютера поступают через концентратор ко всем остальным. Эта топология возникла на заре вычислительной техники, когда компьютеры были подключены к центральному, главному, компьютеру.

В сетях с топологией «звезда» подключение кабеля и управление конфигурацией сети централизованны. Но есть и недостаток: так как все компьютеры подключены к центральной точке, для больших сетей значительно увеличивается расход кабеля. К тому же, если центральный компонент выйдет из строя, нарушится работа всей сети. А если выйдет из строя только один компьютер (или кабель, соединяющий его с концентратором), то лишь этот компьютер не сможет передавать или принимать данные по сети. На остальные компьютеры в сети это не повлияет.

Кольцо

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

Передача маркера

Один из принципов передачи данных в кольцевой сети носит название передачи маркера. Суть его такова. Маркер последовательно, от одного компьютера к другому, передается до тех пор, пока его не получит тот, который «хочет» передать данные. Передающий компьютер изменяет маркер, помещает электронный адрес в данные и посылает их по кольцу.

Данные проходят через каждый компьютер, пока не окажутся у того, чей адрес совпадает с адресом получателя, указанным в данных. После этого принимающий компьютер посылает передающему сообщение, где подтверждает факт приёма данных. Получим подтверждение, передающий компьютер создаёт новый маркер и возвращает его в сеть. На первый взгляд кажется, что передача маркера отнимает много времени, однако на самом деле маркер передвигается приктически со скоростью света. В кольце диаметром 200 м маркер может циркулировать с частотой 10 000 оборотов в секунду.

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

ВВЕДЕНИЕ

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

Целью курсового проекта является оптимизация топологии сети по критерию минимальной протяженности методом ветвей и границ.

1 СРАВНИТЕЛЬНЫЙ АНАЛИЗ ТОПОЛОГИЙ СЕТЕЙ ТЕЛЕКОММУНИКАЦИЙ

1.1 Этапы развития сетей

телекоммуникационный сеть протяженность топология

Различные виды электросвязи длительный период времени развивались независимо друг от друга. Каждый вид электросвязи ориентировался на создание своих каналов, систем передачи (СП) и сетей. Структура сети выбиралась в соответствии с особенностями распределения потоков сообщений, характерных для конкретного виды электросвязи. Некоторые отрасли промышленности и транспорта стали создавать свои сети, предназначенные для удовлетворения потребностей отрасли в передаче сообщений. Разобщенность технических средств не только не позволяла повысить эффективность совокупности сетей в масштабах страны, но и тормозила развитие обособленных сетей. Поэтому уже в начале 1960-х гг. стало ясно, что перспективным направлением развития сетей должно было стать объединение сетей. Было принято решение о создании ЕАСС (Единая автоматизированная сеть связи). ЕАСС базировалась на объединении разрозненных и многочисленных мелких сетей в общегосударственные сети каждого вида электросвязи, а затем в единую сеть с целью совместного использования определенных технических средств, и, в первую очередь, систем передачи и систем коммутации.

При создании ЕАСС было учтено, что определенные технические средства участвуют в процессе передачи независимо от вида сообщений, т. е. являются общими. В связи с этим вся сеть страны стала подразделяться на две взаимосвязанные составляющие:

1) первичную сеть - совокупность сетевых станций, сетевых узлов (дать определение в приложении) и соединяющих их линий передачи, которая позволяет организовывать сеть каналов передачи и групповых трактов.

Структура первичной сети учитывает административное разделение территории страны. Вся территория поделена на зоны, совпадающие, как правило, с территорией областей, краев. В соответствии с этим первичная сеть также состоит из следующих частей:

* местные первичные сети - часть сети, ограниченная территорией города или сельского района;

* зоновые первичные сети - часть сети, охватывающая территорию зоны (область, край, республика), обеспечивающая соединение между собой каналов разных местных сетей внутри одной зоны;

* магистральная первичная сеть - часть сети, соединяющая между собой каналы разных зоновых сетей на всей территории страны.

Структура первичной сети показана на рисунке 1.1.

Рисунок 1.1 - Структура первичной сети

2) вторичная сеть - совокупность технических средств, обеспечивающих передачу сообщений определенного вида, в состав которой входят: оконечные устройства, абонентские и соединительные линии, коммутационные станции, а также каналы, выделенные из первичной сети для образования вторичной.

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

* телефонные;

* телеграфные;

* передачи данных;

* факсимильные;

* телевизионного вещания;

* звукового вещания.

1.2 Основные способы построения телекоммуникационных сетей связи

Одним из основных требований, предъявляемых к сетям передачи индивидуальных сообщений (телефонные, телеграфные, факсимильные, передачи данных), является то, что сеть должна обеспечить каждому пользователю возможность связаться с другим пользователем. Для выполнения этого требования сеть связи строится по определенному принципу в зависимости от условий функционирования. Следовательно, сети связи могут иметь различную структуру, т. е. отличаться числом и расположением узловых и оконечных пунктов (станций), а также характером их взаимосвязи. На рисунке 1.2 показаны способы построения сетей связи.

При полносвязанном способе построения (принцип «каждый с каждым») между узлами существует непосредственная связь. Используется при небольшом количестве узлов на сети (рисунок 1.2 а).

При радиальном способе построения сети связь между узлами осуществляется через центральный узел (рисунок 1.2 б). Используется при построении сети на сравнительно небольшой территории.

На большой территории сеть связи строится по радиально-узловому способу (рисунок 1.2 в).

Кольцевой способ построения сети предусматривает возможность осуществления связи как по часовой, так и против часовой стрелки (рис. 1.2 г). В этом случае при повреждении на определенном участке сеть сохраняет свою работоспособность.

При комбинированном способе построения сети узлы на верхнем иерархическом уровне связываются по полносвязанной схеме рисунок 1.2 д). В этом случае выход одного из узлов не нарушает работу всей сети.

Рисунок 1.2 - Способы построения сетей связи

2 ПОСТРОЕНИЕ МОДЕЛИ ТОПОЛОГИИ РАЗРАБАТЫВАЕМОЙ СЕТИ ТЕЛЕКОММУНИКАЦИЙ

Данные представляем в виде таблицы 2.1

Таблица 2.1- Расстояния между узлами проектируемой сети

Сморгонь

Островец

Плещеницы

Глубокое

Шарковщина

Молодечно

Радошковичи

Заславль

Задача коммивояжера .

Возьмем в качестве произвольного маршрута:

X 0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,7);(7,8);(8,9);(9,10);(10,11);(11,12); (12,13); (13,14); (14,15); (15,1);

Тогда F(X 0) = 56 + 31 + 32 + 80 + 27 + 77 + 80 + 29 + 155 + 87 + 66 + 21 + 43 + 17=801

3 РАЗРАБОТКА ВЫЧИСЛИТЕЛЬНОЙ ПРОЦЕДУРЫ ОПТИМИЗАЦИИ ТОПОЛОГИИ РАЗРАБАТЫВАЕМОЙ СЕТИ

Суть метода динамического программирования заключается в подходе к решению задачи по этапам, с каждым из которых ассоциирована одна управляемая переменная. Набор рекуррентных вычислительных процедур, связывающих различные этапы, обеспечивает получение допустимого оптимального решения задачи в целом при достижении последнего этапа.

Сморгонь

Островец

Плещеницы

Глубокое

Шарковщина

Молодечно

Радошковичи

Заславль

При решении задачи нахождения оптимального пути происходит разделение задачи на процессы (по количеству узлов), в данном случае на 15. Процесс начинается из узла № 1. Фактически не важно, откуда его начинать, все равно маршрут круговой и охватывает все узлы.

На первом этапе вычислительной процедурой будет расстояние от узла № 1 до каждого из оставшихся узлов.

№ процесса	Значение

На следующем этапе значение вычислительной процедуры принимает значение минимального расстояния в следующий (любой узел).

№ процесса	Значение 1 этапа	Значение 2 этапа

Выбирается минимум функции и осуществляется переход к следующему этапу. Следует обратить внимание, что из значений функций можно сразу убирать заведомо неправильные значения. Так же не следует учитывать значения ведущие в «обратную сторону».

4 РАЗРАБОТКА БЛОК-СХЕМЫ ПРОГРАММЫ-ОБОЛОЧКИ И БЛОК-СХЕМ ОСНОВНЫХ ПРОГРАММ-ПРОЦЕДУР ДЛЯ ОПТИМИЗАЦИИ ТОПОЛОГИИ СЕТИ

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

5 РАЗРАБОТКА И ОТЛАДКА ПРОГРАММЫ ОПТИМИЗАЦИИ ТОПОЛОГИИ СЕТИ ТЕЛЕКОММУНИКАЦИЙ ПО КРИТЕРИЮ МИНИМУМА ЕЕ ПРОТЯЖЕННОСТИ

Программа разработана на языке программирования Java. Java -- объектно-ориентированный язык программирования, разрабатываемый компанией Sun Microsystems с 1991 года и официально выпущенный 23 мая 1995 года. Изначально новый язык программирования назывался Oak (James Gosling) и разрабатывался для бытовой электроники, но впоследствии был переименован в Java и стал использоваться для написания апплетов, приложений и серверного программного обеспечения

Отличительной особенностью Java в сравнении с другими языками программирования общего назначения является обеспечение высокой продуктивности программирования, нежели производительность работы приложения или эффективность использования им памяти.

В Java используются практически идентичные соглашения для объявления переменных, передачи параметров, операторов и для управления потоком выполнением кода. В Java добавлены все хорошие черты C++.

Три ключевых элемента объединились в технологии языка Java

Java предоставляет для широкого использования свои апплеты (applets) -- небольшие, надежные, динамичные, не зависящие от платформы активные сетевые приложения, встраиваемые в страницы Web. Апплеты Java могут настраиваться и распространяться потребителям с такой же легкостью, как любые документы HTML

Java высвобождает мощь объектно-ориентированной разработки приложений, сочетая простой и знакомый синтаксис с надежной и удобной в работе средой разработки. Это позволяет широкому кругу программистов быстро создавать новые программы и новые апплеты

Java предоставляет программисту богатый набор классов объектов для ясного абстрагирования многих системных функций, используемых при работе с окнами, сетью и для ввода-вывода. Ключевая черта этих классов заключается в том, что они обеспечивают создание независимых от используемой платформы абстракций для широкого спектра системных интерфейсов

Огромное преимущество Java заключается в том, что на этом языке можно создавать приложения, способные работать на различных платформах. К сети Internet подключены компьютеры самых разных типов - Pentium PC, Macintosh, рабочие станции Sun и так далее. Даже в рамках компьютеров, созданных на базе процессоров Intel, существует несколько платформ, например, Microsoft Windows версии 3.1, Windows 95, Windows NT, OS/2, Solaris, различные разновидности операционной системы UNIX с графической оболочкой X­Windows. Между тем, создавая сервер Web в сети Internet, хотелось бы, чтобы им могло пользоваться как можно большее число людей. В этом случае выручат приложения Java, предназначенные для работы на различных платформах и не зависящие от конкретного типа процессора и операционной системы.

Исходные данные программа берет из текстового файла, представляющего собой таблицу. Путь к файлу прописан в теле программы. ПО умолчанию значение равно «D:\\cites.txt». Имеет значение количества городов, в случае изменения их количества, необходимо изменить значение переменной n.

Для удобства вывода результатов в программе указано наименование городов, для их изменения также необходимо менять код программы. При не изменении названий, программа корректно работает и за основу можно взять номера городов.

Вывод результатов оптимизации производится на экран, с указанием общей протяженности маршрута.

6 РАСЧЕТ ОПТИМАЛЬНОЙ ТОПОЛОГИИ РАЗРАБАТЫВАЕМОЙ СЕТИ ТЕЛЕКОММУНИКАЦИЙ И АНАЛИЗ МОДЕЛИ ТОПОЛОГИИ СЕТИ НА ЧУВСТВИТЕЛЬНОСТЬ К ИЗМЕНЕНИЮ ПАРАМЕТРОВ

Результат работы программы представлены на рисунке 5.2. При этом результат проверен в других алгоритмах.

Схема маршрута с привязкой к карте РБ представлена на рисунке 6.1.

ЗАКЛЮЧЕНИЕ

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

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

1. Таха Х. Введение в исследование операций / пер. с англ. -М.: Вильямс, 2005.

2. Банди Б. Методы оптимизации. Вводный курс. -М.: Радио и связь, 1988.

3. Васильев Ф.В. Численные методы решения экстремальных задач. -М.: Наука, 1980.

ПРИЛОЖЕНИЕ А

ТЕКСТ ПРОГРАММЫ

import java.io.*;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

import java.util.StringTokenizer;

public class ShortestPathDynamicMethods {

public static int readDistancesFromFile() throws FileNotFoundException {

File f1 = new File("D:\\Cities2.txt");

BufferedReader input = new BufferedReader(new FileReader(f1));

BufferedReader input1 = new BufferedReader(new FileReader(f1));

int NUMBER_CITIES = 0;

String line = null;

while ((line = input1.readLine()) != null) {

NUMBER_CITIES++;

} catch (IOException e) {

e.printStackTrace();

int array = new int;

String line = null;

while ((line = input.readLine()) != null) {

StringTokenizer st = new StringTokenizer(line);

while (st.hasMoreTokens()) {

String tkn = st.nextToken();

//System.out.println(tkn);

array[i][j] = Integer.parseInt(tkn);

} catch (IOException e) {

e.printStackTrace();

public static int getShortestDistance(int dist) {

List cityList = new ArrayList();

cityList.add("Ивье");

cityList.add("Ошмяны");

cityList.add("Сморгонь");

cityList.add("Островец");

cityList.add("Поставы");

cityList.add("Мядель");

cityList.add("Плещеницы");

cityList.add("Глубокое");

cityList.add("Шарковщина");

cityList.add("Воложин");

cityList.add("Логойск");

cityList.add("Молодечно");

cityList.add("Вилейка");

cityList.add("Радошковичи");

cityList.add("Заславль");

int n = dist.length;

int dp = new int[n];

for (int d: dp)

Arrays.fill(d, Integer.MAX_VALUE / 2);

for (int mask = 1; mask < 1 << n; mask += 2) {

for (int i = 1; i < n; i++) {

if ((mask & 1 << i) != 0) {

for (int j = 0; j < n; j++) {

if ((mask & 1 << j) != 0) {

dp[i] = Math.min(dp[i], dp[j] + dist[j][i]);

int res = Integer.MAX_VALUE;

for (int i = 1; i < n; i++) {

res = Math.min(res, dp[(1 << n) - 1][i] + dist[i]);

int cur = (1 << n) - 1;

int order = new int[n];

for (int i = n - 1; i >= 1; i--) {

for (int j = 1; j < n; j++) {

if ((cur & 1 << j) != 0 && (bj == -1 || dp + dist > dp[j] + dist[j])) {

cur ^= 1 << bj;

System.out.println("Порядок обхода городов: ");

for (int i = 0; i < order.length; i++)

System.out.println((i + 1) + " " + cityList.get(order[i]));

public static void main(String args) {

System.out.println("Минимальное расстояние: " + getShortestDistance(ShortestPathDynamicMethods.readDistancesFromFile()));

} catch (Exception e) {

e.printStackTrace();

Размещено на Allbest.ru

Подобные документы

Роль и общие принципы построения компьютерных сетей. Топологии: шинная, ячеистая, комбинированная. Основные системы построения сетей "Token Ring" на персональных компьютерах. Протоколы передачи информации. Программное обеспечение, технология монтажа сети.

курсовая работа , добавлен 11.10.2013


Расчет сетей с минимальной протяженностью ветвей. Модель структуры сети соединении станций по принципу "каждая с каждой". Определение числа каналов между пунктами сети. Распределение каналов по ветвям сети, обеспечивающее минимальную протяженность связей.

курсовая работа , добавлен 19.12.2013


Изучение состава и структуры междугородной телефонной сети, плана распределения каналов вторичной сети. Анализ схемы разговорного тракта между телефонными аппаратами разных местных сетей. Расчет путей, сечений и надежности коммутируемой телефонной сети.

курсовая работа , добавлен 19.03.2012


Топология сети: общее понятие и разновидности. Активные и пассивные топологии, их главные особенности. Методы расширения сети. Расширение сети с топологией "звезда", обзор основных способов. Попарное соединение устройств при организации локальной сети.

презентация , добавлен 25.10.2013


Роль компьютерных сетей, принципы построения. Протоколы передачи информации в сети ArcNet, используемые топологии и средства связи. Программное обеспечение, технология развёртки. Операционные системы компьютерных сетей. Инструкция по технике безопасности.

курсовая работа , добавлен 11.10.2013


Изучение топологии NGN сети - сети связи следующего поколения, обеспечивающей передачу всех видов медиатрафика с различными требованиями к качеству обслуживания и их поддержкой. Перспективы применения технологии NGN для построения мультисервисной сети.

курсовая работа , добавлен 25.08.2010


Современные технологии доступа в сети Интернет. Беспроводные системы доступа. Оптико-волоконные и волоконно-коаксиальные системы. Существующие топологии сетей. Выбор топологии, оптического кабеля и трассы прокладки. Экономическое обоснование проекта.

дипломная работа , добавлен 17.04.2014


Анализ способов построения телефонных сетей общего пользования. Расчет интенсивности телефонной нагрузки на сети, емкости пучков соединительных линий. Выбор структуры первичной сети. Выбор типа транспортных модулей SDH и типа оптического кабеля.

курсовая работа , добавлен 22.02.2014


Сфера применения локальных вычислительных сетей как способа соединения компьютеров. Основные топологии, применяемые при построении компьютерных сетей. Одноранговые и иерархические локальные сети. Сущность кабельных и оптоволоконных способов связи.

реферат , добавлен 12.05.2014


Основные типовые топологии вычислительных сетей, их изучение, анализ, оценка. Вывод о работе сетей с различной топологией (цепочечной, полносвязной, ячеистой, комбинированной). Преимущества и недостатки топологий, влияющих на производительность сети.

Под топологией (компоновкой, конфигурацией, структурой) компьютерной сети обычно понимается физическое расположение компьютеров сети один относительно одного и способ соединения их линиями связи. Важно отметить, что понятие топологии относится, в первую очередь, к локальным сетям, в которых структуру связей можно легко проследить. В глобальных сетях структура связей обычно спрятана от пользователей не слишком важная, потому что каждый сеанс связи может выполняться по своему собственному пути.
Топология определяет требования к оборудованию, тип используемого кабеля, возможные и наиболее удобные методы управления обменом, надежность работы, возможности расширения сети.

Существует три основные топология сети:

1. Сетевая топология шина (bus), при которой все компьютеры параллельно подключаются к одной линии связи и информация от каждого компьютера одновременно передается всем другим компьютерам (рис. 1);

2. Cетевая топология звезда (star), при которой к одному центральному компьютеру присоединяются другие периферийные компьютеры, причем каждый из них использует свою отдельную линию связи (рис. 2);

3. Cетевая топология кольцо (ring), при которой каждый компьютер передает информацию всегда только одному компьютеру, следующему в цепочке, а получает информацию только от предыдущего компьютера в цепочке, и эта цепочка замкнута в «кольцо» (рис. 3).

Рис. 1. Сетевая топология «шина»

Рис. 2. Сетевая топология «звезда»

Рис. 3. Сетевая топология «кольцо»

На практике нередко используют и комбинации базовой топологии, но большинство сетей ориентированные именно на этих три. Рассмотрим теперь коротко особенности перечисленной сетевой топологии.

Топология «шина» (или, как ее еще называют, «общая шина») самой своей структурой допускает идентичность сетевого оборудования компьютеров, а также равноправие всех абонентов. При таком соединении компьютеры могут передавать только по очереди, потому что линия связи единственная. В противном случае переданная информация будет искажаться в результате наложения (конфликту, коллизии). Таким образом, в шине реализуется режим полудуплексного (half duplex) обмена (в обоих направлениях, но по очереди, а не одновременно).
В топологии «шина» отсутствует центральный абонент, через которого передается вся информация, которая увеличивает ее надежность (ведь при отказе любого центра перестает функционировать вся управляемая этим центром система). Добавление новых абонентов в шину достаточно простое и обычно возможно даже во время работы сети. В большинстве случаев при использовании шины нужно минимальное количество соединительного кабеля по сравнению с другой топологией. Правда, нужно учесть, что к каждому компьютеру (кроме двух крайних) подходит два кабеля, что не всегда удобно.
Потому что разрешение возможных конфликтов в этом случае ложится на сетевое оборудование каждого отдельного абонента, аппаратура сетевого адаптера при топологии «шина» выходит сложнее, чем при другой топологии. Однако через широкое распространение сетей с топологией «шина» (Ethernet, Arcnet) стоимость сетевого оборудования выходит не слишком высокой.
Шине не страшные отказы отдельных компьютеров, потому что все другие компьютеры сети могут нормально продолжать обмен. Может показаться, что шине не страшный и обрыл кабелю, поскольку в этом случае мы одержимо две полностью работоспособных шины. Однако через особенности распространения электрических сигналов по длинным линиям связи необходимо предусматривать включение на концах шины специальных устройств – терминаторов, показанных на рис. 1 в виде прямоугольников. Без включения терминаторов сигнал отражается от конца линии и искажается так, что связь по сети становится невозможной. Так что при разрыве или повреждении кабеля нарушается согласование линии связи, и прекращается обмен даже между теми компьютерами, которые остались соединенными между собой. Короткое замыкание в любой точке кабеля шины выводит из строя всю сеть. Любой отказ сетевого оборудования в шине очень трудно локализовать, потому что все адаптеры включены параллельно, и понять, который из них вышел из строя, не так-то просто.
При прохождении по линии связи сети с топологией «шина» информационные сигналы ослабляются и никак не возобновляются, что налагает твердые ограничения на суммарную длину линий связи, кроме того, каждый абонент может получать из сети сигналы разного уровня в зависимости от расстояния к передаточному абоненту. Это выдвигает дополнительные требования к приемным узлам сетевого оборудования. Для увеличения длины сети с топологией «шина» часто используют несколько сегментов (каждый из которых являет собой шину), соединенных между собой с помощью специальных обновителей сигналов - репитеров.
Однако такое наращивание длины сети не может длиться бесконечно, потому что существуют еще и ограничения, связанные с конечной скоростью распространения сигналов по линиям связи.

Топология «Звезда» - это топология с явно выделенным центром, к которому подключаются все другие абоненты. Весь обмен информацией идет исключительно через центральный компьютер, на который таким способом ложится очень большая нагрузка, потому ничем другим, кроме сети, оно заниматься не может. Понятно, что сетевое оборудование центрального абонента должно быть существенно больше сложным, чем оборудование периферийных абонентов. О равноправии абонентов в этом случае говорить не придется. Как правило, именно центральный компьютер является самим мощным, и именно на него возлагают все функции по управлению обменом. Никакие конфликты в сети с топологией «звезда» в принципе невозможные, потому что управление полностью централизовано, конфликтовать нет почему.
Если говорить о стойкости звезды к отказам компьютеров, то выход из строя периферийного компьютера никак не отражается на функционировании части сети, которая осталась, зато любой отказ центрального компьютера делает сеть полностью неработоспособной. Поэтому должны приниматься специальные мероприятия по повышению надежности центрального компьютера и его сетевой аппаратуры. Обрыл любого кабеля или короткое замыкание в нем при топологии «звезда» нарушает обмен только с одним компьютером, а все другие компьютеры могут нормально продолжать работу.
На склонение от шины, в звезде на каждой линии связи находятся только два абонента: центральный и один из периферийных. Чаще всего для их соединения используется две линии связи, каждая из которых передает информацию только в одном направлении. Таким образом, на каждой линии связи есть только один приемник и один передатчик. Все это существенно упрощает сетевое установление в сравнении с шиной и спасает от необходимости применение дополнительных внешних терминаторов. Проблема затухания сигналов в линии связи также решается в «звезде» проще, чем в «шине», ведь каждый приемник всегда получает сигнал одного уровня. Серьезный недостаток топологии «звезда» складывается в жестком ограничении количества абонентов. Обычно центральный абонент может обслуживать не больше 8-16 периферийных абонентов. Если в этих пределах подключения новых абонентов достаточно просто, то при их превышении оно просто невозможно. Правда, иногда в звезде предусматривается возможность наращивания, то есть подключение вместо одного из периферийных абонентов еще одного центрального абонента (в итоге выходит топология из нескольких соединенных между собой звезд).
Звезда, показанная на рис. 2, зовется активной, или настоящей звезды. Существует также топология, которая называется пассивной звездой, что только внешне похожая на звезду (рис. 4). В это время она распространена намного больше, чем активная звезда. Достаточно сказать, что она используется в самой популярной на сегодняшний день сети Ethernet.

Рис. 4. Топология «пассивная звезда»

В центре сети с данной топологией содержится не компьютер, а концентратор, или хаб (hub), что выполняет ту же функцию, что и репитер. Он возобновляет сигналы, которые поступают, и пересылает их в другие линии связи. Хотя схема прокладки кабелей подобна настоящей или активной звезде, фактически мы имеем дело с шинной топологией, потому что информация от каждого компьютера одновременно передается ко всем другим компьютерам, а центрального абонента не существует. Естественно, пассивная звезда выходит дороже обычной шины, потому что в этом случае обязательно нужно еще и концентратор. Однако она предоставляет целый ряд дополнительных возможностей, связанных с преимуществами звезды. Именно поэтому в последнее время пассивная звезда все больше вытесняет настоящую звезду, которая считается малоперспективной топологией.
Можно выделить также промежуточный тип топологии между активной и пассивной звездой. В этом случае концентратор не только ретранслирует сигналы, но и делает управление обменом, однако сам в обмене не принимает участие.
Большое преимущество звезды (как активной, так и пассивной) заключается в том, что все точки подключения собраны в одном месте. Это позволяет легко контролировать работу сети, локализовать неисправности сети путем простого отключения от центра тех или других абонентов (что невозможно, например, в случае шины), а также ограничивать доступ посторонних лиц к жизненно важному для сети точкам подключения. К каждому периферийному абоненту в случае звезды может подходить как один кабель (по которому идет передача в обоих направлениях), так и два кабеля (каждый из них передает в одном направлении), причем вторая ситуация встречается чаще. Общим недостатком для всей топологии типа «звезда» значительно больше, чем при другой топологии, затрата кабеля. Например, если компьютеры расположены в одну линию (как на рис. 1), то при выборе топологии «звезда» понадобится в несколько раз больше кабеля, чем при топологии «шина». Это может существенно повлиять на стоимость всей сети в целом.

Топология «Кольцо» – это топология, в которой каждый компьютер соединен линиями связи только с двумя другими: от одного он только получает информацию, а другому только передает. На каждой линии связи, как и в случае звезды, работает только один передатчик и один приемник. Это позволяет отказаться от применения внешних терминаторов. Важна особенность кольца заключается в том, что каждый компьютер ретранслирует (возобновляет) сигнал, то есть выступает в роли репитера, потому затухание сигнала во всем кольце не имеет никакого значения, важно только затухание между соседними компьютерами кольца. Четко выделенного центра в этом случае нет, все компьютеры могут быть одинаковыми. Однако достаточно часто в кильке выделяется специальный абонент, который управляет обменом или контролирует обмен. Понятно, что наличие такого управляющего абонента снижает надежность сети, потому что выход его из строя сразу же парализует весь обмен.
Строго говоря, компьютеры в кильке не являются полностью равноправными (в отличие, например, от шинной топологии). Одни из них обязательно получают информацию от компьютера, который ведет передачу в этот момент, раньше, а другие – позже. Именно на этой особенности топологии и строятся методы управления обменом по сети, специально рассчитанные на «кольцо». В этих методах право на следующую передачу (или, как еще говорят, на захвата сети) переходит последовательно к следующему по кругу компьютеру.
Подключение новых абонентов в «кольцо» обычно совсем безболезненно, хотя и требует обязательной остановки работы всей сети на время подключения. Как и в случае топологии «шина», максимальное количество абонентов в кильке может быть достаточно большая (до тысячи и больше). Кольцевая топология обычно является самой стойкой к перегрузкам, она обеспечивает уверенную работу с самими большими потоками переданной по сети информации, потому что в ней, как правило, нет конфликтов (в отличие от шины), а также отсутствует центральный абонент (в отличие от звезды).
Потому что сигнал в кильке проходит через все компьютеры сети, выход из строя хотя бы одного из них (или же его сетевого встановление) нарушает роботу всей сети в целом. Точно так же любой обрыв или короткое замыкание в каждом из кабелей кольца делает работу всей сети невозможной. Кольцо наиболее уязвимо к повреждениям кабеля, потому в этой топологии обычно предусматривают прокладку двух (или больше) параллельных линий связи, одна из которых находится в резерве.
В то же время большое преимущество кольца заключается в том, что ретрансляция сигналов каждым абонентом позволяет существенно увеличить размеры всей сети в целом (временами до нескольких десятков километров). Кольцо относительно этого существенно превосходит любую другую топологию.

Недостатком кольца (в сравнении со звездой) можно считать то, что к каждому компьютеру сети необходимо подвести два кабеля.

Иногда топология «кольцо» выполняется на основе двух кольцевых линий связи, которые передают информацию в противоположных направлениях. Цель подобного решения – увеличение (в идеале вдвое) скорости передачи информации. К тому же при повреждении одного из кабелей сеть может работать с другим кабелем (правда, предельная скорость уменьшится).
Кроме трех рассмотренной основной, базовой топологии нередко применяется также сетевая топология «дерево» (tree), которую можно рассматривать как комбинацию нескольких звезд. Как и в случае звезды, дерево может быть активным, или настоящим (рис. 5), и пассивным (рис. 6). При активном дереве в центрах объединения нескольких линий связи находятся центральные компьютеры, а при пассивном - концентраторы (хабы).

Рис. 5. Топология «активное дерево»

Рис. 6. Топология «пассивное дерево». К - концентраторы

Применяется достаточно часто и комбинированная топология, например звездно шинная, звездно кольцевая.

Многозначительность понятия топологии.

Топология сети определяет не только физическое расположение компьютеров, но, что намного более важное, характер связей между ними, особенности распространения сигналов по сети. Именно характер связей определяет степень отказостойкости сети, необходимую сложность сетевой аппаратуры, наиболее подходящий метод управления обменом, возможны типы сред передачи (каналов связи), допустимый размер сети (длина линий связи и количество абонентов), необходимость электрического согласования, и много чего другого.
Когда в литературе вспоминается о топологии сети, то могут иметь в виду четыре совсем разных понятия, которые относятся к разным уровням сетевой архитектуры:

1. Физическая топология (то есть схема расположения компьютеров и прокладки кабелей). В этом содержании, например, пассивная звезда ничем не отличается от активной звезды, потому ее нередко называют просто «звездой».

2. Логическая топология (то есть структура связей, характер распространения сигналов по сети). Это, наверно, наиболее правильное определение топологии.

3. Топология управления обменом (то есть принцип и последовательность передачи права на восторг сети между отдельными компьютерами).

4. Информационная топология (то есть направление потоков информации, переданной по сети).

Например, сеть с физической и логической топологией «шина» может как метод управления использовать эстафетную передачу права захвата сети (то есть быть в этом содержании кольцом) и одновременно передавать всю информацию через один выделен компьютер (быть в этом содержании звездой).

Основные понятия. Большое количество графических данных в ГИС со специфическими взаимными связями требует топологического описания объектов и групп объектов, которое зависит от "связанности" (простой или сложной). Оно определяет совокупность топологических моделей.

Напомним, что топологические свойства фигур не изменяются при любых деформациях, производимых без разрывов или соединений. На рис. 4.8 представлены топологически родственные фигуры: прямоугольный четырехугольник, замкнутый контур произвольной формы, окруж­ность, треугольник. Эти объекты (фигуры) имеют одинаковую топологию - одинаковые топологические свойства. Другим примером топо­логически родственных фигур могут служить арифметические знаки сложения " + " и умножения " х ".

Рис. 4.8. Топологически родственные фигуры

В геоинформационных системах применение термина топологический не такое строгое, как в топологии. В ГИС топологическая модель определяется наличием и хранением совокупностей взаимосвязей, таких, как соединенность дуг на пересечениях, упорядоченный набор звень­ев (цепей), образующих границу каждого полигона, взаимосвязи смежности между ареалами и т.п.

В общем смысле слово топологический означает, что в модели объекта хранятся взаимосвязи, которые расширяют использование данных ГИС дляразличных видов пространственного анализа.

Топологическими характеристиками графические модели ГИС существенно отличаются от моделей САПР. Соответственно это различие просматривается в программно-технологическом обеспечении этих систем.

Например, вплоть до настоящего времени много разработок ГИС выполняется с использованием средств Автокада, версий от 10 до 13. Однако в нем не предусмотрены ни работа с покрытиями, ни оверлейные процедуры, ни обработка топологических данных. Принципиально такие операции в системах CAD (Computer-Aided Desing) возможны, но путем доработки программного обеспечения, что требует достаточно высокой квалификации пользователя и, естественно, ограничивает их круг.

В системах ГИС названные выше процедуры являются встроенными и делают доступным анализ картографической информации широ­кому кругу пользователей без всякой доработки.

Элементы топологии, входящие в описание моделей данных ГИС, в простейшем случае определяются связями между элементами основных типов координатных данных. Например, в логическую структуру ("логическая запись" см. разд. 3) описания данных могут входить указания о том, какие линии входят в район, в каких точках эти линии пересекаются. Топологические модели позволяют представлять элементы карты и всю карту в целом в виде графов. Площади, линии и точки описываются границами и узлами (дуговая/узловая структура). Каждая граница идет от начального к конечному узлу, и известно, какие площади находятся слева и справа.

Теоретической основой моделей служат алгебраическая топология и теория графов. В соответствии с алгебраической топологией координатные типы данных: площади, линии и точки называются 2-ячейками, 1-ячейками и 0-ячейками соответственно. Карта рассматривается как ориентированный двухмерный ячеечный комплекс.

Двойственность между теорией графов и алгебраической топологи­ей позволяет применять теоретические положения графов, а также то­пологический подход.

Топологическое векторное представление данных отличается от нетопологического наличием возможности получения исчерпывающего списка взаимоотношений между связанными геометрическими примитивами без изменения хранимых координат пространственных объектов.

Необходимая процедура при работе с топологической моделью -подготовка геометрических данных для построения топологии. Этот процесс не может быть полностью автоматизирован уже на данных средней сложности и реализуется только при дополнительных затратах тру­да (обычно значительных). Таким образом, данные, хранимые в системе, не предусматривающей поддержки топологии, не могут быть надежно преобразованы в топологические данные другой системы чисто автоматическим алгоритмом.

Топологические характеристики должны вычисляться в ходе количественных преобразований моделей объектов ГИС, а затем храниться в базе данных совместно с координатными данными.

Основные топологические характеристики моделей ГИС. Топологические модели в ГИС задаются совокупностью следующих харак­теристик:

Связанность векторов - контуры, дороги и прочие векторы должны храниться не как независимые наборы точек, а как взаимосвязанные друг с другом объекты;

" связанность и примыкание районов - информация о взаимном рас­положении районов и об узлах пересечения районов (рис. 4.9, в);

пересечение - информация о типах пересечений позволяет вос­ производить мосты и дорожные пересечения (рис. 4.9, а). Так Т-образ­ ное пересечение (3 линии) является трехвалентным, а Х-образное (4 линии сходятся в точке пересечения) называют четырехвалентным;

близость - показатель пространственной близости линейных или ареальных объектов (рис. 4.9, б), оценивается числовым параметром, в данном случае символом 5.

Топологические характеристики линейных объектов могут быть представлены визуально с помощью связанных графов. Граф сохраняет структуру модели со всеми узлами и пересечениями. Он напоминает карту с искаженным масштабом. Примером такого графа может служить схема метрополитена. Разница между картой метро и схемой метро по­казывает разницу между картой и графом.

Узлы графа, описывающего картографическую модель, соответству­ют пересечениям дорог, местам смыкания дорог с мостами и т.п. Ребра такого графа описывают участки дорог и соединяющие их объекты. В отличие от классической сетевой модели в данной модели длина ребер может не нести информативной нагрузки.

Рис. 4.9. Основные топологические свойства моделей ГИС: а - пересечение; б - близость; в – связанность

Топологические характеристики ареальных объектов могут быть представлены с помощью графов покрытия и смежности. Граф покры­тия топологически гомоморфен контурной карте соответствующих районов. Ребра такого графа описывают границы между районами, а его узлы (вершины) представляют точки смыкания районов. Степень вер­шины такого графа - это число районов, которые в ней смыкаются. Граф смежности это как бы вывернутый наизнанку граф покрытия. В нем рай­оны отображаются узлами (вершинами), а пара смыкающихся районов -ребрами. На основе такого графа ГИС может выдать ответ на вопрос, является ли проходимой рассматриваемая территория, разделенная на проходимые или непроходимые участки.

Топологические характеристики сопровождаются позиционной и описательной информацией. Вершина графа покрытия может быть до-

полнена координатными точками, в которых смыкаются соответствую­щие районы, а ребрам приписывают левосторонние и правосторонние идентификаторы.

После введения точечных объектов при построении линейных и площадных объектов необходимо "создать" топологию. Эти процессы включают вычисление и кодирование связей между точками, линиями и ареалами.

Пересечения и связи имеют векторное представление. Топологичес­кие характеристики заносятся при кодировании данных в виде дополни­тельных атрибутов. Этот процесс осуществляется автоматически во мно­гих ГИС в ходе дигитализации (картографических или фотограмметри­ческих) данных.

Объекты связаны множеством отношений между собой. Это опре­деляет эффективность применения реляционных моделей и баз данных, в основе которых используется понятие отношения. В свою оче­редь, отношения задают множества связей. Простейшие примеры таких связей: "ближайший к...", "пересекает", "соединен с...".

Каждому объекту можно присвоить признак, который представляет собой идентификатор ближайшего к нему объекта того же класса; таким образом кодируются связи между парами объектов.

В ГИС часто кодируются два особых типа связей: связи в сетях и связи между полигонами.

Топологически сети состоят из объектов двух типов: линий (звенья, грани, ребра, дуги) и узлов (вершины, пересечения, соединения).

Простейший способ кодирования связей между звеньями и узлами зак­лючается в присвоении каждому звену двух дополнительных атрибутов -идентификаторов узлов на каждом конце (входной узел и выходной узел).

В этом случае при кодировании геометрических данных будут иметь место два типа записей:

координаты дуг: (x1,y1), (х2,у2), ..., (xn,yn);

атрибуты дуг: входной узел, выходной узел, длина, описательные характеристики.

Такая структура позволяет, перемещаясь от звена к звену, опреде­лять те из них, у которых перекрываются номера узлов.

Более сложная, но и более совершенная структура имеет список всех звеньев для каждого узла. Это может быть выполнено добавлением к первым двум записи третьего типа;

3) узел: (х, у), смежные дуги (со знаком "+" для входного угла и со знаком "-" - для выходного).

Чтобы избежать неудобств, связанных с хранением неодинакового количества идентификаторов дуг, используют два отдельных файла:

простой упорядоченный список, в котором файл узлов сжат до ряда идентификаторов дуг;

таблицу, в которой для каждого узла хранится информация о по­ ложении первой дуги списка.

Используемое в настоящее время математическое обеспечение ГИС почти исключительно основано на топологических моделях, дающих хорошее формализованное представление о пространственных соотно­шениях между основными объектами карты. Однако, если требуется установить более сложные соотношения, например включение или по­рядок, нужны дополнительные средства.

Растровые модели

Основы построения. Напомним, что модель данных представляет собой отображение непрерывных последовательностей реального мира в набор дискретных объектов.

В растровых моделях дискретизация осуществляется наиболее про­стым способом - весь объект (исследуемая территория) отображается в пространственные ячейки, образующие регулярную сеть. При этом каж­дой ячейке растровой модели соответствует одинаковый по размерам, но разный по характеристикам (цвет, плотность) участок поверхности объекта. В ячейке модели содержится одно значение, усредняющее ха­рактеристику участка поверхности объекта. В теории обработки изоб­ражений эта процедура известна под названием пикселизация.

Если векторная модель дает информацию о том, где расположен тот или иной объект, то растровая - информацию о том, что расположено в той или иной точке территории. Это определяет основное назначение растровых моделей - непрерывное отображение поверхности.

В растровых моделях в качестве атомарной модели используют двух­мерный элемент пространства - пиксель (ячейка). Упорядоченная сово­купность атомарных моделей образует растр, который, в свою очередь, является моделью карты или геообъекта.

Векторные модели относятся к бинарным или квазибинарным. Рас­тровые позволяют отображать полутона.

Как правило, каждый элемент растра или каждая ячейка должны иметь лишь одно значение плотности или цвета. Это применимо не для всех случаев. Например, когда граница двух типов покрытий может про-

Ходить через центр элемента растра, элементу дается значение, характе­ризующее большую часть ячейки или ее центральную точку. Ряд систем позволяет иметь несколько значений для одного элемента растра.

Характеристики растровых моделей. Для растровых моделей су­ществует ряд характеристик: разрешение, значение, ориентация, зоны, положение.

Разрешение - минимальный линейный размер наименьшего участ­ка пространства (поверхности), отображаемый одним пикселем.

Пиксели обычно представляют собой прямоугольники или квадра­ты, реже используются треугольники и шестиугольники. Более высо­ким разрешением обладает растр с меньшим размером ячеек. Высокое разрешение подразумевает обилие деталей, множество ячеек, минималь­ный размер ячеек.

Значение - элемент информации, хранящийся в элементе растра (пикселе). Поскольку при обработке применяют типизированные дан­ные, то есть необходимость определить типы значений растровой мо­дели.

Тип значений в ячейках растра определяется как реальным явлени­ем, так и особенностями ГИС. В частности, в разных системах можно использовать разные классы значений: целые числа, действительные (десятичные) значения, буквенные значения.

Целые числа могут служить характеристиками оптической плотно­сти или кодами, указывающими на позицию в прилагаемой таблице или легенде. Например, возможна следующая легенда, указывающая наиме­нование класса почв: 0 - пустой класс, 1 - суглинистые, 2 - песчаные, 3 - щебнистые и т.п.

Ориентация - угол между направлением на север и положением колонок растра.

Зона растровой модели включает соседствующие друг с другом ячейки, имеющие одинаковое значение. Зоной могут быть отдельные объекты, природные явления, ареалы типов почв, элементы гидро­графии и т.п.

Для указания всех зон с одним и тем же значением используют по­нятие класс зон. Естественно, что не во всех слоях изображения могут присутствовать зоны. Основные характеристики зоны - ее значение и положение.

Буферная зона - зона, границы которой удалены на известное рас­стояние от любого объекта на карте. Буферные зоны различной ширины могут быть созданы вокруг выбранных объектов на базе таблиц сопря­женных характеристик.

Положение обычно задается упорядоченной парой координат (но­мер строки и номер столбца), которые однозначно определяют положе­ние каждого элемента отображаемого пространства в растре.

Проводя сравнение векторных и растровых моделей, отметим удобство векторных для организации и работы со взаимосвязями объектов. Тем не менее, используя простые приемы, например включая взаимосвязи в таб­лицы атрибутов, можно организовать взаимосвязи и в растровых системах..

Необходимо остановиться на вопросах точности отображения в ра­стровых моделях. В растровых форматах в большинстве случаев неяс­но, относятся координаты к центральной точке пикселя или к одному из его углов. Поэтому точность привязки элемента растра определяют как 1/2 ширины и высоты ячейки.

Растровые модели имеют следующие достоинства:

растр не требует предварительного знакомства с явлениями, дан­ ные собираются с равномерно расположенной сети точек, что позволя­ ет в дальнейшем на основе статистических методов обработки получать объективные характеристики исследуемых объектов. Благодаря этому растровые модели могут использоваться для изучения новых явлений, о которых не накоплен материал. В силу простоты этот способ получил наибольшее распространение;

растровые данные проще для обработки по параллельным алго­ ритмам и этим обеспечивают более высокое быстродействие по сравне­ нию с векторными;

некоторые задачи, например создание буферной зоны, много про­ ще решать в растровом виде;

многие растровые модели позволяют вводить векторные данные, в то время как обратная процедура весьма затруднительна для векторных моделей;

процессы растеризации много проще алгоритмически, чем про­ цессы векторизации, которые зачастую требуют экспертных решений.

Наиболее часто растровые модели применяют при обработке аэро­космических снимков для получения данных дистанционных исследо­ваний Земли.

Метод группового кодирования. Самый простой способ ввода рас­тровых моделей - прямой ввод одной ячейки за другой. Н едо статкам и данного подхода являются требования большого объема памяти в компью­тере и значительного времени для организации процедур ввода-вывода. Например, снимок искусственного спутника Земли (ИСЗ) Landsat имеет 74 000 000 элементов растра и это требует огромных ресурсов для хране­ния данных.

При растровом вводе информации в ГИС возникает проблема ее Сжатия, так как наряду с полезной может попадать и избыточная (в том числе и бесполезная) информация. Для сжатия информации, получен­ной со снимка или карты, применяется кодирование участков развертки или метод группового кодирования, учитывающий, что довольно часто В нескольких ячейках значения повторяются.

Суть метода группового кодирования состоит в том, что данные вво­дятся парой чисел, первое обозначает длину группы, второе - значение. Изображение просматривается построчно, и как только определенный тип элемента или ячейки встречается впервые, он помечается призна­ком начала. Если за данной ячейкой следует цепочка ячеек того же типа, то их число подсчитывается, а последняя ячейка помечается признаком конца. В этом случае в памяти хранятся только позиции помеченных ячеек и значения соответствующих счетчиков.

Применение такого метода значительно упрощает хранение и вос­произведение изображений (карт), когда однородные участки (как пра­вило) превосходят размеры одной ячейки.

Обычно ввод осуществляют слева направо, сверху вниз. Рассмот­рим, например, бинарный массив матрицы (5x6):

0 0 1110

0 0 1 1 10

При использовании метода группового кодирования он будет вво­диться как:

303 1203 1 303 1205 1105 1.

Вместо 30 необходимо только 20 элементов данных. В рассмотрен­ном примере экономия составляет 30 %, однако на практике при работе с большими массивами бинарных данных она бывает гораздо больше.

Метод группового кодирования имеет ограничения и может исполь­зоваться далеко не во всех ГИС.

Элементы бинарной матрицы, т.е. растровой модели, могут прини­мать только два значения: "1" или "0". Эта матрица соответствует чер­но-белому изображению. На практике возможно полутоновое или цвет­ное изображение. В этих случаях значения в ячейках растровой модели могут различаться по типам. Тип значений в ячейках растра определяет­ся как исходными данными, так и особенностями программных средств ГИС. В качестве значений растровых данных могут быть применены це­лые числа, действительные (десятичные) значения, буквенные значения.

В одних системах используются толькоцелые числа, в других - различные типы данных. при этом ставится условие единствазначений для отдельных растровых слоев. Целые числа часто служат кодами, указывающими на позицию в прилагаемой таблице или легенде.

Структурно определенные растровые модели. Растровые модели делятся на регулярные, нерегулярные и аложенные (рекурсивные или иерархические) мозаики (рис. 4.10).

рис 4 10. Растровые модели: а - регулярная прямоугольная решетка б - регулярная треугольная решетка, в - полигоны Тиссена

Сканировано

Плоские регулярные мозаики бывают трех типов: квадрат (рис. 4. 10, а), треугольник и шестиугольник (рис. 4.10, б). Квадрат - самая удобная модель, так как позволяет относительно просто проводить обработку больших массивов данных. Треугольные мозаики служат хорошей ос­новой для создания выпуклых (сферических) покрытий.

Среди нерегулярных мозаик чаще всего используют треугольные сети неправильной формы (Triangulated Irregular Network - TIN) и полигоны Тиссена (рис. 4.10, в). Сети TIN удобны для создания цифровых моде­лей отметок местности по заданному набору точек. Они применяются как в растровых, так и в векторных моделях.

Модель треугольной нерегулярной сети (TIN) в значительной мере альтернативна цифровой модели рельефа, построенной на регулярной сети. TIN-модель была разработана в начале 70-х гг. как простой способ построения поверхностей на основе набора неравномерно расположен­ных точек. В 70-е гг. было создано несколько вариантов данной систе­мы, коммерческие системы на базе TIN стали появляться в 80-х гг. как пакеты программ для построения горизонталей.

Модель TIN используется для цифрового моделирования рельефа. При этом узлам и ребрам треугольной сети соотносятся исходные и про­изводные атрибуты цифровой модели.

Полигоны Тиссена (или диаграммы Вороного) представляют собой геометрические конструкции, образуемые относительно множества то­чек таким образом, что границы полигонов являются отрезками перпен­дикуляров, восстанавливаемых к линиям, соединяющим две ближайшие точки. Полигоны Тиссена позволяют проводить анализ на соседство близость и достижимость.

Нерегулярная выборка лучше, чем регулярная, отражает харак­тер реальной поверхности и это является достоинством полигожн Тиссена.

При построении TIN-модели дискретно расположенные точки со единяются линиями, образующими треугольники. В пределах каждогс треугольника поверхность обычно представляется плоскостью. Посколь ку поверхность каждого треугольника задается высотами трех его вер шин, применение треугольников обеспечивает каждому участку мозаичной поверхности точное прилегание к смежным участкам. Это обес печивает непрерывность поверхности при нерегулярном расположении точек.

Данная модель позволяет использовать в качестве элементов мозаи ки более сложные многоугольники, но их всегда можно разбить на тре угольники.

В векторных ГИС модель TIN можно рассматривать как полигоны с атрибутами угла наклона, экспозиции и площади, с тремя вершинами, имеющими атрибуты высоты, и с тремя сторонами, характеризующи­мися углом наклона и направлением.

Для выбора точек модели используют три основных алгоритма: ал­горитм Фоулера и Литла, алгоритм ключевых точек, эвристическое уда­ление точек.

С аналитической точки зрения основу таких вложенных, или иерар­хических, мозаик составляют (рекурсивно) раскладываемые модели. Рекурсивная декомпозиция треугольников приводит к образованию тре­угольных квадродеревьев, причем декомпозиция шестиугольников не­возможна. Единицы с более высоким уровнем разрешающей способно­сти можно объединять, формируя шестиугольники, что приводит к об­разованию семиразрядного дерева. Схема адресации для вложенных шестиугольных мозаик была разработана Л. Гибсоном и Д. Лукасом. Они назвали ее генерализованной сбалансированной троичной мозаикой.

Квадратомическое дерево - одна из наиболее широко известных структур данных, использующихся применительно к площадям, линиям и точкам.

Бесструктурные гиперграфовые и решетчатые модели. Они обра­батывают координатные данные в виде простых строк координат без ка­кой-либо структуры. В случае обработки площадей общие границы всегда вводятся в ЭВМ дважды. Пример практического применения этих моде­лей - хранимые в памяти ЭВМ полные полигоны и векторные цепные коды.

Гиперграфовые модели основаны на теории множеств и гипергра­фов и используют шесть абстрактных типов данных: класс, атрибут клас­са, связь класса, объект, атрибут объекта, связь объекта.

Класс соответствует границе гиперграфа, причем объекты являются узлами этого графа. Каждый класс содержит объекты с атрибутами объек­та и различаемый узел, содержащий атрибут класса. Используя подклас­сы, вводят иерархию классов и объектов.

Связи классов и связи объектов устанавливают соотношения между теми классами, которые не связаны иерархически. Связи классов пред­ставляют потенциальные соотношения между классами, а связи объек­тов - действительные соотношения между объектами. Для образования мультисвязи можно объединить несколько связей объектов. Несколько классов объектов образуют гиперклассы, которые связаны гиперсвязями.

Гиперграфовые модели применимы как к координатным, так и к ат­рибутивным данным. Как правило, они отличаются высокой степенью сложности.

Решетчатые модели базируются на математической теории реше­ток, оперирующей с частично упорядоченными наборами данных. Они полезны в тех случаях, когда отсутствует четкая иерархия объектов.

Элементы алгебраической теории автоматных моделей синтеза ти­повых конструктивных моделей упрощают процесс получения сложных графических изображений. Однако такой подход, находящий широкое применение в САПР, пока не используется в технологиях ГИС.