Содержание к диссертации
Введение
Глава 1 -Текущее состояние вопроса 13
1.1 Лесные пожары в Российской Федерации 13
1.2 Математическое моделирование процессов распространения лесных пожаров 17
1.3 Системы управления борьбой с лесными пожарами 21
Выводы 31
Глава 2 Специальное математическое обеспечение задач локализационного управления лесных пожаров 32
2.1 Математическая постановка задачи оптимальной локализации лесного пожара 33
2.2 Примеры решения задач локализационного управления по критерию минимизации обобщенных затрат на управление 35
Выводы 67
Глава 3 - Решения поставленных задач управления методами теории графов.... 68
3.1 Построение оптимального маршрута 68
3.1.1 Метод нахождения кратчайшего пути по алгоритму
Форда-Белмана 68
3.1.2 Алгоритм Ли (волновой алгоритм) 72
3.1.3 Модифицированный алгоритм фронта волны (МАФВ) 74
3.1.4 Двухволновая модификация волнового алгоритма (ДМВА) 75
3.2 Построения областей достижимости 80
3.3 Построения траекторий локализации процесса распространения 80
3.4 Визуализация данных 84
3.4.1 Локальная модель освещения 84
3.4.2 Модели затенения 88
3.4.3 Алгоритм обратной трассировки лучей 92
3.4.2 Алгоритм создания трехмерной сцены 105
3.5 Методологии разработки и проектирования 109
3.5.1 Методология IDEF0 109
3.5.2 Объектно-ориентированная методология 114
3.5.3 Методология RAD 119
Выводы 122
Глава 4 - Описания структуры и функций информационной системы поддержки принятия решений для задач управления борьбой с лесными пожарами 123
4.1 Общие технические характеристики 123
4.2 Функциональная модель системы 123
4.3 Модуль расчета оптимального маршрута 129
4.3.1 Общее описание 129
4.3.2 Обзор возможных ситуаций при построении маршрута 132
4.4 Модуль расчета областей достижимости 137
4.5 Модуль расчета оптимальной траектории локализации 141
4.6 Модуль трехмерной визуализации 141
Выводы 145
Заключение 146
Список литературы 147
Приложение 1 - Акты внедрения и использования 164
Приложение 2 - Свидетельства авторского права 167
- Лесные пожары в Российской Федерации
- Математическая постановка задачи оптимальной локализации лесного пожара
- Построение оптимального маршрута
- Модуль расчета оптимального маршрута
Введение к работе
Актуальность исследования. Работа посвящена разработке специального и программного обеспечения систем управления противопожарными силами и средствами при борьбе с лесными пожарами - стихийными бедствиями, периодически возникающими в различных регионах планеты. Борьба с лесными пожарами является важной государственной задачей во всех странах, где лесные ресурсы занимают одно из главных мест [143]. Ежегодно только в России регистрируется более 10000 очагов лесных пожаров. Площадь территории, подверженной пожарам, составляет около 300 млн. га. Особенно актуальна задача борьбы с лесными пожарами для районов Сибири и Дальнего Востока [104], на территории которых ежегодно возникают тысячи очагов возгорания, а ежегодный ущерб исчисляется десятками миллионов рублей.
Анализ действий по тушению крупных лесных пожаров показал, что успех борьбы с ними зависит не только от количества технических средств и людских ресурсов, но в определяющей степени - от рациональной их организации и правильной тактики тушения. Тактика тушения крупного лесного пожара определяется характером лесорастительных условий, топографией местности, особенностями распространения и развития. Недостаток сил и средств для ликвидации очагов возгорания компенсируется их маневрированием.
Лесные пожары не только наносят значительный экологический и материальный ущерб народному хозяйству и природной среде, но и представляют угрозу для жизни людей, оказавшихся в зоне их действия. Основной причиной гибели людей является неверный прогноз развития пожара, недооценка действия сопутствующих факторов (например, задымленности территории), ошибки в тактике борьбы с огнем и выборе маршрутов выхода из зоны действия пожара. Это ведет к слишком позднему осознанию опасности и как следствие, недостатку времени для спасения.
Внедрение в практику борьбы с лесными пожарами современных средств обнаружения, методов прогнозирования их распространения и развития, современных методов математического моделирования и теории управления дает возможность планирования и применения новых тактических приемов борьбы с лесными пожарами, более обоснованного подхода к применению управленческих решений с учетом различных возможных ситуаций развития лесного пожара.
Разработка математических моделей вывода сил и средств из зоны действия лесного пожара позволит создать компьютерные учебные и исследовательские тренажеры для отработки на них действий персонала при различных сценариях развития лесного пожара.
Цель и задачи исследования. Целью данной работы является разработка специального математического и программного обеспечения информационной системы поддержки принятия решений, в контексте задач управления борьбой с лесными пожарами.
Для достижения поставленной цели необходимо решить следующие задачи:
Задача оптимизации маршрутов доставки сил и средств к очагам лесного пожара.
Задача расчета областей достижимости.
Задача построения траекторий оптимальной локализации процессов распространения.
Задача расчета оптимальных маршрутов доставки сил и средств с учетом рельефа местности и визуализация результатов на трехмерной сцене.
Методы исследования. Результаты исследований, выполненных в работе, базируются на методах прикладного системного анализа, теории оптимального локализационного управления процессов распространения. При разработке алгоритмов и программного обеспечения использовались принципы модульного структурного программирования.
Научная новизна. Разработана методика, алгоритмы и программное обеспечение для нахождения оптимальных решений по управлению силами и средствами борьбы с лесными пожарами, учитывающую наличие и характеристики первоначального размещения противопожарных сил и средств, интенсивность и динамику лесного пожара, а также топографические условия местности. Научная новизна работы защищена тремя свидетельствами авторского права на интеллектуальную собственность.
Практическая значимость работы. Разработано специальное математическое и программное обеспечение информационной системы поддержки принятия решений для решения задач оптимального управления силами и средствами противопожарной лесоохраны.
Реализация результатов работы. Разработанное математическое и программное обеспечение приняты Всероссийским научно-исследовательским институтом противопожарной охраны лесов и механизации лесного хозяйства (ФГУ "ВНИИПОМлесхоз") к использованию для выполнения расчетов при разработке нормативно-технической документации по оперативной доставке сил и средств тушения на пожар; созданию и размещению объектов противопожарного устройства на территории лесного фонда.
Результаты, полученные лично автором. Разработаны модифицированные алгоритмы и программное обеспечение для решения задач: определение оптимального маршрута движение по пересеченной местности, определение областей достижимости процесса распространения и процесса управления, определение траектории оптимальной локализации процесса распространения, определение и визуализация траектории оптимального маршрута с учетом трехмерности реального пространства, а также информационная система поддержки принятия решений по планированию размещения и оптимальному управлению противопожарных сил и средств.
Апробация работы. Основной материал диссертации отражался в научных докладах, которые обсуждались на: XLTI Международная научная студенческая конференция «Студент и научно-технический прогресс»: Информационные технологии (Новосибирск, 2004);
Лесной и химический комплексы - проблемы и решения (экологические аспекты) (Красноярск, 2003-2006);
Лесные и степные пожары: возникновение, распространение, тушение и экологические последствия: 6-я Международная конференция. -Томский университет. (Томск, 2005);
Всероссийская научно-практическая конференция. (Красноярск, 2004);
Экология южной Сибири и сопредельных территорий. Материалы международной научной школы. (Абакан, 2004);
Публикации по теме диссертации. Результаты диссертационной работы отражены в 9 научных публикациях, в том числе в 1 статье в издании по списку ВАК и 3-х свидетельствах государственной регистрации программ для ЭВМ.
Структура и объем диссертационной работы. Диссертация изложена на 166 страницах и состоит из введения, 4 глав, заключения.
Библиографический список включает 146 наименований литературы.
В первой главе описывается текущее состояние вопроса. Она включает 3 раздела и выводы. В разделе 1.1 анализируется экологический и экономический ущерб от лесных пожаров на территории Российской
Федерации. В разделе 1.2 рассматриваются подходы к моделированию процессов распространения лесных пожаров. В разделе 1.3 рассматриваются системы управления борьбой с лесными пожарами, анализируются работы по моделированию процессов локализации лесных пожаров. Обосновывается выбор задач и целей исследования.
Во второй главе рассмотрена разработка специального математического обеспечение задач локализационного управления. Рассматривается математическая модель системы управления, объектом которой является процесс распространения, а субъектом - силы и средства борьбы с ним. Разработан алгоритм решения задачи оптимального локализационного управления, реализованный в среде MathCad 13. Приведены примеры вычисления траекторий оптимальной локализации при минимизации площади, минимизации времени (наибольшего быстродействия) и промежуточных вариантов. Проведен анализ полученных решений. Результаты исследований по главе 2 опубликованы в [90,95].
В третьей главе рассмотрены решения поставленных задач управления. Для нахождения кратчайшего пути рассматриваются алгоритмы: последовательной релаксации ребер (Форда-Беллмана), алгоритм трассировки (волновой алгоритм Ли), модифицированный алгоритм фронта волны (МАФВ). Для решения задачи визуализации рассматриваются алгоритмы обратной трассировки луча, алгоритм создания трехмерной сцены. МАФВ используется в качестве опорного алгоритма для построения областей достижимости. Построение областей достижимости позволяет интегрировано оценить возможные маршруты движения при различны сценариях управления.
Сложность построения локализующей кривой заключается во взаимном влиянии процессов распространения и локализации. Для решения задач локализационного управления на базе волнового алгоритма применен метод конкурирующих процессов. В качестве первого процесса выступает процесс распространения, а второго - процесс локализации. Оба процесса запускаются поочередно. Первый процесс выделяет область, запрещенную для 2-го процесса. Для его расчета используется разработанный на основе алгоритма маршрутизации метод построения областей достижимости.
Алгоритм МАФВ показывал хорошие результаты при расчетах оптимальных траекторий локализации на картах пересеченной местности. Однако вычислительные эксперименты показали существенное снижение быстродействия алгоритма МАФВ при расчете областей достижимости при наличии протяженных непроходимых препятствий и сильном изгибе итоговой траектории оптимального маршрута.
В значительной степени отмеченные недостатки алгоритма МАФВ устранены в разработанной двухволновой модификации волнового алгоритма (ДМВ А).
При работе алгоритма ДМВА топографическая карта покрывается матрицей ячеек. Каждый элемент матрицы (далее ячейка) содержит в себе базовую скорость движения в некотором участке местности, высоту над уровнем моря и другие необходимые параметры.
Вычислительные эксперименты показали, что с увеличением числа узлов решетки, эффективность алгоритма ДМВА возрастает по сравнению с алгоритмом МАФВ.
Визуализация результатов решения позволяет более адекватно оценить особенности предлагаемого маршрута движения наиболее естественным для человека способом. Для решения задачи трехмерной визуализации используются известные алгоритмы расчетов координат точек в пространстве, а также их видимости и освещенности.
В алгоритме создания трехмерной сцены имитирующей вид местности для некоторого участка карты с учетом ландшафта используется классический подход с представлением криволинейной поверхности в виде совокупности некоторого числа треугольников. Варьируя число и размер треугольников, можно моделировать сколь угодно сложные поверхности с нужным уровнем точности. Для задания высоты некоторой точки местности в трехмерной сцене используется карта высот. В простейшем случае это двумерный массив, где значение каждого элемента массива соответствует высоте некоторого участка местности. При задании карты высот с помощью графического файла с черно-белым изображением, высота рассчитывается исходя из яркости выбранной точки. Карта высот может создаваться динамически на основе отсканированного изображения обычной топографической карты. Непосредственное построение ландшафтной поверхности состоит в последовательной отрисовке множества треугольников заданного размера с расчетом цвета, освещенности для каждого из них.
Для отображения ландшафта ROAM (Real-time Optimally Adapting Meshes, Оптимальная адаптация областей в реальном времени) алгоритму необходимо знать, где на ландшафте больше всего неровных поверхностей, чтобы покрыть их большим числом полигонов, а там где неровностей мало, ROAM тратит меньше полигонов на отображение такой области. Необходимо знать, а как определить неровности на ландшафте. Для этих целей вводится понятие коэффициента неровности. По карте высот коэффициент неровности рассчитывается для каждого квадрата сетки, чтобы впоследствии по этому коэффициенту определять, сколько полигонов тратить на рендеринг конкретной области ландшафта. Использование коэффициента неровности позволяет более точно отображать ландшафт. Коэффициент неровности рассчитывается для каждой точки сетки высот, значение коэффициента неровности і-того квадрата влияет на критерий деления этого квадрата. Эта величина отражает, на сколько неровный ландшафт в і-том квадрате и на сколько данная степень детализации соответствует рельефу конкретной области ландшафта. Соответственно, чем на большее количество квадратов - узлов поделена нужная область ландшафта, тем больше треугольников уйдет на эту область и тем более точно она будет отображена.
Результаты исследований по главе 3 опубликованы в [15,88-90,96-98].
В четвертой главе приводится техническое описание структуры и функций разработанной информационной системы поддержки принятия решений для задач управления борьбой с лесными пожарами РАННЕР. Система РАННЕР разработана в среде Delphi 7 с использованием технологий RAD (Rapid application development, Ускоренная разработка приложений), ООП (Объектно-ориентированное программирование). Система состоит из нескольких специализированных модулей.
Функциональная модель системы выполнена в методологии IDEF0 с учетом минимально необходимой декомпозиции содержания уровней. Основные модули системы «Раннер»: расчет оптимального маршрута, расчет областей достижимости, расчет оптимальной траектории локализации, трехмерная визуализация.
По завершению процесса построения маршрута, результаты могут быть представлены пользователю в наглядном виде, как на двумерной , так и на трехмерной сцене, используя возможности модуля визуализации.
Генерируется отчет о маршруте, содержащий данные о длине, средней скорости и времени движения, а также координаты опорных точек маршрута.
Работа модуля расчета областей достижимости основана на использовании МАФВ и ДМВА. Модуль обеспечивает расчет и построение областей достижимости для некоторого временного отрезка, начало которого совпадает с моментом начала движения из точки старта, как при расчете оптимального маршрута. Длина временного отрезка задается пользователем системы. Результаты работы модуля представляются в виде некоторой области сложной формы с определенным цветом на карте местности.
Работа модуля расчета оптимальной траектории локализации основана на математической модели системы локализации процессов распространения, описанной во второй главе. Для работы модуля используются как данные о динамической проходимости местности спецтехникой, так и данные о пирологической характеристике типа местности, направлению и силе ветра, погодных условиях и дополнительных условиях, заданных пользователем.
В зависимости от типа очага распространения пожара и скорости горения, возможно построение траекторий локализации оптимальных как с точки зрения минимизации площади возгорания, так и с точки зрения скорости локализации.
Результаты работы модуля представляются в виде области, захваченной пожаром и готовой траектории локализации, выведенных на карту местности, с помощью модуля визуализации, используя условные обозначения.
Использование трехмерной графики при представлении результатов расчетов маршрутов движения по местности с различным рельефом позволяет более адекватно оценивать особенности предполагаемого маршрута движения наиболее естественным для человека способом.
Модуль трехмерной визуализации обеспечивает вывод результатов расчетов на трехмерной карте местности. Поддерживается масштабирование изображения, для детализации отдельных участков маршрута или охвата всей карты целиком. Свободное управление камерой, как с помощью клавиатуры, так и с помощью мыши, позволяет пользователю быстро перемещаться в любую точку карты, анализировать ситуацию, смотря на карту под разным углом, из различных ракурсов, визуально проходить по проложенному маршруту, используя вид «из глаз», например водителя спецтехники. Для лучшей интеграции с вышеописанными модулями, установка точек начала и конца требуемого маршрута для модуля расчета оптимальной траектории движения, или задание момента времени для модуля расчета областей достижимости, также возможна с помощью мыши,
Основные результаты по главе 4 опубликованы в [89,95]. Получено 3 свидетельства авторского права [99-101].
Результаты диссертационной работы приняты к использованию в ФГУ «ВНИИПОМЛесхоз» г.Красноярска при выполнении расчетов при разработке нормативно-технической документации по оперативной доставке сил и средств тушения на пожар; созданию и размещению объектов противопожарного устройства на территории лесного фонда.
Полученные в работе результаты используются в Сибирском государственном технологическом университете в учебном процессе по дисциплинам «Теория системного анализа и принятия решений», «Методы оптимизации».
Лесные пожары в Российской Федерации
Общая площадь земли, покрытая бореальными лесами и другими лесными массивами в пределах бореальной зоны, составляет 1.2 млрд. га, из которых на долю покрытой лесом площади приходится примерно 920 млн. га [25]. Этот показатель соответствует 29% всей площади земли, покрытой лесными массивами и 73% площади, занятой хвойными лесами. Примерно 800 млн. га бореальных1 лесов [112] с общей массой древесины на корню примерно 95 млрд. м3 пригодны к использованию (соответственно 41% и 45% общих мировых запасов). Экспортная стоимость продукции лесного хозяйства от эксплуатации бореальных лесов составляет примерно 47% от общемирового уровня [25].
Преобладающее большинство бореальных лесных угодий Евразии площадью около 900 млн. га включено в Российский лесной фонд. Площадь бореальных лесов в Российской Федерации находится в пределах 400-600 млн. га. Это количество составляет 43-65% всей площади земли, занятой сомкнутыми бореальными лесами [1, 64].
Пожары, вызванные природными причинами, являются важным экологическим фактором образования и устойчивого существования бореальных лесов [25, 47, 48, 105]. В сочетании с климатическими условиями и местными условиями произрастания, пожары определяют возрастную структуру, видовой состав, ландшафтное разнообразие и мозаичность лесного покрова [105, 106, 107, 126]. В истории евразийских бореальных лесов, пожары использовались как способ расчистки местности, ведения сельского хозяйства, охоты и животноводства. Лесные пожары являются исторически постоянным фактором их формирования [71,105, 141].
В начале XX в. значение применения сельскохозяйственных палов стало уменьшаться. Однако, несмотря на сокращение масштабов традиционного применения палов, люди по прежнему являются основным источником возникновения пожаров на природоохранных территориях. В среднем в России только 15% пожаров в охраняемых лесах возникает вследствие природных причин [52,59].
Несмотря на то, что в прошлом веке было отмечено сокращение природных пожаров в западной части Евразии (Норвегия, Швеция, Финляндия), частота возникновения пожаров увеличилась в евразийской части России. Официальные статистические данные свидетельствуют о том, что в России ежегодно возникает от 20000 до 40000 пожаров, которые поражают 2-3 млн. га лесных и других угодий [25,59,64,73,76,77]. Использование спутниковых систем NOOA/AVHRR (радиометр очень высокого разрешения), ENVISAT/MERIS (инфракрасный спектрометр среднего разрешения), позволило значительно улучшить эффективность обнаружения действующих пожаров, а также оценки пройденных огнем площадей и последствий пожаров [25]. Например, до 80-х годов прошлого века считалось, что в среднем ежегодно огнем проходилось 1,5 млн. га бореальных лесов на территории бывшего СССР. Однако анализ изображений полученных из космоса, показал, что масштаб воздействия лесных пожаров недооценивался. Исследования, проведенные с помощью дистанционных датчиков, подтвердили, что в бореальной зоне ежегодно было пройдено огнем в среднем по 8 миллионов га. В связи с продолжающимся хозяйственным освоением таежных территорий, ростом плотности населения и рекреационного использования лесов число пожаров продолжает увеличиваться [9,25,105].
Наибольший ущерб лесные пожары наносят лесным экосистемам Азиатской части страны, на долю которой приходится около 95% всей пройденной огнем площади и около 50% общего числа очагов горения. Максимальный процент охватываемой огнем площади приходится на многолесные районы Сибири и Дальнего Востока со слабо развитой инфраструктурой. До 90% всей охватываемой огнем площади ежегодно приходится на долю относительно небольшого количества (около 5%) крупных очагов горения [56].
Математическая постановка задачи оптимальной локализации лесного пожара
Рассматривается система управления, объектом которой является процесс распространения лесного пожара (ЛП), а субъектом - силы и средства борьбы с ним. Качество системы управления определяется функционалом, который характеризует обобщенные затраты на борьбу с ЛП и учитывает затраты, обусловленные продолжительностью локализации (Рт), площадью ЛП (Ps) и длинной заградительного барьера (локализующей кривой) (PL). подвижного конца заградительного барьера в момент времени t; Q(X,t), j = 1,3 - функции затрат на единицу времени локализации, единицу площади, единицу длины создаваемого заградительного барьера; to, tk - время начала и окончания процесса локализации; Хо = (Хоь ог) - координаты места возникновения очага ЛП; А - коэффициент, определяющий направление локализации относительно Хо (А = 1 при локализации по часовой стрелке, А = -1 при локализации против часовой стрелки).
Система ограничений учитывает предельную скорость локализации направление локализации относительно центра ЛП минимальное расстояние от заградительного барьера до кромки ЛП в момент локализации вектор скорости процесса локализации; U(X,t) - максимально возможное значение скорости локализации; F(t, x(t), h) = 0 - уравнение, определяющее множество точек x(t), отстоящих на расстоянии h от кромки ЛП.
Условие F(t, х, 0) 0 соответствует области ЛП в момент времени t (определяется моделями процесса распространения). Проблемы и методы математического моделирования лесных пожаров рассмотрены в разделе 1.2.
Задача (2.1) - (2.4) решается методами теории оптимального локапизационного управления [40,91-93,123]. Анализ необходимых условий оптимальности показывает [91-93,123], что в общем случае для критерия обобщенных затрат (Сь Сг, Сз Ф 0) возможны экстремали трех типов.
Экстремалям 1-го типа соответствуют участки локализирующей линии без контакта с кромкой ЛП (F(t, x(t), h) 0).
Экстремалям 2-го типа соответствуют участки локализирующей линии по кромки ЛП (F(t, x(t), h) = 0).
Экстремалям 3-го типа соответствуют участки локализирующей линии, на которых ограничение (2.3) является активным (выполняется как строгое равенство).
Для задачи максимального быстродействия (Сі = 1, Сг = Сз = 0) возможны экстремали двух первых типов.
Оптимальные траектории локализации ЛП определяются решением краевой задачи для нелинейных дифференциальных уравнений, осложненных условиями Вейерштрасса - Эрдмана для точек перехода от одного типа экстремали к другому. Аналитическое решение задачи (2.1) -(2.4) возможно для сравнительно простых частных случаев [40,92].
В общем случае численное решение задачи (2.1) - (2,4) может быть получено алгоритмом кратчайшего пути на графе-решетке, покрывающей область определения функционала (2.1), Неоднозначность области и другие ограничения геометрического характера на вид искомого решения отображаются соответствующей структурой решетки. Ребрам решетки приписываются веса, пропорциональные значениям вариационного интеграла, взятого вдоль соответствующих ребер [12]. Для решения задачи выбрана квадратная решетка.
Для модели (2.1) - (2.4) в среде MathCad 13 разработан алгоритм ее решения с визуализацией процессов распространения и локализации.
Построение оптимального маршрута
Для решения задач маршрутизации существует большое количество различных алгоритмов, основанных на модификациях нахождения кратчайшего пути в графах, на волновых алгоритмах, на маршрутных алгоритмах, есть и другие. Один из распространенных алгоритмов построения кратчайшего пути основана на теории графов.
Термин "граф" впервые появился в книге венгерского математика Д.Кенига в 1936 г., хотя начальные задачи теории графов восходят еще к Эйлеру (18 век).
Граф - это пара (V,E), где V - конечное непустое множество вершин, а Е - множество неупорядоченных пар u,v вершин из V называемых ребрами. Говорят, что ребро s = u,v соединяет вершины и и v. Ребро S и вершина и (а также s и v ) называются инцидентными, а вершины и и v -смежными. Ребра, инцидентные одной и той же вершине, также называют смежными. Степень вершины равна числу ребер, инцидентных ей.
Часть графа G - (V,E) - это такой граф G = (V\E), что V принадлежит V и Е принадлежит Е. Подграфом графа G называется такая его часть G , которая вместе со всякой парой вершин u, v содержит и ребро u,v , если только оно есть в G.
Путь, соединяющий вершины и и v, - это последовательность вершин v(0), v(l),..., v(n) (п 0) такая, что v(0) = u, u(n) = v и для любого і (0 і n-1 ) вершины v(i) и v(i+l) соединены ребром. Длина пути v(0), v(l), ... ,v(n) равна количеству его ребер т.е. п. Путь замкнут, если v(0) - v(n). Путь называется простым, если все его вершины различны. Замкнутый путь, в котором все ребра различны называется циклом. Простой цикл - это замкнутый путь, все вершины которого, кроме v(0) и v(n), попарно различны. Гамильтоновым называется граф, в котором существует простой цикл, содержащий все вершины графа (но не обязательно все его ребра).
Расстояние между двумя вершинами - это длина кратчайшего пути, соединяющего эти вершины. Обод - это граф, вершины которого v(0), v(l), ..., v(n) (п 2) можно занумеровать так, что для всех і (1 i n-l) вершина v(i) соединена ребрами с v(i-l), v(i+l), вершина v(0) - с v(n), а других ребер нет.
Граф называется связным, если для любой пары вершин существует соединяющий их путь. Максимальный связный подграф графа называется его компонентой связности. Вершины одной компоненты называются взаимно достижимыми.
Дополнением графа G называется граф G с тем же множеством вершин что и у G, причем две различные вершины смежны в G тогда и только тогда, когда они не смежны в G.
Граф называется полным, если любые две его различные вершины соединены ребром. Два графа G и Н изоморфны, если существует взаимно однозначное отображение (называемое изоморфизмом) множества вершин графа G на множество вершин графа Н, сохраняющее смежность.
Автоморфизмом графа G называется изоморфизм графа G на себя. Ориентированный граф, или орграф, G = (V,E) отличается от графа тем что Е - это множество упорядоченных пар (u,v) вершин u,v принадлежащих V, называемых дугами. Дуга (u,v) ведет от вершины и к вершине v. При этом вершину v называют преемником вершины и, а и - предшественником вершины V.
Модуль расчета оптимального маршрута
При поступлении оповещения о возникновении очага пожара в некоторой точке карты, в кратчайшие сроки должен быть выработан маршрут доставки пожарных сил в эту точку. При этом нужно учитывать ретроспективные, текущие и прогнозные данные о метеорологических условиях в части их влияния на проходимость участков местности и скорость движения по маршруту, а также избегать зон пониженной проходимости.
Работа модуля основана на модифицированном алгоритме построения оптимального маршрута движения [94]. Модуль обеспечивает построение оптимального маршрута доставки наземных сил и средств пожаротушения к очагу лесного пожара с учетом топографических условий местности, параметров спецтехники, а также дополнительных условий, определяемых пользователем системы. Поддерживается выбор степени детализации маршрута, для ускорения процесса построения в случае использования модуля в качестве инструмента приблизительной оценки траектории предполагаемого маршрута, либо повышения достоверности траектории маршрута, в случае окончательного расчета. По завершению процесса построения маршрута, результаты могут быть представлены пользователю в наглядном виде, как на двумерной, так и на трехмерной сцене, используя возможности модуля визуализации. Генерируется отчет о маршруте, содержащий данные о длине, средней скорости движения, примерного времени пути, а также координаты опорных точек маршрута.
Описание интерфейса этого и последующих модулей и примеры решения задач управления выполнены на основе информационной базы по Богучанскому району Красноярского края, разработанные и переданные для использования ВНИИПОМЛесхозом (г. Красноярск).
При пользовании программой возникают ситуации, при которых рассчитанный программой маршрут может пролегать не самым очевидным образом и тем самым вызывать некоторую долю сомнений в его корректности. Рассмотрим типовые возможные варианты построения маршрута в различных условиях. Для демонстрации используется стандартный комплект дорог и карт, прилагающийся к программе.
Самым простым вариантом расчета является ситуация без наложения зон и дополнительных условий.
В случае представленном на рисунке 4.10 маршрут достаточно очевидный, если знать, что скорость по Дороге 2 значительно больше, чем по соседним. \
В ситуации представленной на рисунке 4.11, скорость по дорогам значительно больше, чем по бездорожью. Поэтому прямое движение из точки старта в точку финиша по бездорожью отвергнут и выбран оптимальный по быстродействию маршрут, предусматривающий большой крюк вниз в обход участков низкой проходимости.
В программе предусмотрено задание зон различной проходимости в процессе решения задачи. Это позволяет оперативно учитывать изменение оперативной ситуации на возможном маршруте движения. На рисунке 4.12 показан маршрут между двумя пунктами без зоны, а на рисунке 4.13 с зоной ограничения максимальной скорости.
