Ўзбекистон республикаси ахборот технологиялари ва коммуникацияларини ривожлантириш вазирлиги муҳаммад ал-хоразмий номидаги

Литература 
1. Равшанов Н., Шарипов Д.К. Программный комплекс с использованием онлайн 
сервисов для моделирования распространения вредных веществ в атмосфере // 
Информационные технологии моделирования и управления. – Воронеж, 2016. – № 
1(97). – С. 4-12. 
2. Шарипов Д.К. Разработка модели и веб-приложения для прогнозирования 
экологического состояния атмосферы // Theoretical & Applied Science : International 
Scientific 
Journal. 
– 
2016. 
– 
№ 
8(40). 
– 
С. 
58-69. 
– 
http://dx.doi.org/10.15863/TAS.2016.08.40.13. 
 
АЛГОРИТМ ПОИСКА ПУТЕЙ В ГРАФАХ И ИСПОЛЬЗОВАНИЕ ЕГО В 
АВТОМАТИЗАЦИИ ПРОГРАММИРОВАНИЯ РОБОТОВ 
 
А.Б.Якубов (ТУИТ, доцент) 
А.Н.Насриддинов (ТУИТ, студент магистратуры) 
 
Нинешный уровень развития робототехники и мехатроники требует разработки 
новых выскоэффективных методов и средств автоматизации программирования. В связи с 
этим тема данной работы, посвященной автоматизации программирования роботов, 
является весьма актуальной. 
В работе используются графовая модель технологического процесса, элементы 
теории графов и алгоритмов, а также алгоритмический язык С++. Здесь узлам графа 
приводятся в соответствие программные модули для реализации определенных 
элементарьных технологических операций, а дугам графа – последующий программный 
модуль после исходгого. Составленная таким образом графовая модель служит 
информационным пространством для составления программ.
Существует множество методов и алгоритмов поиска путей, маршрутов и других 
структур в графах. Однако каждый из них имеет свои недостатки и преимущества. Это 
зависит от применения каждого из них, и на каком языке программирования он будет 
реализован. Мы рассмотрим наиболее распространенный алгоритм поиска путей, 
маршрутов и других структур в графах. Процесс поиска путей удобно описать с 
использованием двух правил передвижения из одной вершины графовой модели в другую. 
При этом из исследуемой вершины допускается сделать один шаг вперед или назад. 
Длина шага берется равной длине одного элементарного пути. Здесь под элементарным 
путем подразумевается дуга. 

---

403 
1-е правило. Из исследуемой вершины делается один шаг вперед, если элементарный 
путь, выходящий из этой вершины, приводит к новой вершине, по которой еще не прошел 
путь. 
2-е правило. Из исследуемой вершины делается один шаг назад, если элементарные 
пути, выходящие из этой вершины приводят к вершинам, по которым уже прошел путь. 
Для поиска ориентированного пути был разработан алгоритм нахождения сигнального 
пути в графовой модели. В результате работы данного алгоритма полученный путь 
используется при программировании робота. Для формирования программы в 
соответствие с таблицей соответствия производится замена имён узлов графа 
соответствующими прораммными модулями. Данное действие реализуется с помощью 
специального программного модуля. 
Приведенный алгортм является универсальным, так как его можно использовать не 
только для определения прямых путей между заданными узлами графовой модели, но и 
для других структур. Например, колец, маршрутов, контуров, путей с обязательными 
узлами и без них. В некоторых случаях, когда необходимо распараллелировать 
выполнение некоторых технологических опреаций, требуется нахождение изолированных 
путей. В таких случаях также можно использовать вышеприведенный алгоритм.
Останов 
Установка 
нач. значения 
Установка 
начала пути 
Выбрана 
точка? 
Нач. 
узел? 
Один шаг 
назад 
Какая 
точка? 
Один шаг 
вперед 
Вывод на 
печать пути 
Переход к поиску 
сл. пути 
Определение 
точки 
Пуск 

---

404 
На рисунке представлена структурная схема алгоритма нахождения сигнальных 
путей между заданными узлами графовой модели.
Следует заметить, что при передвижении вперед, может возникнуть ситуация, в 
которой из исследуемой вершины выходит не один, а несколько элементарных путей. В 
этом случае элементарный путь в графовой модели выбирается по направлению против 
часовой стрелки. 
Данный алгоритм по сравнению с известными, кроме универсальности, 
обеспечивает высокую эффективность и простоту реализации на алгоритмических языках. 
Алгоритм реализован на алгоритмическом языке С++, его можно использовать при 
программировании промышленных роботов различного назначения. 
Структурная схема алгоритма нахождения путей 
Разработанный алгоритм поиска путей состоит из следующих шагов: 
1) установка начальных значений переменных и массивов; 
2) установка начала пути. Для этого в качестве первого элемента пути берется 
начальный узел; 
3) выбор очередной точки, находящейся от последней точки пути на расстоянии 
элементарного пути. Если такой точки нет, то осуществляется переход к 8 – шагу. 
4) проверка выбранной точки и: 
a) переход к 10 – шагу, если через данную точку ранее прошел путь; 
b) переход к 5 – шагу, если данная точка признана конечной точкой пути; 
c) переход к 7 – шагу, если через данную точку не прошел путь; 
5) вывод на печать (или запись в специально отведенный массив) сформированного 
пути. 
6) переход к 10 – шагу для поиска следующего путь. 
7) один шаг вперед. Для этого выбранная точка включается в путь и осуществляется 
переход к 3 – шагу. 
8) проверка ситуации о том, что при возвращении на один шаг назад не достигается ли 
начало пути, и осуществляется переход к 11 - шагу, если при возвращении 
достигается начальный узел. 
9) один шаг назад по пути. Для рассмотрения выбирается предыдущая точка пути. 
10) определение следующей точки, находящейся от рассматриваемой точки на 
расстоянии элементарного пути и переход к 3 – шагу. 
11) завершение алгоритма.