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

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

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

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

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

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

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

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

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

9

10

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

12 2. Распределение пациентов

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

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

15 Постановка 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.

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

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

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

19 Входные данные % 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).

20 Реализация 2 задачи распределения пациентов :- 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).

21 Реализация 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) :- %write('3333 '), nl, 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].

22 Реализация 2 задачи распределения пациентов %mutual(T - max time for all brigades, Ps - edges list of all brigades, HC - total quantity of patients delivered to each hospital, PQ - sum of patients) %example: mutual(T,Ps,HC,2). mutual(PQ):- [PQ1,PQ2] in 0..PQ, PQ1 + PQ2 #= PQ, HC1 = [0,0], route(1,0,_,T1,Ps1,HC1,HC2,PQ1), route(2,0,_,T2,Ps2,HC2,HC,PQ2), Ps = [Ps1, #|Ps2], T #= max(T1,T2), retract(solution(_,_,_)), asserta(solution(T,Ps,HC)), fail.

23 Реализация 2 задачи распределения пациентов % 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, PQ - number of patients to save) % example: solve(TE,PS,H,2). solve(TE,PS,HC,PQ):- asserta(solution(10000,ps,hc)), not(mutual(PQ)), retract(solution(TE,Ps,Hc)), flatten(Ps,PS), flatten(Hc,HC).

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

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

26 Поиск кратчайших путей Существуют два возможных пути решения этой задачи: 1.С использованием алгоритма Флойда, позволяющего найти кратчайшие пути между всеми парами вершин графа. 2.С использованием алгоритма Дейкстры для каждой из пар Госпиталь - Место аварии Бригада - Место аварии

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

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

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

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

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