Ministry of education and science of the republic «АҚпараттық ЖӘне телекоммуникациялық технологиялар: білім, Ғылым, ТӘжірибе»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ КАЗАХСТАН

MINISTRY OF EDUCATION AND SCIENCE OF THE REPUBLIC

«АҚПАРАТТЫҚ ЖӘНЕ ТЕЛЕКОММУНИКАЦИЯЛЫҚ

ТЕХНОЛОГИЯЛАР: БІЛІМ, ҒЫЛЫМ, ТӘЖІРИБЕ»

атты ІІ Халықаралық ғылыми-тәжірибелік конференциясының

Алматы, Қазақстан, 3-4 желтоқсан, 2015 жыл

ІІ Международной научно-практической конференции

Алматы, Казакстан, 3-4 декабря, 2015 года

Of the ІІ Іnternational scientific - practical conference

Almaty, Kazakhstan, December 3-4, 2015

Алматы 2015

УДК 004(063)

ББК 32.97

А37

Ахметов Б.С. (главный редактор), Калижанова А.У., Козбакова А.Х., Кашаганова Г.Б., Заманова С.К., Абдолдина Ф.Н., Иманбекова Ұ., Мамырова А., Тайсариева Қ.Н., Жұмашева Ж.Т., Юбузова Х.И.

А37 Ақпараттық және телекоммуникациялық технологиялар: білім, ғылым, тәжірибе: Қ.И. Сәтбаев атындағы Қазақ ұлттық техникалық зерттеу университетінің ІІ Халықаралық ғылыми-тәжірибелік конференция еңбектері. 3-4 желтоқсан, 2015 ж. Алматы, Қазақстан = Информационные и телекоммуникационные технологии: образование, наука, практика: ІІ Международная научно-практическая конференция, Алматы, Казахстан. 3-4 декабря 2015 г. = Information and telecommunication technologies: education, science and practice: ІІ International scientific - practical conference, December, 3-4. 2015. Almaty, Kazakhstan. – Алматы: Қ.И. Сәтбаев атындағы ҚазҰТЗУ, 2015 – қазақша, орысша, ағылшынша. І-том. -2015. – 310 б.

ISBN 978-601-228-811-7

УДК 004(063)

ББК 32.97

Доклады, включенные в сборник, одобрены и рекомендованы программным и редакционным комитетами конференции, публикуются в авторской редакции.

УДК 004.021

1. 
   Дорожная сеть города – дороги, перекрестки (обычные), перекрестки со светофорами, кольца.
   
2. 
   Параметры дороги:
   

б) Preal(i, j)R⁺ – реальный усредненный за период времени Time поток.

в) zerotime(i, j)R⁺– время прохождения дуги, если на ней нет ни одной машины.

3. 
   δ(0,1) – светофорный параметр (для каждого перекрестка свой), обозначает, какую часть времени какой свет горит. (соответственно другой свет горит 1-δ времени) 4) Параметры кольца:
   

б) CirclemaxR⁺ – максимальная пропускная способность кольца

в) Circlereal.1, …, Circlereal.Circle_number R⁺ – реальные усреднённые за период времени Time потоки между 1-ой исходящей дорогой и второй, между второй и третьей, …., между Circle_number и 1-ой.

г) Circletime.1, …, Circletime.Circle_number R⁺ – по аналогии с zerotime(i, j) и

Circlereal.

5) Потоковые данные:

а) S – точка отправки потока.

б) T – точка принятия потока.

в) MZ⁺– величина потока (сколько машин подается в точку S).

г) TimeR⁺– время, которое не должен превысить поток из S в T.

Требуется осуществить прохождение потока M из пункта S в пункт T за время не превышающее Time. Если этого сделать невозможно из-за того, что на дорогах пробки, то

выявить эти места и передать на выход. (Скорость всех машин усреднена)

Модель, в которой будет рассматриваться задача

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

Каждая дорога – это дуга графа, каждый перекрёсток без светофора – вершина. Перекрёсток со светофором и кольцо – это более сложные конструкции, которые, тем не менее, приводятся к первым двум (дорога, перекрёсток без светофора) следующим образом: Перекрёсток со светофором

Изначально перекрёсток без светофора – обычная вершина (за исключением того, что ей приписан параметр δ), которая преобразуется в полный граф K₄ как показано на рисунке 1 ниже:

Рис. 1. Преобразование перекрёстка со светофором

Рис. 2. Пояснение к преобразованию перекрёстка со светофором

Усредненный поток Preal(i, j) каждой дуги равен 0 (будем считать, что машины проходят перекресток мгновенно). Соответственно zerotime(i, j) из предыдущего предположения тоже равен 0.

Кольцо

Пусть дано кольцо. Тогда преобразуем его под нашу модель как на рисунке 3.

Рис. 3. Преобразование кольца

В результате получим структуру в рамках простых вершин и дуг. В качестве Pmax(i, j) берем Circlemax. В качестве Preal(i, i+1) и zerotime(i, i+1) берем Circlereal.i и Circletime.i, где рассматривается путь между i-ой и i+1-ой дорогами.

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

Вводится функция h(i, j) = h(Pmax(i, j), Preal(i, j), zerotime(i, j)) R⁺ – время прохождения единицы потока данного участка (дуги). Она получает на вход пропускную способность дуги, усредненный поток и время, которое бы потребовалось единице потока, чтобы проехать по этой дуге, будь она пуста (не было бы других машин). Эта функция носит более эмпирический характер и задаваться может многими способами, при реализации алгоритма был использован следующая формула:

Ниже будет описан алгоритм, который по входным данным будет проверять возможность пропуска данного потока из вершины S в вершину T за время, не превышающее данное. Алгоритм на выходе будет либо выдавать, что поток проходит, либо, если это невозможно, будет выявлять пути (Memory.стоимость) и конкретные перекрёстки (список TrafficWay, по структуре аналогичный Memory.путь), на которых возникают заторы, мешающие успешному протеканию нашего потока. Алгоритм TrafficWay

1-шаг. Используем алгоритм Mflow, в котором

а) В качестве начального и конечного пункта берем S и T,

б) В качестве c_ij берем Pmax(i, j),

в) В качестве cost(i,j), берем h(Pmax(i, j), Preal(i, j), zerotime(i, j)),

г) И в качестве Bound берем Time.

2-шаг. Преобразуем полученный в предыдущем шаге список Memory:

Memory.стоимость = round(Time - Memory.стоимость) + 1. И затем F изменяем на сумму всех Memory.стоимость.

3-шаг. Полученный на втором шаге максимальный поток F сравниваем с M:

а) Если M <= F, то на выходе алгоритм завершает работу с выводом «Успех».

б) Если M > F, то переходим к 4-ему шагу.

4-шаг. Берем первый путь из списка Memory.путь и начинаем по нему идти. а) Берем первую дугу – переходим к пункту б).

б) Сравниваем Preal(i, j) текущей дуги с сумой Pmax(j, k) всех исходящих из вершины, в которую входит текущая, дуг. Если эта сумма больше чем Preal(i, j) (на Рис. 5.4. a < b + c + d), то переходим к следующей дуге, если такое существует, и повторяем пункт б). Если не существует, то переходим к пункту г). Если сумма меньше Preal(I, j), то переходим к пункту в) .

Рис. 4. Пояснение к 4б

в) Если сумма оказалась меньше, то в список TrafficWay (в строку с номером, аналогичным номеру записи текущего пути в списке Memory.путь) заносим номер вершины, в которую входила текущая дуга.

г) Если следующей дуги в пути не существует, то переходим к шагу 5.

5-шаг. Берем следующий путь и переходим к шагу 4а. Если такого пути нет, то переходим к 6 шагу.

6-шаг. Если TrafficWay пуст, то алгоритм завершает свою работу с выходом «Некорректные входные данные». Если TrafficWay содержит записи, то алгоритм также завершает работу и на выходе выдает два списка: Memory.путь – хранит пути и TrafficWay – хранит пробки.

Данный алгоритм работает по следующему принципу. Сначала он ищет поток, который мы можем в принципе пустить из S в T за время, не превосходящее Time (так как F – был максимальный поток за единицу времени, то, чтобы понять сколько машин успеют пройти за время Time из S в T, нужно было взять Time минус время, потраченное на элементарном пути плюс еще одна единица, которая успела доехать до T в последний момент), и, после того, как нашли его, начинаем проверку. Если входной поток не превысил максимальный, то считаем, что он успевает благополучно пройти из S в T за время Time. Если же превышает, то тогда мы предполагаем, что на пути нашего потока встречаются заторы и, начиная с четвертого шага, мы их начинаем искать. Для этого берем поочередно пути из списка Memory.путь, который был сформирован еще при выполнении алгоритма Mflow и для каждого из этих путей проделываем следующие выкладки: Идём по нему и проверяем, чтобы реальный (усредненный) поток, входя в вершину, весь мог пройти сквозь нее, то есть пропускные способности всех исходящих дуг ему это позволяли. Если, пройдя по всем путям, мы не сможем найти пробок – TrafficWay будет пуст, то тогда, скорее всего, входные данные (поток M или время Time) были заданы некорректно. Если же такие найдены, то тогда мы запоминаем с помощью TrafficWay, в каком пути и на каком узле эта пробка возникла. После чего на выход передаем эти два списка.

Вычислим временную сложность данного алгоритма по шагам:

Выполнение алгоритма Mflow дает временную сложность O((n²+m)mC). Изменение Memory.стоимость и затем суммирование занимает не более чем O(mC) операций. Далее, когда начинаем проверять все пути (не более чем mC) и на каждом пути сравниваем каждую дугу (не более чем m) с суммой исходящих (не более m), то получаем O(m³C). В итоге получаем O(n²mC+m²C+mC+m³C) = O((n²m+m³+m+m²)C) = O((n²+m²)mC).

В результате выполненной работы были построены:

1. 
   Алгоритм ShortWay для определения кратчайшего пути в ориентированном мультиграфе.
   
2. 
   Алгоритм Mflow для нахождения максимального потока, стоимость которого не превышает заданную.
   
3. 
   Алгоритм TrafficWay для анализа транспортной сети и выявления на ней узких мест.
   
4. 
   Полученные алгоритмы были реализованы на языке С++. Входные данные берутся из текстового файла (код программы описан в приложении 2).
   

ЛИТЕРАТУРА

1. 
   Beckman M., McGuire C.B., Winsten C.B. Studies in the economics of transportation. CT:Yale University Press, 1956.
   
2. 
   Chudak F., Dos Santos Eleuterio V., The traffic equilibrium problem, 2006.
   
3. 
   Попков В.К. Математические модели связности. Новосибирск: Изд. ИВМиМГ СО РАН, 2006.-409 с.
   
4. 
   Фрэнк Г., Фриш И. Сети, связь и потоки. М.: Связь, 1978.-448 с.
   

К вопросу информационного моделирования сложных систем……………………………… 108 2. Айтмагамбетов А.З., Бутузов Ю.А., Кулакаева А.Е.

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

в системах радиомониторинга на базе низкоорбитальных спутников……………………… 112 3. Алибиева Ж.М., Горбаченко В.И., Мукапил К., Тогжанова К.О.

Нейросетевые методы решения дифференциальных уравнений с частными производными... 116 4. Алинов М.Ш., Жунисбаев А.Б.

Использование ГИС-систем в экологическом мониторинге………………………………… 119 5. Альмуратова К.Б., Дауренбаева Н.А.

Методы вторичной обработки и распознавания изображений……………………………… 122 6. Аманжолова Н.И., Калиева К.А., Мырзахан О.

Оптимизация алгоритма регулирования температуры в технологических процессах…… 124 7. Ахмедиярова А.Т., Шилибаева А.С., Буранбаева А.И.