Применение декларативных языков при решении задач на графах Антонов Александр Сергеевич

2 Содержание Описание задачи Постановка задачи Алгоритмы и решения Направление работ в будущем

3 Описание задачи В городе есть несколько госпиталей. Каждому госпиталю приписано определенное число бригад скорой помощи. Требуется развести пациентов с места аварии по госпиталям.

4 Бизнес процесс (1) Рассмотрим поэтапно процессы, происходящие в рассматриваемой системе: Обработка сигнала об аварии После поступления данного сигнала активируются следующие подпроцессы: –Получение сигнала –Определение места аварии –Определение количества пострадавших –Классификация пострадавших По характеру повреждений По пороговому времени эвкуации

5 Бизнес процесс (2) Вызов бригад скорой помощи Данный процесс включает следующие подэтапы: –Определение, на основе полученных в п.1 данных, необходимого количества бригад скорой помощи и их состав –Определение положения необходимых бригад –Определение времени прибытия бригад на место аварии

6 Бизнес процесс (3) Распределение и вывоз пациентов На данном этапе следует учесть, что пострадавшие имеют различные повреждения, как по характеру, так и по тяжести. Соответственно, для них на этапе 1 устанавливается различное пороговое время эвакуации. Процесс эвакуации проходит в следующем порядке: –Оказание первой помощи и эвакуация пациентов, которым требуется немедленная госпитализация (с применение вертолетов и реанимационных бригад скорой помощи) Определение характера повреждений В зависимости от характера повреждений определяется госпиталь, в который эвакуируется пострадавший –Оказание помощи и эвакуация пострадавших с менее значительными повреждениями Распределение пострадавших по бригадам скорой помощи Распределение пострадавших по госпиталям (зависит от характера повреждений)

7 Объекты задачи 1 Дороги характеризуются следующими показателями: Тип покрытия Загруженность Состояние (дорога может быть заблокирована для бригад скорой помощи из- за ремонта, пробок и т.п.)

8 Объекты задачи 2 Бригады скорой помощи различны и имеют следующие характеристики: Тип –Обычная –Реанимация –Вертолет Скорость передвижения Вместимость Стоимость работы

9 Объекты задачи 3 Пациенты также различаются по ряду признаков: Характер повреждений –Легкие повреждения –Переломы –Ожоги –Реанимация Срочность доставки в госпиталь

10 Объекты задачи 4 Госпитали различаются по: Количеству принимаемых пациентов Типу принимаемых пациентов

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

12 Постановка задачи Город можно представить как сеть дорог на которой заданы точки: Расположение госпиталей Место аварии Положение бригад скорой помощи на момент аварии Дороги могут иметь разное покрытие, так же, часть дорог может быть заблокирована для бригад скорой помощи в момент поступления сигнала об аварии из- за ремонта, пробок и т.п. Известно количество пострадавших в аварии, также как количество пациентов, которое готов принять каждый госпиталь.

13 Ограничения При решении задачи введем следующие ограничения: Для города опорными точками являются перекрестки. Т.о. дороги задаются участками от одного перекрестка до другого. Положение бригады скорой помощи оценивается координатами ближайшего перекрестка. Положение больницы описывается координатой перекрестка. Положение места аварии оценивается координатой ближайшего перекрестка.

14 Общее представление города

15 Этапы решения Решение задачи можно разделить на два этапа: 1.Определить кратчайшие пути (будем использовать термин «кратчайший», но речь идет не о расстоянии, а о времени, необходимом бригаде на преодоление пути) от места аварии до госпиталей на момент поступления сигнала. Далее будут браться в расчет только эти пути, чтобы для каждого больного не решать новую задачу поиска кратчайшего пути. 2.Распределить пациентов по бригадам и госпиталям.

16 1. Определение кратчайших путей

17 Кратчайший путь 1

18 Кратчайший путь 2

19 2. Распределение пациентов Необходимость решения данной задачи объясняется тем, что подход «кто первый приехал, тот везет пациента в ближайший госпиталь» не всегда оказывается верным.

20 Пример задачи распределения пациентов

21 Временная диаграмма 1 Br1 Br2 t

22 Временная диаграмма 2 Br1 Br2 t

23 Пояснение к диаграммам Если первая бригада (которая первой приезжает наместо аварии) заберет пациента в ближайший (первый) госпиталь, то второго пациента заберет вторая бригада, и так как первый госпиталь уже будет заполнен, повезет его во второй госпиталь. Время, за которое эвакуируют обоих, составит 120 (Первая бригада совершит путь до места аварии и в госпиталь Н1 затратив на это 15, вторая бригада совершит путь до места аварии и в госпиталь Н2 и затратит 120, т.о. время за которое последний пациент будет доставлен в госпиталь составит 120). Однако видно, что если первая бригада повезет пациента во второй (т.е. дальний) госпиталь, то вторая сможет доставить своего пациента в первый, и тогда общее время составит 105 (Первая бригада совершит путь до места аварии и в госпиталь Н2 затратив на это 105, вторая бригада совершит путь до места аварии и в госпиталь Н1 и затратит 30, т.о. время за которое последний пациент будет доставлен в госпиталь составит 105).

24 Варианты решения задачи распределения пациентов Рассмотрим три постановки задачи распределения пациентов: 1.Решение задачи как линейной оптимизационной 2.Решение на графах 3.Сведение к классической транспортной задаче

25 Постановка 1 задачи распределения пациентов Размерность задачи: b – бригады (1…B) i – итерации: 1 – приехать на место аварии и отвезти 1-го пациента, 2 – вернуться на место аварии и отвезти 2-го пациета,... (1…PQ), где PQ - число пациентов. h – госпитали (1…H) Постановка: 1.Набор булевых переменных Pbih (везем или нет пациента бригадой b на итерации i в госпиталь h). Если нет булевых, то целочисленные от 0 до 1. 2.Вспомогательные булевые переменные i > 1: Rbih (вспомогательная переменная для определения, нужно ли бригаде b возвращаться на место аварии после итерации i – 1) 3.Вспомогательная переменная TEmax (максимальное время эвакуации пациента) 4. h: bi Pbih HCh (hospital capacity) 5.– bih Pbih – PQ (должны отвезти не меньше пациентов, чем требуется) 6. (b, i): h Pbih 1 (нельзя везти больше одного пациента за раз) 7. (b, i1, i2), i1 < i2: h Pbi1h – h Pbi2h 0 (нельзя везти на итерации, если не везли на предыдущей итерации) 8. (b, i, h), i > 1: h Pbih + Pb,i-1,h – Rbih 1 (связь R и P) 9. (b, i), i = 1: h Pbih (ATb + HTbh) – TEmax 0 (b, i), i > 1: h Pb1h (ATb + HTbh) + ik=2 h HTbh ( Pbih + Rbih) – TEmax 0 Цель: Минимизировать TEmax, изменяя Pbih, Rbih.

26 Постановка 1 задачи распределения пациентов Данная постановка имеет ряд недостатков: Наиболее существенным недостатком является проблема расширения. При увеличении числа госпиталей, бригад или пациентов требуется внесение в текст программы дополнительных строк описывающих ограничения, вытекающие из уравнений 6 – 9. Также необходимо внесение дополнительных слагаемых в эти уравнения.

27 Постановка 2 задачи распределения пациентов Для каждой бригады задается дерево возможных путей. Чтобы не строить все дерево сразу и не хранить его в память, оно строится динамически, т.е. на каждом шаге вычисляются возможные направления следующего шага, совершенные шаги сохраняются, т.о. получаем путь, пройденный бригадой. Рассматриваются все пути, выбирается минимальный. Количество шагов равно количеству отвезенных пациентов. Цель: варьируя количество пациентов, доставленных каждой бригадой, минимизировать общее время доставки пациентов.

28 Постановка 2 задачи распределения пациентов путь := первый шаг, путь | шаг, путь | [] шаг := вернуться из госпиталя, отвезти пациента первый шаг := прибыть к месту аварии, отвезти пациента в госпиталь | []

29 Входные данные задачи распределения пациентов %problemsize(number of brigades, number of hospitals, number op patients). problem_size(2,2,2). % hospital capacity(hospital nuber, capacity) hc(1,1). hc(2,2). % arrival time /to disaster/ (N brigade, time) at(1,5). at(2,20). % time to hospital (N brigade, N hospital, time) ht(1,1,10). ht(1,2,100). ht(2,1,10). ht(2,2,100).

30 Реализация 2 задачи распределения пациентов (1) :- use_module(library('clp/bounds')). :- consult(conditions). :- consult(inc_arr). % path(N brigade, N from, N to, path time) path(Br,0,B,T) :- at(Br,AT), ht(Br,B,HT), T #= AT + HT. path(Br,A,B,T) :- ht(Br,A,HT1), ht(Br,B,HT2), T #= HT1 + HT2. % store path to list [A,B,T] step(Br,A,B,T,[A,B,T]) :- path(Br,A,B,T).

31 Реализация 2 задачи распределения пациентов (2) % route(N brigade, N from, N to, path time, Ps - edges list, HC - total quantity of patients delivered to each hospital before this route, HC - total quantity of patients delivered to each hospital after this route, Pq - number of patients) route(_,X,X,0,[],HC,HC,0). route(Br,X,Y,T,Ps,HC,HCnew,Pq) :- Pq #> 0, Pq1 #= Pq - 1, route(Br,X,Z,T1,Ps1,HC,HC1,Pq1), step(Br,Z,Y,T2,Ps2), inc(Y,_,HC1,HCnew), nth1(Y,HCnew,Hc1), hc(Y,Hc2), Hc1 =< Hc2, T #= T1 + T2, solution(BT,_,_), T < BT, Ps = [Ps1|Ps2].

32 Реализация 2 задачи распределения пациентов (3) routes([],PsARR,PsARR,TARR,TARR,HF,HF,_). routes(BrARR,PsARR,PsARRnew,TARR,TARRnew,HF,HFnew,PQARR) :- BrARR = [Br|BrARR1], nth1(Br,PQARR,PQ1), route(Br,0,_,T1,Ps1,HF,HF1,PQ1), set_arr(Br,PsARR,[#,Br|Ps1],PsARR2,_), set_arr(Br,TARR,[T1],TARR1,_), routes(BrARR1,PsARR2,PsARRnew,TARR1,TARRnew,HF1,HFnew,PQARR).

33 Реализация 2 задачи распределения пациентов (4) %mutual - finds a solution for number of brigades and rewrites it to database, if new solution is better then old, saved in database. mutual:- problem_size(Br,H,PQ), create_arr(HC1,H), create_arr(TARR,Br), length(PsARR,Br), init_arr(PsARR,[]), length(PQARR,Br), PQARR in 0..PQ, sum(PQARR,#=,PQ), numlist(1,Br,BrARR), routes(BrARR,PsARR,Ps,TARR,TARR2,HC1,HC,PQARR), msort(TARR2,TARRsort), last(TARRsort,T), retract(solution(_,_,_)), asserta(solution(T,Ps,HC)), fail.

34 Реализация 2 задачи распределения пациентов (5) % solve(TE - total time, PS - list of routs for brigades ([route of Br1 # rout of Br2]), HC - total quantity of patients delivered to each hospital) % example: solve(TE,PS,H). solve(TE,PS,HC):- asserta(solution(100000,ps,hc)), not(mutual), retract(solution(TE,Ps,Hc)), flatten(Ps,PS), flatten(Hc,HC).

35 Реализация 2 задачи распределения пациентов (6) Запрос к системе: ?- solve(TE,PS,H). Ответ: TE = [105], PS = [#, 1, 0, 2, 105, #, 2, 0, 1|...], H = [1, 1]

36 Постановка 3 задачи распределения пациентов Место происшествия представляет собой поставщика пациентов, госпитали – потребители. Предложение составляет количество, равное числу пострадавших в аварии (PQ), спрос – количество пациентов, которое готов принять госпиталь (HCj). Получаем следующие условия: Целевая функция: Где: C1j – стоимость доставки в соответствующий госпиталь

37 Направление работ в будущем Получение входных данных для задачи распределения пациентов по условиям исходной задачи и результатам решения задачи поиска кратчайших путей Уменьшение времени работы алгоритма решения задачи распределения пациентов Решение задачи поиска кратчайших путей Связь с графическим модулем приложения

38 Связь с графическим модулем Для поддержания переносимости создаваемой системы и независимости от выбранной платформы возможны два варианта реализации интерфейса с пользователем: 1.Создание Java-приложения 2.Реализация приложения как веб-сервиса Выбранный для решения основной задачи язык SWI-Prolog предоставляет библиотеки как для связи с Java, так и для генерации XML кода и создания HTTP соединений.

39 Веб-сервис веб-сервис (англ. web service) программная система, идентифицируемая строкой URI, чьи публичные интерфейсы и привязки определены и описаны языком XML. Описание этой программной системы может быть найдено другими программными системами, которые могут взаимодействовать с ней согласно этому описанию посредством сообщений, основанных на XML, и передаваемых с помощью интернет-протоколов.

40 Достоинства веб-сервисов Веб-сервисы обеспечивают взаимодействие программных систем независимо от платформы Веб-сервисы основаны на базе открытых стандартов и протоколов. Благодаря использованию XML достигается простота разработки и отладки веб-сервисов Использование интернет-протокола HTTP обеспечивает взаимодействие программных систем через межсетевой экран

41 Стандарты XML: Расширяемый язык разметки, предназначенный для хранения и передачи структурированных данных; SOAP: Протокол обмена сообщениями на базе XML; WSDL: Язык описания внешних интерфейсов веб- службы на базе XML; UDDI: Универсальный интерфейс распознавания, описания и интеграции (Universal Discovery, Description, and Integration). Каталог веб-служб и сведений о компаниях, предоставляющих веб- службы во всеобщее пользование или конкретным компаниям.

42 Веб-сервис поиска кратчайших путей Задача поиска кратчайших путей решается с помощью соответствующего веб-сервиса:

43 Графический интерфейс Графический интерфейс планируется создавать на основе открытых сервисов Google.maps

44 Схема взаимодействия с веб-сервисом