VI Международная студенческая научная конференция Студенческий научный форум - 2014

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

Алгоритмы нахождения кратчайших путей между вершинами графа принадлежат классу NP полных задач, которые экспоненциально зависят от размера входа. Решать такие задачи методом перебора всех элементов не представляется возможным. Поэтому решение задачи на графе состоит в том, чтобы построить достаточно эффективный алгоритм, который гарантированно находит оптимум в случае, если множество допустимых решений не пусто. При решении задачи выполнен анализ алгоритмов, применяемых в настоящее время для поиска кратчайших путей между вершинами графа [1,2]. При этом проведено сравнения объемов вычислений, т. е вычислительной сложности по каждому из алгоритмов. Сравнительный анализ показал, что наименьшую трудоемкость имеет алгоритм Дейкстры. Алгоритм Дейкстрыпрост в реализации, т. к. использует операции двух типов: операцию сложения и операцию сравнения по минимуму. Этот алгоритм широко используется для решения задач выбора рационального движения транспорта .

В соответствии с выбранным алгоритмом, разработана структурная схема, на основе которой спроектировано цифровое устройство (ЦУ) для поиска оптимальных путей в графе (рисунок 1). Схема состоит из следующих узлов:

ТГ – тактовый генератор;

БС – блок сопряжения;

БУ – центральный блок управления;

БВИ – блок вывода информации;

ММГ– матричная модель графа, содержит электронную модель графа;

БОП – блок операндов, предназначен для установки начальных данных, а так же для хранения промежуточных значений и результата;

БПДП – блок поиска длинны пути, выполняет поиск кратчайшего пути до каждой неотмеченной вершины графа, если такой существует;

БПМП – блок поиска минимального пути, анализирует значения кратчайших путей для всех неотмеченных вершин и выбирает минимальное.

Рисунок 1 – Электрическая структурная схема ЦУ

Для реализации ЦУ, отвечающего современным стандартам, использованы программируемые логические интегральные схемы (ПЛИС). Применение ПЛИС позволяет усовершенствовать работу устройства путем применения новой программной прошивки микросхемы – загрузчика ПЛИС без дополнительных аппаратных затрат и переразводки печатной платы. Электрическая функциональная схема спроектирована в САПР ISE WebPACK с помощью схемотехнического редактора и проверена с помощью пакета моделирования ISim. Каждый функциональный блок устройства объединяется в макрос. На рисунке 2 представлены функциональная схема блоков ЦУ и их временные диаграммы. Проведен анализ временных диаграмм, выполненных для графа, который имеет 8 вершин. При использовании частоты 400МГц (t_f=2,5нс): время анализа будет равно Ta=(8*3+6)*8*2,5=600нс; время загрузки Tз=8²*2*2,5=320нс; время чтения Tч=2*8*2*2,5= 80нс; общее время работы T=600+320+80= 1мс. Данный расчет говорит о высоком быстродействии ЦУ.

Результаты проектирования ЦУ показали, что его использование позволит повысить эффективность работы транспорта за счет сокращения времени на планирование маршрута движения автотранспорта. Устройство имеет высокое быстродействие и малые аппаратные затраты. Получаемые в результате использования цифрового устройства рациональные маршруты могут привести к снижению затрат на перевозку грузов.

Рисунок 2 – Функциональная схема блоков ЦУ и их временные диаграммы

Литература

1. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ. 2-е изд.-М.: «Вильямс», 2006. – 1296 с.

2. Федосеева Л.И. Устройство оптимизации кратчайшего пути между вершинами графа на примере задачи коммивояжера / Л.И.Федосеева // XXI век: итоги прошлого и проблемы настоящего плюс: пер. науч. изд. – Пенза, 03/2011, с.132-138.

Код для цитирования: Скопировать