[ Алгоритми перебору ]

Завдання, розібрані в тексті і запропоновані в якості вправ, неодноразово пропонувалися різні роки на різних олімпіадах і конкурсах, і встановити їх авторів не представляється можливим. У цій серії статей розглядається клас алгоритмів реалізують перебір ситуацій. Такі алгоритми використовуються в найрізноманітніших завданнях від ігор до проектування друкованих плат. В задачах такого роду часто доводиться вести пошук серед безлічі об’єктів (позицій, ситуацій), які задані не відразу все (актуально), а якимось правилом, що їх породжують (потенційно). В загальному випадку для пошуку потрібного об’єкту потрібно розглянути всі можливі об’єкти, що у зв’язку з великим числом і труднощами їх одержання вимагає занадто великого часу і ресурсів. Однак у ряді випадків вдається не розглядати явно невідповідні об’єкти. У таких завданнях велику роль відіграють як вибір моделі, так і структура даних.

1. Хвильовий алгоритм

Для ілюстрації ідеї розглянемо задачу пошуку по карті місцевості найкоротшого маршруту, що з’єднує дві задані точки («комп’ютерний штурман»). Якщо б всі ділянки були прохідні, то оптимальний маршрут будувався б легко це відрізок прямої, що з’єднує зазначені точки. На жаль, у житті є безліч нездоланних для обраного способу пересування (наприклад, пішки) перешкод (хащі, болота, будови тощо). Тому завдання про вибір оптимального маршруту не настільки проста. Більш того, вона істотно залежить від того, хто її розв’язує. Якщо вирішальний людина, то, вибираючи маршрут, він може оглядати карту місцевості всю цілком (говорять ще, що людина володіє інтегральним зором). Комп’ютера для аналізу в кожен конкретний момент доступний лише якийсь елемент карти (біля комп’ютера локальне зір). У цьому відмінність між інтегральним і локальним зором і криється одна з причин труднощів, а іноді і неможливість переформулювання алгоритму, що використовується людиною, комп’ютерний алгоритм.
Насамперед побудуємо модель задачі. Тут ми повинні вирішити, що означають слова: «карта місцевості», «непрохідний ділянка», «найкоротший маршрут».
Одна з можливих моделей така; карта місцевості розбивається на дрібні квадрати, розмірами яких можна знехтувати, і координати точки перетину діагоналей квадрата приймемо за координати цього квадрата. Тоді всю карту можна представити у вигляді двовимірного цілочислового масиву Map, індекси якого координати відповідних точок, а значення ознака можливості проходження точки з координатами х і у. Map [х, у] = 0, якщо ділянка проходимо, і дорівнює 1, якщо ні. Дві точки будемо називати сусідніми, якщо вони мають тільки одну різну координату (наприклад, точки Map [5, 4] і Map [6, 4] сусідні, а точки Map [5, 4] і Map [6, 3] немає). Маршрутом будемо вважати послідовність сусідніх точок карти. Довжиною маршруту будемо вважати число клітин в ньому (це визначення відповідає нагоди рівнинній місцевості, коли при подоланні будь-якого квадрата проходиться приблизно однаковий шлях).
В термінах цієї моделі вихідна задача формулюється так: дано двомірний числовий масив Map з елементами, рівними 0 і 1, і дві пари індексів (дві точки): x_begin, y_begin і x_end, y_end. Потрібно побудувати послідовність сусідніх елементів з нульовими значеннями таку, щоб першим елементом в ній був Map [x_begin, y_begin], а останнім Map [x_end, y_end], причому число елементів в ній було б мінімальною з усіх можливих.
Таким чином, об’єктами перебору є всі маршрути, що з’єднують зазначені точки. Ці маршрути, по-перше, треба побудувати (вони задані лише потенційно), що саме по собі непросто, по-друге, їх може бути дуже багато (значно більше, ніж число точок на карті), і з безлічі побудованих маршрутів вибрати маршрут мінімальної довжини.
Хвильовий алгоритм дозволяє обійти ці труднощі шляхом побудови відразу оптимального маршруту. При цьому, якщо поставлена задача нерозв’язна (немає жодного маршруту, що з’єднує зазначені точки), то це стає відомо на певному етапі. Основна частина цього алгоритму побудова множини точок, до яких можна дістатися за До кроків і не можна швидше (цей процес аналогічний процесу поширення хвилі, звідки і походить назва алгоритму).
Змістовний опис хвильового алгоритму таке:
1. Початковий етап. Пометим початкову точку числом 1 (в цю точку веде маршрут довжини 0).
2. Поширення хвилі. Якщо розглянута точка позначена числом До > 0 (до неї можна потрапити за К1 кроків), то всі сусідні точки, позначені нулем, треба позначити числом До + 1 (в них можна потрапити за До кроків). Поширення хвилі здійснюється до тих пір, поки це можливо (є ще сусідні, позначені нулем, точки) і доцільно (ще не дійшли до кінцевої точки).
3. Перевірка можливості побудови шляху. Якщо після поширення хвилі кінцева точка позначена певним числом До > 0, то в неї можна потрапити за станом На 1 крок. В іншому випадку ця точка недосяжна з початковою.
4. Побудова шляху. Для того щоб побудувати оптимальний маршрут, необхідно, починаючи з кінцевої точки, вибирати сусідню з нею, позначену числом на одиницю менше. Потім проробити це ж з новою точкою. І так далі, поки не доберемося до початкової.
З опису алгоритму видно, що він розпадається на два етапи: поширення хвилі (включаючи початковий етап) і побудова шляху. Така структура дозволяє природним чином розбити вихідний алгоритм на дві процедури.
Перш ніж приступити до реалізації цих процедур, відзначимо, що в них нам доведеться переглядати точки, сусідні з заданої. І тут нас підстерігає одна технічна трудність: не у всіх точок однакове число сусідів біля точок на кордоні карти сусідів менше. Щоб уникнути зайвих перевірок, розширимо масив Map і пометим всю кордон як непрохідні точки. Тоді всі розглянуті точки будуть не на кордоні і тому будуть мати однакове число сусідів 4.
Почнемо з процедури поширення хвилі. Основна дія побудову чергового фронту хвилі. Дію потрібно повторити, якщо черговий фронт хвилі був побудований і до кінцевої точки ще не дійшли. Процес побудови фронту перегляд у циклі елементів двовимірного масиву. Таким чином, у реалізації побудови фронту хвилі будемо використовувати подвійний цикл, а процедура розповсюдження хвилі містить потрійний цикл.

Procedure Wave (x_begin, y_begin, x_end, y_end: integer);
{ координати початку і кінця шляху )
var
k: integer; { номер «фронту хвилі» }
х, у: integer; { координати поточної точки }
flag: boolean; { ознака необхідності будувати черговий фронт }
begin
Map[x_begin, y_begin] := 1; { початковий етап }
k := 1; (у точку, позначену числом k, можна потрапити за k-1 крок }
flag := true; { треба будувати фронт }
while flag do { будуємо черговий фронт }
begin
flag := false;
{ можливо, що хвилі просунутися не вдасться }
for х := 1 to Length_Map do { Length_Map — максимальне значення індексу х}
for := 1 to Width_Map do { Width_Map — максимальне значення індексу у}
if Map [х, у] = k then
begin
{ переглянути -сусідів і позначити черговий фронт)
if Мар [х+1, у] = 0 then
begin
Мар [х+1, у] := k+1; flag := true
end;
if Map [x, y-l] = 0 then
begin
Map [x, y-l] := k+1; flag := true
end;
if Map [x, y+l] = 0 then
begin
Map [x, y+l] := k+1; flag := true
end;
if Map [x-l, y] = 0 then
begin
Map [x-l, y] := k+1; flag := true
end;
end;
if Map[x_end, y_end] > 0 then flag := false
else k := k+1
{ переходимо до наступного фронту хвилі}
end
end;

Процедура формування шляху використовує заповнений масив Map і формує на його основі масив Way,. починаючи від кінцевої точки.

Procedure Track (x_end, у_end: integer); { побудова шляху”}
var
k: integer; { номер фронту хвилі }
step: integer; { номер кроку шляху }
х, у: integer; { координати поточної точки }
Procedure Way_Step; { приєднання черговий точки до маршруту}
begin
Way [step, 1] := x; Way [step, 2] := у;
step := step+1; k := k-1 { мітка наступної точки }
end;
begin
step := 1
Way [l, l] := x_end; Way[l, 2] := y_end;
k := Map [x_end, y_end] — 1; { число, яким повинна бути позначена наступна точка }
х := x_end; у := у_end;
while k > 0 do { знайти наступну точку }
begin
if Map [x+l, y] = k
then begin x := x+1; end Way_Step
else if Map [x, y-l] = k
then begin у := y-l; end Way_Step
else if Map [x, y+1] = k
then begin у := y+1; end Way_Step
else if Map [x-l, y] = k
then begin x := x-l; end Way_Step
end
end;

Доказ оптимальності побудованого маршруту досить просте. Його можна запропонувати школярам в якості самостійного завдання.
Тепер програма, вирішальна вихідну задачу, буде виглядати наступним чином:

Program Short_Way;
const Length_Map = 10; Width_Map = 8; {розміри карти }
var
x_begin, y_begin, x_end, y_end: integer;
(початок і кінець шляху }
Map: array [0..Length_Map+l, 0..Width_Map+l] of integer;
{ карта з доданими кордонами }
Way: array [1..Length_Map * Width_Map,1… 2] of integer;
{ маршрут }
i, j, k: integer;
{ опис процедур наведено вище}
begin
{ перед початком потрібно задати кінці маршруту і карту }
Wave (x_begin, y_begin, x_end, y_end); { хвиля }
if Map [x_end, y_end] > 0 { якщо до кінцевої точки можна дістатися }
then Track (x_end, y_end) { координати точок шляху в масиві Way }
else writeln ( ‘ Маршрут непрохідний! ‘)
end.

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

Вправа

На шаховій дошці розташовані білий король і N чорних пішаків. Король може брати пішаки і ходити по звичайним шаховими правилами (тобто не встаючи на бите поле). Пішаки, на відміну від звичайної шахової гри, не можуть переміщатися по дошці. Напишіть програму, що визначає, чи може король з заданого поля потрапити на інше задане поле.

2. Хвиля на графі

Знову розглянемо задачу знаходження оптимального маршруту з одного населеного пункту в інший, але при інших припущеннях.
Щоб досягти кінцевого пункту швидше, будемо використовувати літак, а отже, будувати авіаційний маршрут. А оскільки саме неприємне в польоті це зліт і посадка, будемо мінімізувати їх кількість. Таким чином, маршрут це послідовність населених пунктів А1, А2, …, Ап, таких що з Ак у Ak+1 можна долетіти без проміжних посадок. Ми маємо набір точок, ряд з яких є «сусідніми» (в сенсі безпосадочного перельоту). Але на відміну від попереднього випадку, коли кожна точка мала рівно чотирьох сусідів, тут число сусідів може бути різним у різних точок. Тому уявити їх масивом, аналогічно масиву Map, нам не вдасться.
Задачі обробки деякого набору об’єктів, щодо будь-якої пари яких можна сказати, перебувають вони у певному відношенні один до одного ( «сусіди»), зустрічаються досить часто. Такі структури мають спеціальну назву графи, при цьому самі об’єкти (точки) називаються вершинами, а пари вершин, безпосередньо пов’язаних між собою (сусідні), ребрами.
Маршрутом на графі називається послідовність вершин A1, А2 …, Ап така, що для всіх k = 1,…, n1 вершини Ак і Ак+1 зв’язані ребром.
У цих термінах розглянута задача про авіаційному маршруті формулюється так: задано граф, в якому виділено дві вершини, потрібно знайти маршрут, який з’єднує їх і містить найменше число вершин.
До пошуку маршруту на графі наводять і завдання «трасування друкованих плат» з’єднання радіодеталей (тут вершини точки на платі, між якими можна проводити з’єднання, а ребра можливі шляхи проведення), і задачі пошуку виграшних стратегій в іграх (тут вершини це всілякі позиції або ситуації, які виникають у грі, а ребра це сусідні позиції, тобто такі, що одна переходить в іншу після чергового ходу), і багато інших.
При зображенні графа його вершини позначаються точками, а ребра відрізками або лініями, що з’єднують вершини. Наприклад, граф з п’ятьма вершинами a, b, з, d, e і ребрами (a, b), (a, c), (b, c), (з, d) і (d, е) можна зображати так:

Рис. 1

Найпростішим способом опису графа, що містить п вершин, є таблиця суміжності розміром n x n. Вона будується так: вершини графа перенумеровуються, і на перетині i-го рядка з j-й стовпець записується 1, якщо вершини з номерами i та j пов’язані між собою ребром, і 0 у протилежному випадку. Так, таблиця суміжності для графа, зображеного на рис. 1 з нумерацією вершин в алфавітному порядку, має вигляд:

0 1 1 0 0
1 0 1 0 0
1 1 0 1 0
0 0 1 0 1
0 0 0 1 0

При такому способі опису інформацію про графі зручно зберігати в двомірному числовому масиві з числом рядків і стовпців, рівним числу вершин (таблиця суміжності).
На жаль, таблиця суміжності неощадлива, так як в ній міститься надлишкова інформація, в той час як для роботи з графом достатньо перерахувати лише сусідні пари (яких може бути істотно менше, ніж всіх пар).
Іншим способом представлення графів (і часто більш економічним) є списковые структури, в яких посилання вказують на сусідні вершини. Наприклад, для графа, зображеного на рис. 1, списковую структуру можна взяти таку, як на рис. 2.

Масив записів;
кожен елемент
масиву містить
ім’я вершини (номер) і покажчик на список сусідніх з нею вершин. Цей масив створюється статично (перед початком роботи програми) Списки створюються динамічно в процесі роботи програми

Рис. 2

Нижче наведено опис даних і процедура створення списковой структури для подання графа:
{… }
const max_graf = 100; { максимальна кількість вершин графа}
type list = ^elem;
elem = record
num: integer;
next: list;
end;
var
Graf: array[1..max_graf] of elem;
{… }
Procedure CreateGraf(n:integer) ;
(n — число вершин графа)
var a:integer;
sosed,sosed1: list;
begin
for i:=1 to n do { для кожної вершини }
begin
new(sosed); { виділили пам’ять для нового елемента }
graf[i].next := sosed; { посилання на новий елемент }
Writeln (‘елемент ‘, i, ‘ введіть номер чергового сусіда або 0 ‘) ;
repeat
Readln(a);
sosed^.num := a; { покажчик на чергового сусіда }
if а0 then
begin
new(sosed1);
sosed^. next := sosed1
sosed := sosed1
end;
until a=0 { більше сусідів немає}
end
end;

Задача пошуку найкоротшого маршруту на графі повністю аналогічна розглянутій раніше задачі пошуку на карті (з тією тільки різницею, що немає вершин, заборонених для використання, їх можна викинути на етапі формалізації завдання, так як це на відміну від картки не порушує загальної структури розглянутих даних). Тому для її вирішення можна застосувати хвильовий алгоритм.
Покажемо, як у цьому випадку буде виглядати процедура поширення хвилі.

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] .nurn := 1; {початковий етап }
Add(num_begin, end_qu); {помістили початок шляху в чергу }
flag := true; {треба будувати фронт }
while flag and (not goal) do { будуємо черговий фронт }
begin
Extract (nurn, beg_qu) ;
&