заведём числовую таблицу V того же размера, что и L. Значением каждого элемента V(i,j) таблицы будет минимально возможное количество шагов, которые ведут из комнаты (i0,j0) в комнату (i,j) в лабиринте. Сначала заполним таблицу V числами -1.
Установим номер очередного шага h:=0.
Присвоим элементу V(i0,j0) значение h.
НЦПОКА V(ik,jk)= -1
Просматриваем клетки таблицы (i,j), в которых V(i,j)=h. По информации, содержащейся в L, заносим число h+1 во все клетки таблицы V, соответствующие комнатам смежным комнате (i,j), которые ещё содержат -1 (т.е ещё не проходились). После просмотра увеличиваем h на 1.
КЦ
Обратный ход волнового алгоритма
Установим текущее положение i:=ik, j:=jk.
Установим h:=(i,j).
НЦ пока h<>0
Используя информацию таблицы L, находим комнату, смежную комнате (i,j), в которой записано число h-1, и устанавливаем текущее положение, соответствующее найденной комнате. В зависимости от того, в какую сторону эта комната находится от предыдущей, выводим один из символов: "С", "Ю", "З" или "В".
Уменьшаем h на 1.
КЦ
Программная реализация:
type
ROOM=record
N,S,W,E:integer
end;
var
s:string; i0,j0,ik,jk,i,j,index,h:integer; l:array[1..50,1..50] of ROOM; v:array[1..50,1..50] of integer;
begin
ReadLn(s);
i0:=25; j0:=25; i:=i0; j:=j0;
for index:=1 to ord(s[0]) do
begin
if s[index]=’C’ then
begin
l[i,j].N:=1; l[i+1,j].S:=1; i:=i+1;
end;
if s[index]=’Ю’ then
begin
l[i,j].S:=1;
l[i-1,j].N:=1;
i:=i-1;
end;
if s[index]='З' then
begin
l[i,j].W:=1;
l[i,j-1].E:=1;
j:=j-1;
end;
if s[index]=’В’ then
begin
l[i,j].E:=1; l[i,j+1].W:=1; j:=j+1;
end;
end;
ik:=i; jk:=j;
for i:=1 to 50 do
for j:=1 to 50 do
v[i,j]:=-1;
h:=0;
v[i0,j0]:=h;
while v[ik,jk]=-1 do
begin
for i:=1 to 50 do
for j:=1 to 50 do
if v[i,j]=h then
begin
if (l[i,j].N=1) and (v[i+1,j]=-1) then
v[i+1,j]:=h+1;
if (l[i,j].S=1) and (v[i-1,j]=-1) then
v[i-1,j]:=h+1;
if (l[i,j].W=1) and (v[i,j-1]=-1) then
v[i,j-1]:=h+1;
if (l[i,j].E=1) and (v[i,j+1]=-1) then
v[i,j+1]:=h+1;
end;
h:=h+1;
end;
i:=ik; j:=jk; h:=v[i,j];
while v[i,j]<>0 do
begin
if (i+1<=50) and (v[i+1,j]=h-1) and (l[i,j].N=1)
then
begin
Write('С');
i:=i+1;
end
else
if (i-1>0) and (v[i-1,j]=h-1) and (l[i,j].S=1)
then
begin
Write(’Ю’);
i:=i-1;
end else if (j-1>0) and(v[i,j-1]=h-1) and (l[i,j].W=1)
then
begin Write('З'); j:=j-1;
end
else
if (j+1<=50) and(v[i,j+1]=h-1) and (l[i,j].E=1)
then
begin
Write('В');
j:=j+1;
end;
h:=h-1;
end;
Write(' ');
end.
ВАРИАНТ 2 (с использованием динамической памяти):
Procedure Wave (num_begin, num_end: integer);
{номера вершин начала и конца пути}
Var
k: integer; {номер «фронта волны»}
num: integer; {номер текущей вершины}
flag: boolean; {признак необходимости строить очередной фронт}
beg_qu, end_qu, elem_qu: list; {начало, конец элемента очереди}
Procedure Add (num: integer; var end_qu: list);
{добавление элемента к очереди}
Var
elem_qu: list;
begin
end_qu^.num:=num; {поместили элемент в конец очереди}
new(elem_qu); {выделили память под следующий элемент}
end_qu^.next:=elem_qu; {присоединили новый элемент}
end_qu:elem_qu
end;
Procedure Extract (var num: integer; var begin_qu: list);
{извлечь элемент из списка}
var
elem_qu: list;
begin
num:=beg_qu^.num; {считали первый элемент очереди}
elem_qu:=beg_qu; {запомнили ссылку на первый элемент для последующего уничтожения}
beg_qu:=beg_qu^.next; {переносим указатель начала очереди на второй элемент}
Dispose (elem_qu); {освобождаем память, уничтожив первый элемент}
end;
begin
new (elem_qu); {инициализация очереди и размещение в ней первого элемента}
beg_qu:=elem_qu; {очередь пока пуста}
end_qu:=elem_qu;
Graf [num begin].num:= 1; {начальный этап}
Add (num_begin, end_qu); {поместили начало пути в очередь}
Flag:=true; {нужно строить фронт}
While flag and (not goal) do {строим очередной фронт}
begin
Extract (num, beg_qu); {берём значение очередного элемента очереди}
k:= Graf [num].num; {число шагов до извлечённого элемента – 1}
{просмотреть соседей, поместить очередной фронт и добавить помеченные элементы в очередь}
ref:=Graf[num].next;
repeat
a:=ref^.num;
if a<>0 then begin
{обработка очередного соседа
if Graf [a].num=0
{пометить вершину следующим фронтом}
then begin
Graf[a].num:= k+1;
Add(a, end_qu)
End;
ref:=ref^.next
{переходим к следующему соседу}
end;
until a=0;
if Graf[num_end].num<>0
then goal:= true {дошли до цели}
else
if beg_qu = end_qu then flag false {очередь пуста}
end;
end.
7.4.4 АЛГОРИТМ ДЕЙКСТРЫ
Данный алгоритм находит наименьшую суммарную весовую стоимость от первой вершины до всех вершин графа (ориентированный граф с неотрицательными весами) за время О(N2).
Работа алгоритма:
- в процееса алгоритма некоторые города будут выделенными () в начале - только город 1, в конце – все);
- для каждого выделенного города I хранится наименьшая стоимость пути 1à I, при этом известно, что минимум достигается на пути, проходящем только через выделенные города;
- для каждого невыделенного города I хранится наименьшая стоимость путь 1à I, в котором в качестве промежуточных используются только выделенные города.
При выборе пути от вершины к вершине алгоритм действует «жадным» способом: выбирает выодящее ребро с наименьшим (наибольшим) весом.
|
Пример
На рисунке указаны стоимости ребер и порядок их обхода.
ПРОГРАММНАЯ РЕАЛИЗАЦИЯ:
program deikstra;
uses crt;
type sp=^elem; {Описание данных}
elem=record
nom,st:integer;
next:sp;
end;
const
n=10;
var a:array [1..n] of sp;
f,z,log:sp;
d,I,u,nach,konn:integer;
b:array [1..n] of integer;
c:array [1..n] of boolean;
{---------------------------------}
Procedure Add(var g:sp;i,den:integer);
Begin
new(f);
f^.nom:=i;
f^.st:=den;
f^.next:=g;
g:=f;
end;
{----------------------------------}
procedure Print(j:sp);
Begin
z:=j;
while z^.next<>nil do
Begin
write(' ',z^.nom,' ',z^.st,' ');
z:=z^.next;
end;
WRITELN;
end;
{-------------------------------------}
Procedure Lesen;
var i,x,y,ver:integer;
Begin
assign(input,'input.txt');
reset(input);
readln(d);
readln(nach,konn);
for i:=1 to d do
Begin
read(ver);
new(a[ver]);
a[ver]^.next:=nil;
repeat
read(x,y);
if (x<>0) and (y<>0) then add(a[ver],x,y);
until Eoln(input);
readln;
end;
close(input);
end;
{----------------------------------------}
{-------------------------------------}
Procedure Init;
{Удаляем в вершины до которых нельзя добраться и в массив цен
ставим очень большое число}
Begin
fillchar(c,sizeof(c),true);
for i:=1 to d do
Begin
if (a[i]^.nom=0) and (a[i]^.st=0) and (a[i]^.next=nil) then
c[i]:=false;
b[i]:=32760;
end;
b[nach]:=0;
end;
{-------------------------------------}
function Proverka:boolean;
begin
Proverka:=false;
for i:=1 to d do
Begin
if c[i]=true then Begin Proverka:=true; exit; end;
end;
end;
{----------------------------------------}
function Min:integer;
var i,m,nomer:integer;
Begin
m:=32767;
nomer:=-1;
for i:=1 to d do
Begin
if (m>b[i]) and (c[i]<>false) then Begin m:=b[i];nomer:=i;;end;
end;
Min:=nomer;
end;
{---------------------------------------}
function Srav(sn,ss,pv:integer):boolean;
Begin
Srav:=(b[pv]+ss)<b[sn];
end;
{--------------------------------------}
Begin
clrscr;
Lesen;
Init;
while Proverka do
Begin
U:=Min;
c[u]:=false;
while (a[u]^.next<>nil)do
Begin
if srav(a[u]^.nom,a[u]^.st,u) then
b[a[u]^.nom]:=b[u]+a[u]^.st;
log:=a[u];
a[u]:=a[u]^.next;
dispose(log);
end;
end;
writeln(b[konn]);
end.
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОЙ РЕАЛИЗАЦИИ УЧАЩИМИСЯ:
Задача 1. ПУТЬ.
Найти кратчайшее расстояние между двумя заданнымивершинами в графе. Найти все возможные пути между этими двумя вершинами.
Задача 2.
Лабиринт задается матрицей смежности N*N, где C(i,j)=1, если узел i связан узлом j посредством дороги. Часть узлов назначается входами, часть - выходами. Входы и выходы задаются последовательностями узлов X(1),..,X(p) и Y(1),..,Y(k) соответственно.
Найти максимальное число людей, которых можно провести от входов до выходов таким образом, чтобы:
а) их пути не пересекались по дорогам, но могли пересекаться по узлам;
б) их пути не пересекались по узлам;
Задача 3.
N шестеpенок пpонумеpованы от 1 до N (N<= 10). Заданы M (0<= <=M<=45) соединений паp шестеpенoк в виде (i,j), 1<=i<j<=N (шестеpня с номеpом i находится в зацеплении с шестеpней j). Можно ли повеpнуть шестеpню с номеpом 1?
Если да, то найти количество шестеpен, пpишедших в движение.
Если нет, то тpебуется убpать минимальное число шестеpен так, чтобы в оставшейся системе пpи вpащении шестеpни 1 во вpащение пpишло бы максимальное число шестеpен. Указать номеpа убpанных шестеpен (если такой набоp не один, то любой из них) и количество шестеpен, пpишедших в движение.
Задача 4.
Имеется N прямоугольных конвертов и N прямоугольных открыток различных размеров. Можно ли разложить все открытки по конвертам, чтобы в каждом конверте было по одной открытке. Замечание. Открытки нельзя складывать, сгибать и помещать в конверт под углом. Например, открытка с размерами сторон 5:1 помещается в конверты с размерами 5:1, 6:3, 4.3:4.3, но не входит в конверты с размерами 4:1, 10:0.5, 4.2:4.2.
Задача 5.
Составить программу для нахождения произвольного разбиения 20 студентов на 2 команды, численность которых отличается не более чем в 2 раза, если известно, что в любой команде должны быть студенты, обязательно знакомые друг с другом. Круг знакомств задается матрицей (20,20) с элементами
A(ij)={1,если i знаком с j}
{0,иначе}.
Задача 6.
Имеется N человек и прямоугольная таблица А[1:N,1:N];элемент A[i,j] равен 1, если человек i знаком с человеком j, А[i,j]=А[j,i]. Можно ли разбить людей на 2 группы, чтобы в каждой группе были только незнакомые люди?
Задача 7.
Пусть группа состоит из N человек. В ней каждый имеет (N/2) друзей и не больше K врагов. У одного из них есть книга, которую все хотели бы прочитать и потом обсудить с некоторыми из остальных.
Написать программу, которая:
- Находит способ передачи книги таким образом, чтобы она побывала у каждого в точности один раз, переходя только от друга к другу и наконец возвратилась к своему владельцу.
- Разбивает людей на S групп, где будет обсуждаться книга, таким образом, чтобы вместе с каждым человеком в ту же самую группу вошло не более P его врагов.
Примечание: предполагается, что S*P>=K.
Задача 9.
В заданном графе необходимо определить, существует ли цикл, проходящий по каждому ребру графа ровно один раз.
Задача 10.
Имеется N городов. Для каждой пары городов (I,J) можно построить дорогу, соединяющую эти два города и не заходящие в другие города. Стоимость такой дороги A(I,J). Вне городов дороги не пересекаются.
Написать алгоритм для нахождения самой дешевой системы дорог, позволяющей попасть из любого города в любой другой. Результаты задавать таблицей B[1:N,1:N], где B[I,J]=1 тогда и только тогда, когда дорогу, соединяющую города I и J, следует строить.
Задача 11.
В картинной галерее каждый сторож работает в течение некоторого непрерывного отрезка времени. Расписанием стражи называется множество пар [Т1(i), Т2(i)] - моментов начала и конца дежурства i-го сторожа из интервала [0,EndTime].
Для заданного расписания стражи требуется:
(а) проверить, в любой ли момент в галерее находится не менее двух сторожей.
Если условие (а) не выполнено, то:
(б) перечислить все интервалы времени с недостаточной охраной (менее 2 сторожей).
(в) добавить наименьшее число сторожей с заданной, одинаковой для всех длительностью дежурства, чтобы получить правильное расписание (т.е. удовлетворяющее условию (а)).
(г) проверить, можно ли обойтись без добавления новых сторожей, если разрешается сдвигать времена дежурства каждого из сторожей с сохранением длительности дежурства.
(д) Если это возможно, то составить расписание с наименьшим числом сдвигов.
Задача 12.
Вводится N - количество домов и К - количество дорог. Дома пронумерованы от 1 до N. Каждая дорога определяется тройкой чисел - двумя номерами домов - концов дороги и длиной дороги. В каждом доме живет по одному человеку. Найти точку - место встречи всех людей, от которой суммарное расстояние до всех домов будет минимальным.
Если точка лежит на доpоге, то указать номера домов – концов этой доpоги и расстояние от первого из этих домов. Если точка совпадает с домом, то указать номер этого дома.
Примечание: длины дорог - положительные целые числа.
Задача 13.
N колец сцеплены между собой (задана матрица A(n*n), A(i,j)=1в случае, если кольца i и j сцеплены друг с другом и A(i,j)=0 иначе). Удалить минимальное количество колец так, чтобы получилась цепочка.
Задача 14.
Янка положил на стол N выпуклых K-гранников и N различных типов наклеек по K штук каждая. Ночью кто-то наклеил наклейки на грани, по одной на грань. Помогите Янке расставить многогранники так, чтобы наклейка
каждого типа была видна pовно K-1 раз.
Задача 15.
Имеется N точек и M проводков. Проводком можно соединить некоторую пару различных точек, причем пара может быть соединена не более чем одним проводком. Все проводки должны быть использованы.
Пусть Di - количество проводков, которые будут соединены с точкой с номером i, i=1,..., N.
Необходимо соединить N точек с помощью M проводков таким образом, чтобы сумма S=D1*D1 + D2*D2 +... + Dn*Dn была максимальной.
Вывести величины Di в неубывающем порядке и. по требованию (priznak=1), список соединений.
ВВОД:
<Введите N:> N (N<=100)
<Введите M:> M (M<=1000)
<PRIZNAK=> PRIZNAK
ВЫВОД:
<Результирующая конфигурация:> Di в неубывающем порядке.
<Сумма S> S
<Список соединений>
<Точку 1 соединить с> список точек
.....
<Точку N соединить с> список точек
Задача 16.
Задано N городов c номерами от 1 до N и сеть из M дорог с односторонним движением между ними. Каждая дорога задается тройкой (i, j, k), где i - номер города, в котором дорога начинается, j - номер города, в котором дорога заканчивается, а k - ее длина (число k - натуральное). Дороги друг с другом могут пересекаться только в концевых городах.
Все пути между двумя указанными городами A и B можно упорядочить в список по неубыванию их длин (если есть несколько путей одинаковой длины, то выбираем один из них). Необходимо найти один из путей, который может быть вторым в списке.
Вывести его длину L и города, через которые он проходит.
ВВОД:
<Количество городов N:> N
<Количество дорог M:> M
<Начало, конец и длина дороги 1:> i1, j1, k1
......
<Начало, конец и длина дороги M:> iM, jM, kM
<Города A и B, между которыми надо найти путь:> A, B
ВЫВОД:
<Пути нет>
или
<Путь проходит по городам> A, i1, i2,..., B
<Длина пути> L
Задача 17. Ларсона
Пусть G - конечный неориентированный связный граф. Предположим, что он представляет собой систему тоннелей, в которых может прятаться беглец. Группа из S полицейских, двигаясь по туннелям, стремится схватить этого беглеца, который может двигаться с любой скоростью, стремясь избежать поимки. Требуется определить минимальное количество полицейских S, гарантирующих поимку беглеца.
[s1]аль