20. Структура моделирующего алгоритма
Мы уже отмечали, что процесс автомобильного движения существенно отличается от традиционных процессов массового обслуживания. Поэтому и структура моделирующего алгоритма обладает особенностями по сравнению с алгоритмами, рассмотренными в предыдущей главе.
Описываемый ниже моделирующий алгоритм состоит из следующих основных блоков (подалгоритмов):
формирование потока автомобилей;
определение скорости автомобиля и его перемещения;
отыскание места для обгоняющего автомобиля в своем ряду;
оценка интервала
встречном потоке;
переход к встречному потоку;
фиксация состояний системы (результатов моделирования).
Для представления моделирующего алгоритма в виде операторной схемы нам потребуются следующие операторы:
— проверка наличия в регистре данных об автомобилях (проверка условия
где
— количество автомобилей, помещенных в регистр);
— формирование параметров нового автомобиля, появившегося на дороге (формирование момента появления автомобиля с помощью - случайных чисел, выбор по жребию типа автомобиля, его скорости и других характеристик);
— проверка принадлежности
момента появления автомобиля на дороге, данному
— запись в регистр данных о сформированном автомобиле; подсчет числа автомобилей в регистре,
— выборка из регистра данных об автомобиле;
— счетчик числа автомобилей в регистре (реализует операцию
)
— отыскание свободных ячеек для запоминания расстояния
, скорости автомобиля
конкретной скорости движения
и других параметров автомобиля;
— счетчик количества автомобилей, движущихся по дороге в данном направлении (реализует операцию
)
— формирование
(
количество автомобилей, передвижение которых в данном интервале
уже рассмотрено);
— счетчик количества рассмотренных автомобилей (реализует операцию
)
— проверка условия
- выбор номера очередного автомобиля и его характеристик (просмотр автомобилей начинается от пункта В для прямого потока);
— определение характеристик дороги в точке местонахождения рассматриваемого автомобиля (уклоны, повороты, знаки и т. д.);
Описание функционирования алгоритма начнем с блока формирования потока автомобилей. Работа его протекает следующем образом. Оператор
проверяет условие
выполнение которого свидетельствует о наличии в регистре автомобилей сформированных в предыдущем интервале
Если автомобили в регистре имеются, управление по стрелке с индексом 1 передается оператору
для выборки параметров автомобиля из регистра; если нет — по стрелке с индексом 0 оператору
который формирует параметры нового автомобиля. Работа оператора
осуществляется так: из совокупности случайных чисел, равномерно распределенных в интервале (0, 1), выбирается очередное случайное число
и преобразуется к заданному закону распределения. Полученное таким образом случайное число
есть интервал времени между моментами появления
автомобилей. Поэтому момент появления
автомобиля на дороге
Затем с помощью процедуры «.выбор по жребию» определяется тип автомобиля и из блока памяти ЭВМ выбираются все интересующие нас характеристики (максимальная скорость
вес, габариты и т. д.). Управление передается оператору
который (проверкой неравенства
выясняет принадлежность сформированного автомобиля рассматриваемому интервалу
Если неравенство
не выполнено (момент появления автомобиля находится в данном
управление по стрелке с индексом 0 передается оператору
для организации счетчика
(расстояние от пункта
), и выбора ячеек памяти, куда заносятся остальные сформированные данные. Оператор
увеличивает на 1 величину
количество автомобилей на дороге (движущихся в данном направлении). Если неравенство, проверяемое оператором
выполнено, сформированный автомобиль не принадлежит рассматриваемому
данные о нем заносятся в регистр оператором
который, кроме того, реализует операцию
количество машин в регистре). На этом блок формирования потока автомобилей свою работу заканчивает.
Перейдем К описанию следующего
— определение скорости автомобиля и его перемещения. Этот блок работает циклически, просматривая по порядку все автомобили на дороге.
начале цикла
(оператор
)
— количество автомобилей, которые в данном цикле
уже рассмотрены. При переходе к очередному автомобилю оператор
прибавляет
к числу
Оператор
проверкой условия
определяет, все ли автомобили на дороге уже просмотрены; если условие, проверяемое оператором
выполнено, управление по стрелке с индексом 1 передается оператору
для выбора номера очередного автомобиля (просмотр автомобилей для прямого потока начинается с автомобиля, ближайшего к пункту В).
Оператор
извлекает из памяти машины характеристики интересующего пас участка дороги (к ним относятся уклоны, подъемы, повороты, знаки, ограничивающие скорость, характеристики качества покрытия дороги и все остальные величины, которые потребуются нам для реализации оператора
— определение скорости автомобиля). Определив с помощью оператора
скорость автомобиля, вычисляем его перемещение
за время
(оператор
и новую координату
(оператор
Оператор
проверяя условие
определяет, принадлежит ли местоположение автомобиля рассматриваемому отрезку дороги
Если
— автомобиль не достиг еще пункта В (для прямого потока), управление по стрелке с индексом 1 передается оператору
. В противном случае определяется Амомент
прибытия автомобиля в пункт В (оператор
От оператора
управление передается оператору
который осуществляет проверку неравенства
Здесь
-момент прибытия
автомобиля в пункт В, а
-момент прибытия
Мы приняли предположение, что на последнем (перед пунктом В) интервале
обгон исключается. Такое предположение на практике часто оказывается справедливым. Кроме того, мы не располагаем сведениями о движении автомобилей за точкой В. и поэтому не можем проверить возможность обгона на этом интервале
Вследствие сказанного справедливость неравенства
означает лишь формальное изменение порядка следования
автомобилей; поэтому в некоторый момент времени
автомобиль должен - снизить скорость до скорости впереди идущего. От
по стрелке с индексом 1 управление передается оператору
Оператор
определяет момент Ы, коцца данный и впереди идущий автомобили
будут находиться на расстоянии
(расстояние безопасности движения). Этот момент интересен с той точки зрения, что до
автомобиль будет двигаться со своей максимальной скоростью, а после
скоростью впереди идущего автомобиля. Оператор
присваивает данному автомобилю скорость впереди идущего. Оператор
вычисляет новое
(работает аналогично оператору
). Оператор
вычисляет новую координату
(аналогично оператору
и, наконец, оператор
вычисляет момент прибытия рассматриваемого автомобиля в пункт В. От оператора
управление передается оператору
Для подсчета количества рассмотренных автомобилей; туда же по стрелке с индексом 1 передается управление и от оператора
если неравенство не выполнено
автомобиль прибывает в В, не нарушая порядка движения).
Теперь вернемся к оператору
Если автомобиль еще не достиг пункта В
по стрелке с индексом 1 управление передается оператору
который проверяет неравенство
Признак со
присваивается обгоняющему автомобилю, поэтому выполнение неравенства
свидетельствует о том, что рассматриваемый автомобиль является обгоняющим. Тогда по стрелке с индексом 1 управление передается оператору
который, проверяя неравенство
определяет, достиг ли данный обгоняющий автомобиль места, на которое он должен стать, закончив обгон. Если неравенство
выполнено (обгон закончен), оператор
присваивает данному автомобилю признак
(что соответствует необгоняющему а автомобилю) и передает управление оператору
Если обгон еще не закончен
управление по стрелке с индексом 0 передается оператору
который записывает в счетчик
данного автомобиля величину
вычисленную оператором
и передает управление оператору
Для перехода к следующему автомобилю. Оператор
проверяет неравенство
смысл этой проверки заключается в том, чтобы определить, имеется ли между рассматриваемым и впереди идущим автомобилем расстояние, равное или большее
(расстояние безопасности). Если
(т. е. рассматриваемый автомобиль в своем движении не догнал еще предыдущего), управление по стрелке с индексом 1 передается оператору
для
записи
в счетчик
и затем оператору
Для перехода - к новому автомобилю. Если
т. е. возникла ситуация, соответствующая ложности неравенства
(оператор
). управление по стрелке с индексом 0 передается оператору
Оператор
определяет момент времени 6, когда эти автомобили будут находиться на расстоянии
Друг от друга (6? отсчитывается от начала данного
Оператор
вычисляет этот момент относительно
(начала отсчета). Оператор
определяет местоположение автомобиля к моменту
Итак, если неравенство
не выполнено, т. е. впереди идущий автомобиль мешает данному двигаться со своей максимальной скоростью, данный автомобиль вынужден идти на обгон. Чтобы определить возможность обгона, требуется решить несколько вопросов и в первую очередь вопрос о наличии места в своем ряду, куда обгоняющий автомобиль может стать по окончании обгона. Для отыскания места в своем ряду (это место ищется среди
впереди идущих автомобилей) необходимо переместить
впереди идущих автомобилей на
назад, т. е. восстановить на дороге ситуацию, возникшую к моменту
Этим и занимается оператор
На этом мы закончим рассмотрение блока определения скорости автомобиля и его перемещения и перейдем к описанию блока проверки возможности обгона. Оператор
— первый оператор блока проверки возможности обгона — решает этот вопрос, выясняя наличие дорожного знака; запрещающего обгон на данном участке дороги (обгон также запрещен на спусках, поворотах и других особо опасных участках дороги). Если обгон запрещен, управление по стрелке с индексом 1 передается оператору
для сообщения данному автомобилю скорости впереди идущего; если разрешен — по стрелке с индексом 0 оператору
которым начинается цикл отыскания места в своем ряду (поиск места ведется среди
впереди идущих автомобилей). Оператор
проверяет, все ли впереди идущие автомобили уже просмотрены. Если
— автомобили еще имеются, управление передается (по стрелке с индексом 1) оператору
для проверки неравенства
(проверки наличия интервала, длиной
между
автомобилем). Если неравенство
не выполнено,
управление по стрелке с индексом 0 передается оператору
для перехода к следующему автомобилю (реализуется операция
Если интервал длиной
не обнаружен среди всех
впереди идущих автомобилей, это значит, что данный автомобиль не может совершить обгон. Тогда оператор
сообщает ему скорость впереди идущего. Оператор
определяет
автомобиля с учетом измененной скорости
оператор
возвращает
сдвинутые автомобили на свои прежние места, т. е. восстанавливает на дороге ситуацию, имевшую место к моменту
От оператора
управление передается оператору
для записи
в счетчик
Возвратимся теперь к оператору
Если неравенство
проверяемое оператором
выполнено, управление по стрелке с индексом 1 передается оператору
который фиксирует помер автомобиля, впереди которого имеется место для обгоняющего автомобиля. От оператора
управление передается оператору
которым начинается новый блок — оценка интервала во встречном потоке.
Оператор
приближенно оценивает номер автомобиля встречного потока, ближайшего к обгоняющему. Оператор
осуществляет переход к встречному потоку для некоторой окрестности места обгона. Оператор
определяет
автомобиля (номер которого был получен в операторе
к моменту
Для этого же автомобиля оператор
проверяет неравенство
т. е. определяет, превышает ли интервал между обгоняющим и ближайшим встречным автомобилем величину
Если условие, проверяемое оператором
выполнено, управление по стрелке с индексом 1 передается оператору
Однако остается открытым вопрос о наличии автомобилей внутри интервала
Для проверки последнего обстоятельства придется последовательно переходить к
или
встречным автомобилям. От оператора
по стрелке с индексом 0 управление передается оператору
для формирования признака
Оператор
обеспечивает переход к
автомобилю встречного потока и опять передает управление оператору
На этом заканчивается первый полуцикл обследования автомобилей встречного потока. От оператора
(если условие
не выполнено) по стрелке с индексом 0 управление передается оператору
для
перехода к
автомобилю встречного потока, затем управление опять передается оператору
На этом заканчивается второй из упомянутых полуциклов.
В случае, когда условие, проверяемое оператором
выполнено, управление по стрелке с индексом 1 передается оператору
для вычисления фактического интервала между автомобилями встречного потока
Оператор
проверяет условие, состоящее в том, что вычисленный интервал меньше, чем
Если это условие выполнено и, следовательно, обгон невозможен, управление передается оператору
для присвоения даньому автомобилю скорости впереди идущего. Если
— обгон возможен, управление по стрелке с индексом 0 передается оператору
которым начинается подалгоритм, определяющий, не мешает
обгону обгоняющая встречная машина. Этот подалгоритм работает циклически, просматривая, начиная с
автомашины,
автомашин встречного потока. Оператор
осуществляет переход к
автомашине; оператор
подсчитывает
— количество уже просмотренных автомобилей. Оператор
проверяет, все ли
автомобилей мы уже просмотрели и, если
по стрелке с индексом 0 передает управление оператору
Оператор
проверяя значение признака со, определяет, является ли рассматриваемая автомашина обгоняющей или нет. Если
управление передается снова оператору
для перехода к следующей автомашине. Если
— автомобиль обгоняющий, оператор
вычисляет
и затем оператор
проверкой неравенства
определяет, помешает ли он обгону или нет. Когда нераьенство
оказывается невыполненным, т. е. встречный обгоняющий автомобиль не позволит осуществить обгон, управление по стрелке с индексом О передается снова оператору
который присваивает данному автомобилю скорость впереди идущего. Если
— обгон возможен, по стрелке с индексом 1 управление передается оператору
Оператор
сообщает данному автомобилю его максимальную скорость, т. е.
скорость, с которой автомобиль движется, если нет помех движению. Затем оператор
присваивает данному автомобилю признак
и оператор
определяет
-координату обгоняющего автомобиля для конечного момента интервала
От оператора
управление передается оператору
который, возвращая
впереди идущих автомобилей вперед, восстанавливает нормальную ситуацию на дороге. Затем управление передается оператору
для записи вычисленного оператором
в счетчик яд и затем оператору
Для перехода к новому автомобилю.
На этом заканчивается описание работы алгоритма над машинами прямого потока (из пункта А в пункт В). Оставшаяся группа операторов занимается переходом к встречному потоку, переходом к новому
фиксацией и обработкой результатов моделирования. Рассмотрим подообнее работу этого последнего блока.
Оператор
обеспечивает переход к встречному потоку и передает управление оператору
который прибавляет единицу к параметру р. Оператор
проверяет условие
Когда это условие выполнено, ушавление по стрелке с индексом 1 передается оператору
который формирует
и передает управление оператору
Если условие, проверяемое оператором
не выполнено, по стрелке с индексом 0 управление непосредственно передается оператору
Этот оператор проверяет условие
если условие выполнено, по стрелке с индексом 1 управление передается оператору
. В случае, если условие, проверяемое оператором
не выполнено, по стрелке с индексом 0 управление передается оператору
Смысл этих процедур состоит в следующем. Предположим сначала, что оператор
вступает в действие впервые за реализацию. В этом случае
(начальное условие); тогда от оператора
мы попадаем к операторам
т. е. просматриваем тот же интервал
для встречного потока. Если же речь идет о возвращении к прямому потоку, то
(оператор
и от операторов
мы попадаем к оператору
т. е. переходим к очередному
При следующем переходе к встречному потоку
но это поправляется оператором
Оператор
обеспечивает переход к следующему
и передает управление оператору
который проверяет условие
Если это условие не выполнено, значит интервал моделирования
закончен и тогда по стрелке с индексом 0 мы переходим к оператору
фиксирующему результаты моделирования за реализацию. Если же условие, проверяемое оператором
выполнено, мы переходим к моделированию процесса и управление передается оператору
От оператора
управление передается оператору
Если условие, проверяемое оператором
выполнено, управление передается по стрелке с индексом 1 оператору
для ввода начальных условий, соответствующих переходу к новой реализации процесса. Далее управление передается упомянутому ранее оператору
. В случае, если условие, проверяемое оператором
не выполнено, работает стандартная пара операторов
— обработка и выдача результатов.
В заключение остановимся кратко на способах приближенной оценки номера автомобиля встречного потока (оператор
Для проверки возможности обгона необходимо оценить расстояния между соседними автомобилями встречного потока, ближайшими к автомобилю, претендующему на обгон. Если для этой цели пользоваться перебором всех автомобилей, мы придем к непомерно большому количеству операций на ЭВМ. Желательно значительно сократить количество рассматриваемых при переборе автомобилей. Для этого необходимо хотя бы примерно оценить номер автомобиля встречного потока, находящегося поблизости от автомобиля, претендующего на обгон. Здесь могут быть пригодны различные способы, в зависимости от особенностей модели. В частности, в рассматриваемом моделирующем алгоритме применялся следующий прием.
Пусть 5 — координата автомобиля, претендующего на обгон в момент времени
Расстояние
встречный автомобиль, движущийся со скоростью
пройдет за интервал времени
Если
— интенсивность встречного потока (автомобилей в час), то за интервал времени
где
момент начала движения автомобилей на дороге, через точку
пройдет приблизительно
автомобилей. Целая часть числа
является приближенной оценкой номера автомобиля встречного потока, ближайшего к автомобилю, претендующему на обгон.
Заметим, что разработка более точных способов оценки числа
способствовала бы сокращению непроизводительного расхода операций ЭВМ при моделировании.