ISSN 2225-7551

351.86:004.424.4

 

В.Ф. Гречанинов, начальник отдела

Государственная служба Украины по чрезвычайным ситуациям, г. Киев, Украина

В.В. Казимир, д-р техн. наук

Черниговский государственный технологический университет, г. Чернигов, Украина

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

В.Ф. Гречанінов, начальник відділу

Державна служба України з надзвичайних ситуацій, м. Київ, Україна

В.В.Казимир, д-р техн. наук

Чернігівський державний технологічний університет, м. Чернігів, Україна

ОСОБЛИВОСТІ АЛГОРИТМІВ ПЕРЕДИСЛОКАЦІЇ РЕСУРСІВ
ДЛЯ БОРОТЬБИ З НАДЗВИЧАЙНИМИ СИТУАЦІЯМИ НА ПОТЕНЦІЙНО НЕБЕЗПЕЧНИХ ОБ’ЄКТАХ

V.F. Grechaninov, Chairman of the Department

The State Service of Ukraine for emergency situations, Kyiev, Ukraine

V.V. Kazymyr, Doctor of Technical Sciences

Chernihiv State Technological University, Chernihiv, Ukraine

THE MAIN FEATURES OF RESOURSE RELOCATION ALGORITHMS FOR REACTION ON DANGEROUS SITUATIONS

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

Ключевые слова: граф, поиск минимального пути, нечеткий граф.

Пропонується використовувати поняття інтерпретації ваги ребра графа для зведення задачі пошуку раціонального маршруту передислокації ресурсів до класичних задач пошуку оптимального шляху на графах або до задач пошуку шляхів у нечітких графах.

Ключові слова: граф, пошук мінімального шляху, нечіткий граф.

There is proposed to use weight interpretation to convert real task definition of searching the rational rote to classical task of searching of minimal path on graph

Key words: graph, minimal path searching, fuzzy graph.

Постановка проблемы. Известно, что за последние годы на потенциально опасных объектах Украины (военных складах, арсеналах, АЭС, нефтеперерабатывающих и химических производствах и т. д.) время от времени возникали чрезвычайные ситуации (ЧС), наносящие значительный урон народному хозяйству страны.

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

В общем случае в модели развития чрезвычайной ситуации (рис.) выделяется ряд характерных этапов:

1. Этап создания благоприятных условий для возникновения ситуации (t1 –t0).

2. Этап возникновения и развития ЧС (t2 –t1).

3. Этап обнаружения и борьбы с ЧС собственными силами (t3 –t2).

4. Этап передислокации ресурсов борьбы с ЧС в место ее возникновения (t4 –t3).

5. Этап борьбы с ЧС с использованием внешних и внутренних ресурсов (t5 –t4).

6. Этап анализа ЧС (t6 –t5).

Рис. Модель развития чрезвычайной ситуации.

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

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

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

< X, R, W >, (1)

где X – множество вершин графа;

R множество ориентированных ребер графа;

W: – однозначное отображение множества ребер на множество целых неотрицательных чисел;

W (r) – вес ребра r.

Для каждой пары вершин i, xj> обозначим через Lij множества простых путей, состоящих из инцидентных ребер из xi, в xj. Каждому пути lij Lij соответствует множество ребер входящих в него, а под весом пути lij будем понимать:

(2)

Тогда задача нахождения кратчайшего пути на графе формулируем таким образом:

Найти такой lij, для которого .

В классическом варианте для задачи определения минимального пути на графе разработано множество алгоритмов. Наиболее известными из них являются: алгоритм Флойда-Уоршелла [1], алгоритм Форда-Беллмана [12; 13; 14], алгоритмы Дейкстры [3;7], алгоритм Минти [2; 7]. Имеется множество программных реализаций указанных выше алгоритмов [2; 3; 4; 6; 8; 9; 10].

Алгоритм Минти решения задачи о кратчайшем пути в сети представляет собой итеративный процесс, в ходе которого строится путь L=(s=i0, i1, ..., ip-1, ip=t).

На предварительном (нулевом) этапе алгоритма:

– Ø формируется массив значений так называемых модифицированных длин которые перед началом первой итерации полагаются равными сi,j ≥0;

– Ø осуществляется отметка вершины i0 = s числом mi0 = 0.

Далее выполняются стандартные итерации, каждая из которых включает следующие этапы:

1. Отметка вершин сети. Обозначим множество вершин cети, отмеченных на предыдущих итерациях, как (на первой итерации ). Для каждой вершины ищутся дуги, соединяющие ее с еще не помеченными вершинами-потомками j, модифицированная длина которых Найденные таким способом вершины j помечаются числом mj = i, указывающим на «родителя». В том случае, когда сразу несколько дуг, имеющих заканчиваются в одной и той же вершине j, значение для ее пометки выбирается произвольно.

Если среди вновь помеченных вершин окажется вершина t, то, значит, найден искомый путь (i0, i1,..., i(p-1), ip), где

на чем алгоритм завершается.

В случае, если вершины t нет среди отмеченных, и одновременно нельзя отметить ни одной новой вершины, то переходим к этапу 2.

2. Преобразование значений модифицированных длин дуг. Для каждой вершины ищутся дуги, соединяющие ее с еще не помеченными вершинами j, и находятся

Далее модифицированные длины всех дуг, которые соединяют отмеченные вершины с неотмеченными (, ), уменьшаются на величину

в результате чего кратчайшие неиспользованные дуги получают нулевую модифицированную длину.

Затем происходит переход к следующей итерации.

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

Если это произошло на первом шаге (что возможно только в случае, если начальная и конечная вершины соединены дугой нулевой длины), то доказываемое утверждение очевидно.

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

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

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

1. Зависимости для определения веса пути могут носить нелинейный характер относительно весов ребер.

2. Задача может быть многокритериальной.

Целью данной работы является избавление от этих недостатков.

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

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

W(l’’’) = min W(l’) ; W(l’’),

где

l’’ = l’ × l’’.

Отсюда при известных характеристиках легкости прохождения ребер можно найти характеристику легкости прохождения пути lij:

W(lij) = min (W(l1) ; W(l2),… W(lк)),

а задача нахождения самого легкого по проходимости пути сводится к

W (ij) = max ().

В каком-то смысле W(lij) можно рассматривать как характеристику функции принадлежности ребра lk орграфу. Аналогично можно рассматривать вес пути как его легкость прохождения.

Дальнейшим усложнением модели задачи является выделение для ребра 2-х и более весов с различными типами интерпретаций. Так, например, ребру r можно поставить в соответствие веса wr’ и wr’’, где wr’ имеет простейший вариант интерпретации, wr’’ имеет интерпретацию функции принадлежности ребра графу. В этом случае при наличии порогового значения принадлежности задачу нахождения рационального пути можно сформулировать как задачу нахождения оптимального относительно W’’ пути на подграфе, в котором ребра имеют функцию принадлежности, превышающую порог проходимости. Аналогичный прием можно применить тогда, когда вес ребра r представляется в виде n-ки; <,,….>.

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

<, > , <, >, …, <, >.

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

mr > + + … + .

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

Список использованных источников

1. Алгоритмы: построение и анализ = Introduction to Algorithms / Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. – 2-е изд. – М. Вильямс, 2006. – С. 1296. 

2. Ахо Альфред В. Структуры данных и алгоритмы / Ахо Альфред В., Хопкрофт Джон Э., Ульман Джеффри Д. – М. : Вильямс, 2000. – 384 с.

3. Долинский М. С. Решение сложных и олимпиадных задач по программированию: учебное пособие / М. С. Долинский. – СПб. : Питер, 2006. – 366 с.

4. Кристофидес Н. Теория графов. Алгоритмический подход / Н. Кристофидес. – М. : Мир, 1978. – 432 с.

5. Левитин А. Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms / Левитин А. – М. : Вильямс, 2006. – С. 189-195.

6. Липский В. Комбинаторика для программистов / В. Липский. – М. : Мир, 1988. – 213 с.

7. Методичка по методам оптимизации [Электронный ресурс]. – Режим доступа. : www.studfiles.ru/dir/cat14 /subj93/file10844/view103599/page7.html.

8. Новиков Ф. А. Дискретная математика для программистов / Ф. А. Новиков. – СПб. : Питер, 2000. – 304 с.

9. Окулов С. М. Программирование в алгоритмах / С. М. Окулов. – М. : БИНОМ. Лаборатория знаний, 2002. – 341 с.

10. Седжвик Р. Фундаментальные алгоритмы на C++ / Р. Седжвик. – СПб. : ООО «ДиаСофтЮП», 2002. – Часть 5: Алгоритмы на графах.496 с.

11. E. W. Dijkstra. A note on two problems in connexion with graphs. // Numerische Mathematik. – V. 1 (1959). – P. 269-271

12. Ford Jr., Lester R. (August 14, 1956). Network Flow Theory. Paper P-923. Santa Monica, California: RAND Corporation.

13. L. R. Ford, Jr., D. R. Fulkerson. Flows in Networks, Princeton University Press, 1962.

14. R. Bellman: On a Routing Problem // Quarterly of Applied Mathematics. – 1958. – Vol 16. – №. 1. – C. 87-90.