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) завершение алгоритма.
Do'stlaringiz bilan baham: