3. Побудова інформаційної системи організації оптимального виходу людей з будівель під час пожежі.

   1. Постановка задачі оптимального виходу людей з будівель під час пожежі.

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

Рис.3.1.1. Графическое представление задачи эвакуации

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

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

Поставим в соответствие данной графической модели связной граф, представленный на рис.3.2, для которого определены следующие исходные данные:

1. - множество магазинов и торговых точек в ТЗ; каждому элементу соответствует пара – координаты размещения магазина;

2. - количество посетителей, находящихся в данный момент в магазинах;

3. - множество мест выхода из ТЗ с координатами ;

4. - множество магазинов, в которых произошел пожар с координатами ;

5. - множество точек возникновения пожара в ТЗ с координатами .

6. – множество светодиодных светильников, вмонтированных в пол ТЗ с координатами .

Рис. 3.1.2. Связной граф графической модели

Вершины графа прономерованы цифрами от 1 до 6, каждой из них соответствует отдельный элемент. Так вершинам 1 – 18 соответствует множество магазинов, вершинам 19 – 58 соответствует множество светодиодных светильников, а вершинам 59 – 56 соответствует множество мест выхода.

Ставится задача определения оптимальных путей эвакуации посетителей из магазинов и ТЗ в случае возникновения пожара в одном или нескольких магазинов из множества D и/или в одной или нескольких точках ТЗ из множества Е. Каждый из путей должен быть подсвечен определенным цветом, быть минимальной длины и обеспечивать эвакуацию максимального количества людей за минимальное время.

2. Огляд методів знаходження оптимального виходу людей з будівель під час пожежі.

3. 2. 1. Алгоритм Флойда - Уоршелла

Алгоритм Флойда - Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом.

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