Вторая половина XX столетия, как этап развития, характеризуется появлением в разных странах информационного общества, в котором информационные продукты и услуги и сфера их производства и применения становятся одним из основных экономических ресурсов и фактором, меняющим формы экономической деятельности, виды организаций и социальные взаимоотношения [1, 3, 7, 17, 42, 64, 69, 97].
Самыми преуспевающими в деловом мире являются фирмы и корпорации, использующие современные информационные технологии для удовлетворения потребностей конечного потребителя в знаниях, информационных продуктах и услугах.
Огромные объемы современной информации в сочетании с требованием быстро собрать информацию, качественно обработать ее, проанализировать и на основе этого принять решение неизбежно приводят к необходимости использования баз данных.
Можно выделить две качественные группы технологий, которые человек использует в своей деятельности: технологии приспособления к окружающей среде, технологии преобразования среды в соответствии со своими потребностями. Оба типа вышеназванных технологий в настоящее время в большой степени реализуются с использованием методов геоинформатики.
Геоданные все чаще рассматриваются в качестве национального информационного ресурса многоцелевого использования, а геоинформационные технологии обеспечивают их пространственную унификацию, комплексное и сопряженное использование, современные ГИС признаны одним из универсальных интегрированных информационно-технологических средств, способствующих эффективному решению территориальных проблем управления и планирования [96, 99, 102].
Современное общество характеризуется широким внедрением методов информатизации во все сферы деятельности [47, 64, 97]. С одной стороны это привело к информационных технологий и систем в разные сферы деятельности, такие как транспорт [43−46, 91, 101], экономика [69, 87, 94, 97], науки о земле [47, 71, 99, 102] и т. д. С другой стороны современное развитие характеризуется существенным возрастанием информационных объемов, которые необходимо обрабатывать и хранить. Это неизбежно приводит к необходимости использования баз данных как неотъемлемой части исследований как ранее проводимых, так и новых.
Еще одной особенностью современного развития общества является интеграция [47, 48] и возникновение новых научных направлений на этой основе. Следствием интеграции является возникновение новых научных направлений, к числу которых относится и геоинформатика.
Геоинформатика (нем. Geoinformatik англ.: Spatial Informatics, Geolnformatics) имеет три аспекта развития и интерпретации.
1. Научное направление, основанное на интеграции математики, информатики и наук о Земле, изучающее пространственно временные явления (структуру, связи, элементы, динамику) на Земле и применимое для аналогичных исследований других объектов космического происхождения.
2. Прикладное направление, связанное с разработкой технологий и систем для изучения и управления процессами и явлениями окружающего мира.
3. Производство (в первую очередь картографическое) информационных продуктов специального и коммерческого назначения, используемых в картографическом производстве и в других сферах как инструмент анализа и поддержки принятия решений. Центральным элементом геоинформатики является исследование и использование пространственных отношений. Согласно международному стандарту ISO OSI/TC 211: Geographic Information/ Geomatics, International Draft Standart [100] геоинформатика направлена на развитие и приложение методов и концепций информатики для исследования пространственных объектов и явлений. Связующим элементом в геоинформатике являются пространственные отношения [99].
Геоинформатика ближе к информатике, чем, например, к географии. Подобно биоинформатике, информатике окружающей среды, экономической информатике [94] геоинформатика оперирует с современными концепциями информатики и переносит их в прикладные области.
Геоинформатика основывается на знаниях и функциях геоинформации, с ее представлением в форме геоданных и последующими разнообразными приложениями [26, 27, 51]. При этом полученные знания используются и реализуются в геоинформационных технологиях и геоинформационных системах. Существенное развитие и взаимный перенос знаний геоинформатики инициируется не только за счет методов информатики, но и за счет научных дисциплин таких как геодезия, фотограмметрия, картография, география.
Среди множества объектов, которые изучает геоинформатика особое место занимают объекты большой протяженности (ОБП).
Объекты большой протяженности — это объекты линейные размеры которых таковы, что при их исследовании и проектировании необходим учет кривизны земной поверхности. Кроме того, картографическое представление ОБП, лежащих более чем в одной координатной зоне, характеризуется большими искажениями.
К таким объектам относятся транспортные сети, нефтеи газопроводы, реперные сети, линии электропередач, телекоммуникационные сети, зоны распространения выбросов от многих крупных промышленных предприятий (до 2.5 тыс. км) и многие другие.
Это определяет актуальность исследования таких объектов и решения проблем, связанных с ними.
Одна из первых проблем связана с необходимостью эффективного проектирования ОБП, в частности в проектировании железных дорог.
Большой вклад в развитие вопросов принятия решений в проектировании железных дорог внесли: Г. Л. Аккерман, Е. П. Алексеев, В. А. Анисимов, Вл.А. Анисимов, В. В. Анисимов, Р. А. Аукуционек, В. А. Бучкин, Н. С. Бушуев, Ю. А. Быков, Б. Н. Веденисов, В. В. Виноградов, Б. А. Волков, А. В. Гавриленков, А.Е.
Гибшман, С. М. Гончарук, А. В. Горинов, Б. И. Гороховцев, В. П. Житкевич, Г. Г. Иванов, А. И. Иоаннисян, Э. П. Исаенко, В. В. Каменцев, И. И. Кантор, JI.B. Канторович, Б. С. Козин, В. Ю. Козлов, А. П. Кондратченко, Г. Г. Коншин, В. А. Копыленко, И. П. Корженевич, В. В. Космин, Н. Б. Курган, А. Д. Ларионов, В. Н. Лившиц, П. А. Луговой, С. Я. Луцкий, Е. А. Макушкина, Б. С. Малышев, B.C. Миронов, А. О. Нейман, В. И. Новакович, Г. С. Переселенков, И. Г. Переселенкова, В. А. Подвербный, Э. И. Позамантир, А. С. Понарин, И. В. Прокудин, А. Л. Ревзон, Е. С. Свинцов, Э. С. Спиридонов, В. И. Струченков, К. К. Таль, И. В. Турбин, А. А. Цернант, B.C. Шварцфельд, В. А. Шемонаев, Е. А. Шиварева, А. Д. Шишков, В. Я. Шульга, Т. Г. Яковлева и др.
В современных условиях решение многих задач требует сбора информации и построения информационных моделей об объекте исследования. Информационные модели ОБП не только имеют большой информационный объем, но характеризуются сложной совокупностью связей, а также имеют топологические характеристики, которые должны учитываться при их анализе. Это делает актуальным разработку технологий работы с такими моделями, снижающими нагрузку на пользователя.
Большие информационные объемы требуют организации эффективного хранения данных об ОБП. Это делает актуальным исследование баз данных, которые хранят такие объемы информации и специфические связи между информационными моделями пространственных объектов.
Важным является не только хранение информации об ОБП, но и эффективное ее использование для анализа и принятия решений.
Значительный вклад в изучение вопросов теории принятия решений, теории полезности и теории нечетких множеств внесли российские и зарубежные ученые: М. А. Айзерман, Р. Беллман, А. Н. Борисов, А. Вальд, Э. И. Вилкас, Л. А. Заде, Р. Л. Кини, А. Я. Кирута, А. Кофман, О. А. Крумберг, О. И. Ларичев, И. М. Макаров, Е. З. Майминас, Н. Н. Моисеев, Л. Мозес, О. Моргенштерн, Е. М. Мошкович, Дж. фон Нейман, С. А. Орлровский, В. В. Подиновский, В. А. Попов, Д. А. Поспелов, X. Райфа, Б. Руа, A.M. Рубинов, В.Б.
Соколов, В. Б. Тарасов, А. Н. Тихонов, П. К. Фишберн, Е. М. Фуремс, В. Я. Цветков, В. Н. Цыгичко, Г. Чернов, Д. И. Шапиро, К. Д. Эрроу, Р. Ягер, А. В. Язенин, и другие.
В современных условиях исследование ОБП наиболее эффективно возможно методами геоинформатики.
Большой в клад в развитие теории геоинформатики внесли ученые A.M. Берлянд, С. И. Матвеев, В. П. Савиных, В. Я Цветков, B.C. Тикунов, А. В. Мартыненко, Малинников В. А. Александров В.Н. и др.
Применительно к решению задач, связанных с развитием железнодорожного транспорта необходимо использовать методы геоинформатики транспорта. Существенный вклад в развитие геоинформатики на железнодорожном транспорте внесли Бородко А. В., А. Б. Левин, Г. С. Бронштейн, В. А. Коугия, С. И. Матвеев, У. Д. Ниязгулов, М. Н. Садакова, В. Я. Цветков, В. П. Кулагин, А. Д. Иванников, А. Н. Тихонов и др.
Во введении дается актуальность и краткие особенности исследования. В первой главе дается анализ особенностей объектов большой протяженности исследуется геоинформатика как метод изучения транспортных сетей, исследуется аспект влияния кривизны Земли на точность определения высот ОБП. На основе анализа ставятся основные проблемы и задачи исследований.
Во второй главе раскрываются особенности хранения данных с использованием ГИС в аспекте разработки распределенной базы данных, исследуется специфика геоданных. Исследуются особенности и методы применения информационных моделей, в том числе информационных моделей БД ГИС. исследуется специфика автоматизированной обработки информации в ГИС как человеко-машинной системе. Дается ретроспективный анализ принципов автоматизации, разработанных В. М. Глушковым, и соответствие этим принципам методам автоматизации проектирования с использованием ГИС.
В третьей главе дается классификационный анализ существующих номенклатур карт и цифровых моделей. Дается разработка классификации карт, применимая для основы классификации цифровых моделей.
В четвертой главе дается анализ объектов большой протяженности в аспекте их картографического отображения и проектирования с учетом искажений на границах зон. Дается подход сопоставления высокоточной крупномасштабной информации и мелкомасштабной обзорной. Дается подход использования теории графов для переноса топологических свойств на цифровые модели объектов проектирования.
В пятой главе дается технология работы геоинформационной распределенной базы данных. Исследуются условия, при которых она может быть распределенной и анализируются варианты технологий распределенной работы для различных случаев и применительно к решению проектных задач. В главе дается технологический подход переноса топологических свойств пространственных объектов в модели базы данных.
В заключении приводятся основные выводы работы.
Выводы. Использование теории графов позволяет упростить описание сложной сети ОБП, сводя все ее элементы к 5 типовым.
5.4.2. Анализа топологии транспортных объектов с использованием теории графов.
Графовая форма представления моделей — форма, которая дает представление модели или ее характеристик в виде одного или совокупности взаимосвязанных графов. Пример графа — схема метрополитена: множество станций (вершины графа) и соединяющих их линий (ребра графа). Необходимость использования теории графов в геоинформатике обусловлена требованием введения топологических свойств в координатные данные ГИС и возможностями анализа и решения задач, которые дает теория графов.
Дуга (Arc) а — фундаментальное понятие теории графовопределяется как упорядоченная пара вершин, графически изображается отрезком или непрерывной линией стрелкой, направленной, например, от вершины начала дуги к вершине — концу дуги. Дуга может начинаться и кончатся в одной вершине. Такая дуга (ребро) называется петлей (рис. 5.2.а).
Дуга есть элемент ориентированного графа и обозначается стрелкой, а ребро элемент неориентированного графа и обозначается криволинейным или прямолинейным отрезком без стрелки.
Вершина (Vertex) v — фундаментальное понятие теории графов, экземпляр одного из двух типов элементов графа, соответствующий объекту некоторой фиксированной природыабстрактная структура, образуемая совокупностью однородных (чаще всего) объектов-вершин вместе с их связями, порождает топологическую структуру, именуемую графом. Другие названия вершины — узел, точка.
А). Петля.
Б). Граф неориентированный Ь.
В) Граф ориентированный (сеть).
Рис. 5.2 Виды графов.
Последовательность ребер в графе, соединяющая две его вершины называется маршрутом. Длина маршрута равна количеству ребер в порядке их прохождения. Г. называется связанным, если любая пара его вершин соединена маршрутом. Замкнутый маршрут называют контуром или циклом.
Граф с конечным числом вершин называется конечным. Сетью называется конечный граф (рис. 5.2. в), в котором одна вершина не имеет входных дуг (начальная вершинаа) и одна вершина не имеет исходящих дуг (конечная вершина — Ь).
Начальная вершина (Start vertex) обозначает вход графа. На рис 5.2. в она обозначена а. Все остальные вершины являются входными вершинами фрагмента (Entry vertex of a fragment). Входная вершина фрагмента та, для которой существует путь из начальной вершины графа.
Количественная характеристика графовой модели называется весом вершины графа.
Вес вершины (Weight of a vertex) — число, приписанное вершинедействия, производимые над ними, зависят от конкретной интерпретации.
Выходная вершина подграфа (Output vertex of subgraph) — вершина подграфа, через которую проходит любой путь из вершин подграфа в произвольную вершину графа, не принадлежащую подграфу. Каждая вершина имеет свою метку.
Метка (Label) — число, символ, слово в некотором алфавите, вектор и т. п., приписанные вершине (или ребру/дуге) графа и играющие идентифицирующую роль.
Если граф описывает некую классификацию, то метка является классификационным идентификатором вершины. Разметка или приписывание меток в этом случае является идентификацией объектов по признакам классификации.
Совокупность меток образует уникальный идентификатор объекта классификации. Это одна функция меток. Друга не менее важная состоит в том, что именно для иерархической системы классификации метки показывают связь данного объекта классификации с другими и его место в системе классификации. Для этого надо используют понятие маршрута. Mapuipym (Sequence) — чередующаяся последовательность вершин v и ребер (дуг) е графа G такая, что е* = (v'i-i, vi), 1.
Маршрут конечен, если число входящих в него ребер конечно, и бесконечен в противном случае..
Важным для сетевых систем является характеристика Гамильтонов путь (Hamiltonian path) — замкнутый путь, обходящий все вершины графа только один раз. Если каждой дуге присвоено число, называемое сложностью прохода, то нахождение гамильтонова пути связано с нахождением минимальной сложности прохода. Эта же задача известна под названием «задачи о коммивояжере», если граф представляет собой связанную сеть..
Транспортная сеть (Transportation network) — линейный объект геоинформационной системы. В теории графов транспортная сеть представляет собой сетевую модель (граф), в которой обязательно выполняются два условия: определены две вершины — вход и выход сетидля каждой дуги задана характеристика называемая пропусканной способностью.
Анализ транспортной сети представляет собой одну из основных задач в топологии..
5.4.3 Решение задачи минимизации стоимости перевозок методом кратчайшего пути в графе.
Перевозка осуществляется в транспортной сети. В теории графов транспортная сеть представляет собой сетевую модель (граф), в которой обязательно выполняются два условия: определены две вершины — вход и выход сетидля каждой дуги задана характеристика называемая пропусканной способностью..
Анализ транспортной сети представляет собой одну из основных задач в логистике, а именно доставка груза из входа сети в точку выхода при условии минимизации заданного критерия. Как правило этот критерий определяется минимизацией затрат, но в отдельных случаях (доставка грузов в условиях чрезвычайных ситуаций) критерием может быть минимальное время доставки..
Один из методы решения таких оптимизационных задач основан на теореме о максимальном потоке и минимальном разрезе, утверждающей, что максимальный поток, который можно пропустить через сеть из вершины U в вершину V, равен минимальной пропускной способности разрезов, разделяющих вершины U и V. На этой основе строят различные алгоритмы нахождения максимального потока..
Для конечных графов, т. е. для графов с конечным множеством вершин и ребер, как правило, проблема существования алгоритма решения задач, в том числе оптимизационных, решается положительно. Решение многих задач, связанных с конечными графами, может быть выполнено с помощью полного перебора всех допустимых вариантов. Однако таким способом удается решить задачу только для графов с небольшим числом вершин и ребер. Поэтому существенное значение для теории графов имеет построение эффективных алгоритмов, находящих точное или приближенное решение..
Постановка задачи.
Дан неориентированный граф G =.
Вершина (Vertex) v — фундаментальное понятие теории графов, экземпляр одного из двух типов элементов графа, соответствующий объекту некоторой фиксированной природыабстрактная структура, образуемая совокупностью однородных (чаще всего) объектов-вершин вместе с их связями, порождает топологическую структуру, именуемую графом.
В нашем случае пара (V, E), где V (Vertex) — непустое множество объектов, называемых вершинами графа, а Е {Edge) — подмножество двухэлементных подмножеств множества V, называемых ребрами графа..
Вес дуги (Weight of an arc) — число, приписанное дуге и играющее, например, роль физической длины дуги. В общем случае смысл веса должен оговариваться особо.
Назначение веса означает, что каждой ребру <м, v> еЕ поставлено в соответствие некоторое вещественное число, а (и, v), называемое весом (Weight of an arc) данной дуги..
Если последовательность вершин vo, V|,., vp определяет путь в G, то его длина определяется как сумма весов ребер. В этом случае используют термин вес пути. Вес пути (Weight of a path) — функция, определенная на множестве дуг путичаще всего это — сумма весов дуг пути.
Вес может иметь разное значение. Он может отражать как фактор расстояния, так и фактор затрат при перевозке груза на расстояние определяемой точками входа и выхода транспортной сети. Таким образом вершинам соответствуют реальные пункты отправки, назначения и промежуточные (станции, железнодорожные узлы)..
Вес дуги также может соответствовать времени перемещения грузов между вершинами. Необходимо найти кратчайший путь между фиксированными вершинами s, teV. которые соответствуют началу и кончу маршрута..
Длину такого кратчайшего пути мы будем обозначать d (s, t) и называть расстоянием от s до t (расстояние, определенное таким образом, может быть отрицательным)..
Если каждый контур графа имеет положительную длину, то кратчайший путь будет всегда элементарным путем, т. е. в последовательности v (,., vp не будет повторов..
На практике железнодорожных и автоперевозок, как правило, путь существует и надо выбрать из множества существующих путей кратчайший..
В этом случае для произвольных s, t е V (s, t) существует вершина v, такая что d (5, t) = d (5, v) + a (v, t)..
Действительно, таким свойством обладает предпоследняя вершина v произвольного кратчайшего пути из s в t. Используя этот рекурсивный подход, мы можем найти вершину и, для которой d (s, v) = d (s, w) + a (w, v), и т. д..
Из положительности длины всех контуров следует, что создаваемая таким образом последовательность t, v, и,. не содержит повторений и оканчивается вершиной s..
Алгоритм решения на языке Паскаль..
Данные: 1. Расстояния (веса) ?>[v] от фиксированной вершины s до всех остальных вершин v е V, 2. Фиксированная вершина t, 3. Матрица весов ребер, А[и, v], и, v е V..
Результаты: переменная Way, которая содержит последовательность вершин, определяющую кратчайший путь из s в t. begin.
WAY=0- WAY<=t v:= twhile vy s do begin и := вершина, для которой D[v] = D[u] + A[u, v]-.
WAY uv:= и end end..
Для эффективности решения необходимо оценить временную сложность или вычислительную сложность алгоритма. Временная сложность (Time complexity) определяется как число шагов, выполняемых алгоритмом в худшем случае, обычно рассматривается как функция размерности задачи, представленной входными данными. Обычно под размерностью теоретико-графовой задачи понимается число вершин графа п, число дуг т или пара (п, т). Под шагом алгоритма понимается выполнение одной из команд некоторой гипотетической машины. Поскольку при таком определении шага сложность алгоритма зависит от конкретного вида машинных команд, во внимание принимается асимптотическая сложность, т. е. асимптотическая скорость увеличения числа шагов алгоритма, когда размерность задачи неограниченно растет. Ясно, что при двух произвольных «разумных» способах перевода алгоритма в последовательность машинных команд соответствующие сложности различаются не более чем на мультипликативную константу, а их скорость роста одинакова. В нашем случае шаг алгоритма соответствует выбору вершины. Если выбор вершины и происходит в результате просмотра всех вершин, то сложность алгоритма -0(п2)..
При 100 вершинах данная задача вполне решается на современных персональных компьютерах типа Пентиум. На практике число промежуточных пунктов плюс пункт отправки и назначения не превышают 20−30. Однако в реальной ситуации на промежуточных станциях возможны затраты в виде простое или перегрузки или сортировки вагонов. В результирующем графе эти ситуации отразятся дополнительными дугами, между вершинами означающими прибытие груза в промежуточный пункт, отправка груза из промежуточного пункта..
Таким образом, в транспортном графе возникает два типа ребер. Первые связаны с транспортировкой и соответствуют реальному перемещению груза в пространстве. Вторые не соответствуют перемещению, а описывают затраты связанные с задержкой на промежуточной станции. Это приводит к тому. Что реальный транспортный граф будет иметь вдвое больше ребер и вершин, соответствующих пунктам остановки..
В данной постановке задачи такая особенность не влияет на результат решения. Однако за счет этого условия число вершин в графе при реальных 20−30 станциях возрастет до 40 — 60. Но и в этом случае их число будет меньше 100, что позволяет решать задачу алгоритмически. Это является достоинством решения и дает основание рекомендовать методы теории графов для анализа транспортных сетей..
5.4.4 Идентификация объектов ГР БД с применение теории графов.
Как уже отмечалось использование теории графов с одной стороны позволяет упрощать сложные сети, сводя большую совокупность элементов к 5−10 типовым качественным элементам, с соответствующими числовыми характеристиками..
С другой стороны теория графов позволяет вводить топологические свойства в цифровые модели объектов, весьма важные при пространственном анализе и при анализе проектных решений. Поэтому важным этапом технологии является введение свойств графов в объекты базы данных..
Одним из ключевых понятий баз данных и всех информационных систем хранения данных является идентификация и идентификатор. Поскольку это понятие используется в различных направлениях необходимо остановится на нем..
Идентификатор (identifier) вообще многоаспектное понятие используемое в теории баз данных, в программировании, в ГИС, в системах информационной безопасности. Отсюда различные его интерпретации:.
1. Лексическая единица, используемая в качестве имени для элементов языка-.
2. Уникальное имя, присваиваемое записи базы данных и представляющее собой последовательность латинских букв и цифр, начинающуюся с буквы. В некоторых языках используются и другие знаки, например, #, &, -,, а также русские буквы..
3. Уникальное имя в языках программирования, системах классификации, кодирования и информационных массивах..
4. Уникальное имя (номер), приписываемый пространственному объектукоторый служит для связи табличных и графических данных ГИС..
5. Уникальное имя объекта или субъекта в системе информационной безопасности..
Идентификатор объекта (entity identifier) более узкое понятие и определяется как элемент данных, однозначно определяющий объект внутри системы Объектом может быть объект базы данных или объект ГИС..
Процедура идентификации (identification) заключается присвоения объектам или субъектам идентификатора. В базах данных идентификация является обязательной..
Поэтому возникает проблема разработки методики или процедуры идентификации при создании любой базы данных, включая БД ГИС..
В нашем случае, сохраняя последовательность исследований. В качестве основы идентификации используем рассмотренную выше классификацию..
На рис. 5.3 приведена классификационная модель в виде ориентированного графа, которая построена на основе анализа номенклатуры топографических карт [87]. Она включает два типа элементов дуги и вершины..
Дуга изображается отрезком непрерывной линией стрелкой, направленной, например, от вершины ПЗ — начала дуги к вершине Ml ОООконцу дуги. На рисунке 5.3 дуги обозначены стрелками..
Начальная вершина (Start vertex), которая обозначает вход классификационного графа, на рис 5.3. обозначена ПЗ и соответствует поверхности Земли. Эта вершина определяет нулевой уровень иерархической классификации..
Все остальные вершины являются входными вершинами фрагмента (Entry vertex of a fragment). Входная вершина фрагмента та, для которой существует путь из начальной вершины графа..
Эти вершины графа классификации имеют обозначения, включающие прописную букву «М» и цифру, обозначающую число тысяч в масштабе соответствующей карты. Например, топографическая карта масштаба 1: 300 ООО обозначается МЗОО, а карта масштаба 1: 50 ООО обозначается М50..
М100.
М50.
М25 • вес1/9.
М500 вес¼ вес 1/256.
М2 • вес1/9.
М10 вес¼.
М1 вес¼.
Рис. 5.3 Граф классификации топографических карт по признаку номенклатуры..
Около каждой вершины в скобках показана валентность вершины или степень деления по качественным признакам, если она отлична от степени деления (1:1) «один к одному». Еще раз подчеркивается, что степень деления определяется по качественным признакам..
Количественная характеристика деления включена в характеристику f* графовой модели, которая называется весом вершины графа. # Вес вершины (Weight of a vertex) — число, приписанное вершинедействия, производимые над ними, зависят от конкретной интерпретации (например, решетку или полурешетку)..
Вес вершины графа показывает в знаменателе количество элементов входной вершины, которые включает в себя выходная вершина. На рис. 5.3 входящими вершинами являются те, в которые входят стрелки..
Все вершины, начиная с первого уровня классификации до предпоследнего, являются не только входными, но и выходными вершинами подграфа..
Выходная вершина подграфа (Output vertex of subgraph) — вершина подграфа, через которую проходит любой путь из вершин подграфа в произвольную вершину графа, не принадлежащую подграфу..
Каждая вершина имеет свою метку, которые из-за плотности изображения на рис. 5.3 не показаны..
Метка (Label) — число, символ, слово в некотором алфавите, вектор и т. п., приписанные вершине (или ребру/дуге) графа и играющие идентифицирующую роль. Разметка или приписывание меток есть отображение вида <Р: V (G) -+L, где L — множество меток. В отличие от нумерации здесь не требуется взаимной однозначности..
Если граф описывает некую классификацию, то метка является классификационным идентификатором вершины. В нашем случае запись N-37−144-(256-а) включает несколько меток..
Разметка или приписывание меток в этом случае является идентификацией объектов по признакам классификации..
Отображение вида.
Р: V (G) -+L, является правилом присвоения классификационных идентификаторов (обозначений) объектам классификации в единой системе классификации..
Здесь V (G) множество дуг V (классификационного) графа G. ср: функция отображения или правило присвоения классификационного идентификатора, в соответствии с признаком классификации..
Для нашего случая метки первого уровня отличаются от всех остальных записью через дефис. Таким образом, метки первого уровня имеют идентификатор включающий: символ, дефис и букву латинского алфавита. Это обусловлено естественной классификацией, т. е. соответствием построения графа классификации реальным признакам (номенклатура) объекта классификации (топографическая карта). Что и находит отражение в обозначении меток..
Метки всех остальных уровней разделены в записях дефисом. Дефис как элемент метки входит только в метки первого уровня классификации. Механизм создания меток приведен в таблице 5.2. В ней вводится понятие «своего» признака. «Свой» признак это признак определяющий классифицируемый объект на данном уровне классификации. Поскольку по существу формирование метки выполняется по рекурсивному правилу, то «свой» признак играет роль дополнения метки вышестоящего уровня информацией относящейся во первых к данному уровню и во вторых к самому объекту классификации..
ЗАКЛЮЧЕНИЕ.
В ходе проведенных диссертационных исследований автором получены следующие результаты. Выявлена специфика геоданных, которая состоит в необходимости выделения трех факторов: временного, пространственного и тематического и организации их информационных моделей в виде связанных совокупностей графической и табличной информации. Причем эти информационные модели являются динамическими, т. е. изменение графической части информационной модели влечет изменение табличной и наоборот изменение табличной влечет изменение графической. Эта специфика является определяющей и условием организации геоинформационной распределенной базы данных..
Анализ технологических процессов выявил, что автоматизация с использованием ГИС проходит согласно принципам автоматизации, определенным В. М. Глушковым, что соответствует стратегическим целям развития автоматизации в стране..
В ходе исследовании картографической информации, в частности, картографических проекций, выявлены проблема совместимости картографического изображения объектов большой протяженности на границах зон, где искажения картографических проекций особенно велики. Для совместимости предложено использовать цифровые модели в специально разработанной фасетной системе классификации, сопоставимой с системой классификации топографических карт..
В свою очередь разработана система иерархической классификации основанием деления для которой являются карты масштаба 1:1 000 000, никогда не используемые в проектных задачах из-за низкой точности координат на местности..
Разработан алгоритм автоматической классификации цифровых моделей основанный на выявлении и параметризации их пространства признаков..
Разработана система классификации цифровых моделей на базе естественной классификации топографических карт и расширения этой классификации дополнительными параметрами цифровых карт и цифровых моделей..
Разработаны механизмы идентификации и маршрутизации в РГ БД. основанные на методологи и теории графов..
Выявлено, что для эффективного использования БД объектов большой протяженности необходимо обеспечить к ним доступ для всех возможных пользователей данной информации. Это возможно путем создания распределенной БД. В работе проанализированы и сформулированы требования к организации распределенной БД. Определены три технологии работы с распределенной БД и их применимость к разным случаем решения проектных задач..
Выявлено, что цифровые модели не являются носителями топологической информации, которая очень важна при пространственном анализе. Поэтому для введения такой информации в ЦМ на основе теории графов разработан механизм переноса топологических свойств объектов в базу данных цифровых моделей объектов..
Разработан алгоритм решения задач при управлении транспортными потоками, основанный на теории графов..
Методические положения, выводы и рекомендации, содержащиеся в диссертации, являются результатом самостоятельного исследования автора. Конкретный вклад автора в полученные научные результаты заключается в следующем:.
Разработана система классификация карт разных масштабов. На ее основе разработана фасетная классификация цифровых моделей по аспекту их соотносимости к картам разных масштабов..
Выявлено, что для эффективного использования БД объектов большой протяженности необходимо обеспечить к ним доступ для всех возможных пользователей данной информации. Это возможно путем создания распределенной БД. В работе проанализированы и сформулированы требования к организации распределенной БД. Определены три технологии работы с распределенной БД и их применимость к разным случаем решения проектных задач..
Выявлено, что цифровые модели не являются носителями топологической информации, которая очень важна при пространственном анализе. Поэтому для введения такой информации в ЦМ на основе теории графов разработан механизм переноса топологических свойств объектов в базу данных цифровых моделей объектов..
Разработан механизм применения теории графов для решения задач при управлении транспортными потоками..
Наиболее существенным в данной работе следует считать разработку технологий геоинформационной распределенной базы данных объектов большой протяженности. Эта технология позволяет:.
1. Использовать высокую точность геодезических и спутниковых измерений с наглядностью картографической информации при проведении предпроектных исследований, при создании вариантов проектных решений..
2. Проводить обобщенный и детальный анализ картографической информации в разных масштабах за счет динамической генерализации и детализации электронных карт в ГИС. При этом не снижается точность измерений и расчетов при переходе к более мелким масштабам, что характерно при использовании обычных карт..
3. Устранять недостатки, связанные с проектированием объектов большой протяженности, размеры которых превосходят координатную зону. Это достигается за счет разработанной автором системы классификации. В этом случае появляется возможность стыковки крупномасштабной информации на уровне цифровых моделей, исключая искажения на границах зон, связанные с картографическим проектированием..
4. Решить проблему совмещения точности геодезических работ с обзорностью картографической информации..
5. Создать возможность уменьшения коэффициента развития трассы на основе выбора в качестве информационной интегрирующей основы более точных трехмерных цифровых моделей вместо двухмерных менее точных картографических моделей..
6. Свести в единую технологическую цепочку предпроектные исследования, проектирование, мониторинг созданного объекта и перепроектирование..
7. Создает эффект эмерджентности, который состоит в том, что ГР БД становится средством не только связи и обмена информацией между разными информационными системами, но дополняя информацию и методы обработки одной системы, информацией и методами обработки другой системы создает новую информационную макросистему с качественно новыми возможностями в сравнении с информационными системами, входящими в ее состав..
Материалы исследований могут быть рекомендованы для внедрения в проектных и производственных организациях связанных с транспортировкой и передачей грузопотоков на большие расстояния. Это нефтегазодобывающие, предприятия, электроэнергетические, транспортные системы и отрасли и т. д..