Программная реализация алгоритма вычисления оптимального пути

Реализация алгоритма вычисления оптимального пути для операционных систем Windows XP / 7 / 8 / 10 была организована с помощью математического пакета MathCAD.

MathCAD — система компьютерной алгебры из класса систем автоматизированного проектирования, ориентированная на подготовку интерактивных документов с вычислениями и визуальным сопровождением, отличается легкостью использования и применения для коллективной работы. Выбор этой системы во многом обусловлен интуитивным и простым для использования интерфейсом среды, а также широким применением MathCAD в проектах, с целью визуализации результатов математического моделирования путем использования распределённых вычислений и традиционных языков программирования.

Важным инструментом в решении задания была возможность создания таблиц в среде MathCAD и последующее обращение к отдельным ее элементам. Таким образом, мы программно реализовали предложенную нам таблицу 1.

Таблица 1.

Временные задержки, заданные в таблице среды MathCAD.

Используя временную таблицу и схему дорог вычисляется время, затрачиваемое на прохождение каждого участка. Суммируются представленные в таблице значения для каждого из участков пути на каждом шаге.

При помощи функции min находятся минимальные значения для каждого последующего шага, путем складывания значения минимального пути, приводящего в данную точку с предыдущего шага и непосредственно времени, затрачиваемого на прохождение данного пути.

Из полученных в нулевом шаге результатов осуществляется выбор наименьшего, используя функцию «min» среды MathCAD.

Прохождение в прямом порядке от пункта S₀ в пункт S_кон.. Нахождение получившегося минимального пути, при помощи выбора минимального значения на каждом последующем шаге. Сопоставление топологической схемы и результатов вычислений.

Нанесение найденного пути на карту.

В результате решения задачи было выявлено, что оптимальный путь для данных условий — S₀A₁A₂A₃B₄A₅B₆S_кон и затрачиваемое на прохождение его время — 101 минуту. Сам путь представлен на рисунке 4, в то время как полный код программы — в приложении Б.