лицей №1 г. Салават Республика Башкортостан
Учитель информатики
МАТЕМАТИЧЕСКОЕ И КОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕ.
НАХОЖДЕНИЕ КРАТЧАЙШЕГО ПУТИ.
Человек издавна использует моделирование для исследования объектов, процессов, явлений в различных областях. Результаты этих исследований служат для определения и улучшения характеристик реальных объектов и процессов. Рассмотрим моделирование на следующем примере.
Задание: Имеется N населенных пунктов, соединенных дорогами. Определить кратчайший маршрут от пункта отправления до пункта назначения.
Это задача оптимизационная и различные ее модификации в действительности возникают не только при определении кратчайшего пути между населенными пунктами, но и в ситуациях иного характера. Можно попробовать справиться с этой задачей перебором всех вариантов при небольших значениях N, однако при больших N с этим справиться сложнее. Предпочтение отдается вычислительной схеме в исследовании операций (ИО). Цель, которую преследуют в процессе исследования операций (ИО), заключается в том, чтобы выявить наилучший (оптимальный) способ действия при решении той или иной задачи.
Математическая модель может быть записана в следующем виде
Найти оптимум z=f([х1,х2,….хn ) ( целевая функция).
Большинство алгоритмов, разработанных для решения задач с помощью математических моделей (ИО), не позволяют получить решение в аналитической форме. Как правило, решение находится путем осуществления ряда повторяющихся вычислительных процедур – итераций.
Алгоритм нахождения кратчайшего пути для сетей без циклов
Этап 1. Постановка задачи
Описание задачи. Рассмотрим сеть, изображенную на Рис.1. Узел 1 представляет исходный пункт, а узел 7 – пункт назначения. Сеть не имеет циклов, поскольку нет ни одной цепи, связывающей узел с самим собой.
Цель моделирования. Установить связь между маршрутом кратчайшего пути и расстояниями между населенными пунктами.
Анализ объекта. Объект моделирования – система, состоящая из двух более простых объектов: населенных пунктов и расстояний между ними. Не все смежные населенные пункты могут быть связаны дорогами. Нахождение кратчайшего пути может быть в сетях без циклов и с циклами.
Этап II. Разработка модели кратчайшего пути без циклов
Информационная модель
Таблица 1.
Объект | Параметры | Действия | |
неуправляемые | управляемые | ||
Населенные пункты | Пункт отправления ( 1) | 1. Количество населенных пунктов. 2.Пункты назначения | 1.Выбор количества населенных пунктов. 2. Выбор пункта назначения. |
Расстояния | 1.Расстояния между смежными пунктами: dij. 2. Кратчайшее расстояние между узлами 1 и j =2,..n: uj. | 1.Измерение расстояния между смежными узлами. 2.Расчет кратчайшего расстояния между узлами 1 и j. | |
Система | Маршрут кратчайшего пути | Расчет кратчайшего пути |
Математическая модель.
Введем следующие обозначения:
dij - расстояние на сети между смежными узлами i и j ;
uj - кратчайшее расстояние между узлами 1 и j , u1 =0.
Процедура завершается, когда получено значение u7 . Общая формула для вычисления uj имеет вид:
uj = min кратчайшее расстояние до предыдущего узла i плюс
i расстояние между текущим узлом j и предыдущим узлом i
.
i
Из этой формулы следует, что кратчайшее расстояние uj до узла j можно вычислить лишь после того, как определено кратчайшее расстояние до каждого предыдущего узла i, соединенного дугой с узлом j.
Для узла 1 можно вычислить лишь u2 и u3 . (Хотя узел 4 соединен с узлом 1 дугой, соответствующее значение u4 вычислить нельзя, пока не будут определены u2 и u3 ). Вычислительная схема состоит из следующих этапов.
Этап 1: u1 =0.
Этап 2: u2 =u1 +d12 =0+2=2 (из 1)
u3 =u1 +d13 =0+4=4 (из 1)
Этап 3: 
(из 3)
Этап 4: 
(из 2)
(из 3)
Этап 5: 
(из 5)
Минимальное расстояние между узлами 1 и 7 равно 13, а соответствующий маршрут - 
. Полученное решение дает кратчайшее расстояние между узлом 1 и любым из других узлов сети.
Компьютерная модель
Для моделирования выберем среду программирования Турбо Паскаль. В этой среде информационная и математическая модели объединяются, составляется программа, которая содержит следующие области:
- исходные данные: количество населенных пунктов, пункт назначения и расстояния между смежными узлами;
- промежуточные расчеты – нахождение кратчайшего расстояния между смежными узлами; результат - кратчайший путь.
Программа
uses Crt;
const
d:array[1..7,1..7] of integer=((0,2,4,10,0,0,0),
(50,0,0,11,5,0,0 ),
(50,50,0,3,0,1,0),
(50,50,50,0,8,7,0),
(50,50,50,50,0,0,6),
(50,50,50,50,50,0,9)
,(50,50,50,50,50,50,0));
var
u, b,o:array[1..7] of integer;
i, j,a, k,k2,k3,i1,n, n1:integer;
begin
Clrscr;
u[1]:=0; k2:=1;
writeln('Нахождение кратчайшего пути из узла 1 в узел N');
writeln('Ввести N');read(N1);n:=7;
{ Нахождение u[j]=min{u[i]+d[i, j] }
for J:=2 to n do
begin
k:=0;
for i:=1 to j-1 do
begin
if d[i, j]<>0 then begin u[j]:=u[i]+d[i, j];end;
if (d[i, j]<>0)and(k=0) then begin a:=u[j];k:=1;end;
if u[j]<a then a:=u[j];
end;
u[j]:=a;
end;
{Формирование маршрута кратчайшего пути }
o[1]:=n1 ;k3:=2;
j:=n1;
while j>2 do
begin
for i1:=j-1 downto 1 do
if (d[i1,j]<>0)and (u[j]=u[i1]+d[i1,j]) then
begin
o[k3]:=i1;inc(k3);
end;
j:=o[k3-1];
end;
o[k3]:=1;
{ Вывод кратчайшего пути }
writeln('Получившиеся участки:');
for i:=k3 downto 1 do
write(o[i],chr(26));
write(' дают кратчайший путь=',u[n1]);
readln;readln;
end.
Этап III. Компьютерный эксперимент.
План моделирования.
Провести расчет компьютерной модели по данным, приведенным на рис.1. Пункт назначения – узел 7. (Ответ: u7 =13, маршрут
). Провести расчет по этим же данным, пунктом назначения взять узел 4 (Ответ: u4 =7, маршрут 
). Список Литературы
1. Таха Х. Введение в исследование операций. - М.: ФБФ, 1992.
