2. «Города» (2-й тур стрежевской олимпиады по
программированию 2002 г.)
Имеется n городов (n<=20), некоторые из которых попарно соединены между
собой m дорогами (m<=100). Требуется найти кротчайший путь из города с
номером 1 в город с номером n.
Входные данные: n,m; m дорог (для каждой дороги номера городов,
которые она соединяет и ее длина).
Выходные данные: Маршрут в виде последовательности номеров
городов и путь.
Пример: Граф-иилюстрация:
Вход:
4 6
1 2 1
2 4 2
2 4 5
1 4 6
1 3 5
3 4 3
Выход: Маршрут: 1 2 4 Путь:3
Предлагается использовать для хранения информации о дорогах матрицу
смежности,
где номер столбца и строки – номера городов, которые
соединяет дорога, а сам
элемент – длина дороги. Также предлагается хранить из
нескольких одинаковых дорог
дорогу с минимальной длиной (ребро с минимальным весом) и
игнорировать при чтении
входных данных дороги, соединяющие город самого с собой
(петли)((2,2), (5,5), (1,1) и т.д.).
В программе будем
действовать следующим образом: в качестве начальной вершины
берем 1-й город и начинаем обход (поиск) до n-й вершины. Если мы
зашли в тупик, то
возвращаемся на один шаг назад и повторяем все заново.
Каждый раз при получении нового
маршрута отбираем маршрут с минимальной длиной.
Для хранения
множества пройденных вершин (городов) пользуемся булевским массивом
(битовой шкалой). Занимаем именно города, а не дороги, т.к.
один город нужно проходить
не более одного раза потому, что при многократном
прохождении одного города длина пути
только увеличивается. Таким образом, многократно снижается
трудоемкость, т.к. вычеркиваем
из матрицы смежности целый столбец и строку. Но можно пойти
другим путем: перед переходом
в новое вложение обнулить соответствующие
строку и столбец исходной матрицы и восстановить
их после возврата. Мы этого делать не будем принципиально,
т.к. для этого понадобится еще один
локальный массив (или внешний массив массивов (двумерный
массив)) в рекурсивной процедуре
(см. строгие рекомендации п.4), но еще и
потому, что такой вариант не пройдет в нашей программе,
т.к. функция, возвращающая путь по значениям массива
формирования, работает напрямую с матрицей
смежности, и возвратит нуль, т.к. соответствующие элементы
в это время будут равны нулю
(задание: откажитесь от функции суммы). Для начала
посчитаем сумму всех длин, т.е. найдем
максимально возможный путь и будем сравнивать с ним все
найденные пути, выбирая минимальный.
Напишем программу…
Program goroda;
uses crt;
var
a:array[1..20,1..20] of byte;
{матрица смежности}
b:array[1..20] of boolean; {массив хранения индексов пройденных вершин}
prom,res:array[1..20] of byte;
{массив формирования – rer, массив результата - res}
g1,g2,i,n,m:byte;
kmax,s:word; {промежуточная (s) и результирующая суммы (kmax)}
Procedure Build(v,k:byte);
var j:byte;
begin
if keypressed then halt;
b[v]:=true;
Prom[k]:=v;
if v=n then {если путь найден}
begin
if s<=kmax then {если путь
минимальный}
begin
kmax:=s;
res:=prom;
g1:=k; {после ввода дорог g1
используется как количество городов в массиве результата}
end;
end
else {если путь не
конечный, то продолжить перебор}
for j:=2 to n do
if (a[v, j]>0) and (not b[j]) then {если существует
дорога из v в j, и вершина j не пройдена}
begin
inc(s,a[v,
j]); {прибавить к сумме длину дороги} build(j,k+1); dec(s,a[v,j]); end;
b[v]:=false;
end;
begin
readln(n,m);
for i:=1 to m do
begin
readln(g1,g2,s);
{заполнение матрицы смежности: из двух одинаковых дорог
выбирается дорога с минимальным
путем и игнорируются петли}
if (a[g1,g2]=0)or(a[g1,g2]>0)and(a[g1,g2]>s)and(g1<>g2) then
begin
a[g1,g2]:=s;
a[g2,g1]:=s; inc(kmax,s); end;
end;
s:=0;
build(1,1); {построить от первого города маршрут}
writeln('-----------------------------------------------------------------------------');
writeln('Min
way=',kmax);
for i:=1 to g1 do
write(res[i]:3);
readln;
end.
Второй вариант программы – нерекурсивный.
Program New_backtracking;
uses crt;
var
a:array[0..20,0..20]
of byte; {матрица смежности}
Prom,result:array[1..20]
of byte;
b:array[0..20]
of boolean; {битовая шкала для
хранения множества
пройденных вершин}
empty:boolean;
{сигнализирует о ненайденной вершине}
g1,g2,n,m,i,k:byte;
kmax,s:word;
Procedure goprev(var x:byte);
{возвратиться на один шаг назад}
begin
Prom[x]:=0;
dec(x);
end;
Procedure gonext(var
x:byte); {перейти к следующему шагу}
begin
inc(x);
end;
Function next(x:byte):byte; {функция подачи следующей
вершины}
Var j:byte;
begin
empty:=true;
{изначально вершина не найдена}
b[Prom[x]]:=false;
{забываем предыдущий город}
dec(s,a[prom[x-1],prom[x]]); {возвращаем предыдущее
значение s}
for j:=Prom[x]+1 to n do {ищем следующую вершину}
if (a[prom[x-1], j]>0)and (not b[j]) then {если вершина j не занята и существует ребро (prom[x-1], j)}
begin
inc(s,a[prom[x-1], j]); {увеличиваем длину пути}
empty:=false; {сигнализируем о найденной вершине}
b[j]:=true; {запоминаем город}
next:=j;
exit; {досрочно выходим из
подпрограммы}
end;
end;
begin
readln(n,m);
for i:=1 to
m do
begin {Заполнение
матрицы смежности приведите к такому же
виду как и в рекурсивном варианте}
readln(g1,g2,s);
a[g1,g2]:=s; a[g2,g1]:=s;
inc(kmax,s); {заносим в kmax
максимальное значение, какое только может быть, чтобы было,
с чем сравнивать сумму от
каждого нового пути, и выбирать минимальный}
end;
{перебор}
k:=1; prom[k]:=1; b[1]:=true; inc(k); s:=0;
repeat
prom[k]:=next(k);
if (prom[k]=n)and(kmax>s) then {если найден маршрут и он минимальный, то запомнить его,
его длину и количество городов, входящих в этот путь}
begin result:=prom; kmax:=s;
g1:=k; end else
if empty then goprev(k)
else gonext(k);
until (k<2) or keypressed;
writeln('MW=',kmax);
for i:=1 to g1 do
write(result[i]:3);
readln;
end.
