Methods_AP_PZ

Приклад 7.4

В рекурсивній програмі, де кількість вводів зменшується вдвічі, але

необхідно перевірити кожний елемент, виникає наступне рекурентне співвідношення:

CN = CN/2 + N, де N ≥ 2 і С1 = 0.

Розв’язання. CN порядка 2N. Рекурсія розкривається в суму N + N / 2 +

N / 4 + N / 8 + ... (Як і завданні 2, рекурентне співвідношення визначено точно тільки в тому випадку, якщо N є ступенем числа 2). Якщо дана послідовність нескінченна, то сума простої геометричної прогрес-сии дорівнює 2N. Оскільки ми використовуємо цілочисельне ділення і зупиняємося на 1, дане значення є наближенням до точного відповіді. У

точному рішенні використовуються властивості двійкового представлення числа N.

Приклад 7.5

У рекурсивній програмі, яка повинна виконати лінійний прохід по

вводах до, протягом чи після розбиття їх на дві половини, виникає наступне рекурентне співвідношення:

CN = 2СN/2 + N, де N ≥ 2 і С1 = 0.

Розв’язання. CN порядка N lgN. На це рішення посилаються набагато ширше, ніж на інші з наведених тут, оскільки ця рекурсія використовується в

цілому сімействі алгоритмів "розділяй і володарюй".

.

.

.

n.

51

Ми знаходимо рішення майже так само, як це було зроблено у Прикладі

2, але з додатковим прийомом на другому кроці - діленням обох частин рівності на 2n, який дозволяє розкрити рекурсію.

Приклад 7.6

У рекурсивній програмі, яка розбиває введення надвоє, а потім виробляє постійна кількість інших операцій виникає наступна рекурсія.

CN=2CN/2 + 1, где N ≥ 2 и С1 = 1.

Розв’язання. CN порядка 2N. Це рішення можна отримати так само, як і рішення прикладу 4. За допомогою наведених методів можна вирішити різні варіанти подібних завдань, що мають інші початкові умови або невеликі відмінності в додатковому члені, але необхідно пам'ятати, що деякі рекурсії,

що здаються схожими, можуть мати набагато більш складні рішення.

7.2 Завдання на практичну роботу

Виконати завдання згідно вказівок викладача.

1.Створіть рекурсивну програму, яка знаходить максимальний елемент

вмасиві, виконуючи порівняння першого масиву з максимальним елементом іншої частини масиву (обчисленим рекурсивно).

2.Створіть рекурсивну програму, яка знаходить максимальний елемент

взв'язковому списку.

3.Вирішіть задачу про Ханойські вежі рекурсивно.

4.Створіть рекурсивну програму, яка обчислює довжину i-ой мітки на лінійці з 2N - 1 мітками.

5.Створіть програму, яка забезпечує рекурсивне рішення задачі про Ханойські вежі шляхом заповнення масиву, що містить всі переміщення.

6.Створіть функцію, яка ефективно обчислює кількість кінцевих нулів у двійковому поданні цілого числа.

7.Малювання зірки Коха n-го порядку зводиться до виконання

послідовності команд типу "повернути на α градусів, потім намалювати

52

сегмент лінії довжиною 1/3N. Установіть відповідність з системами числення, що дозволяє малювати зірку шляхом збільшення значення лічильника і подальшого обчислення на базі цього значення кута а.

53

Практична робота № 8

Евристика

8.1 Теоретичні відомості

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

Приклад 8.1

Алгоритм ЦІД (ціле і дробове)

В алгоритмічних мовах високого рівня оператор INT (X) для виділення цілої частини змішаного десяткового подання числа Х реалізується за допомогою евристичного алгоритму з порозрядним зважуванням. Розробимо такий алгоритм. Перша, найпростіша версія алгоритму ЦІД могла б полягати в послідовному відніманні одиниці з Х, до тих пір поки результат не стане менше 1 і одночасного підрахунку кількості проведених вирахувань.

Очевидно, що кількість вирахувань, підрахована лічильником С, дорівнює цілій частині С (Х), а дробова частина D (X) дорівнює X - C (X), і для реалізації першої версії (назвемо її "рішення в лоб") можна використати найпростіший рекурсивний алгоритм виду

c = 0

while x >= 1 do х = х - 1 and c = c + 1 od.

Перебір з поверненням

Лабіринт, що складається із прохідних і непрохідних кліток, заданий матрицею A розміром mxn. Елемент матриці A[i,j]=0, якщо клітинка (i,j)

прохідна. А якщо ні, то A[i, j] .

Потрібно знайти довжину найкоротшого шляху із клітинки (1, 1) у

клітинку (m, n).

Фактично дана матриця суміжності (тільки в ній нулі замінені

нескінченностями, а одиниці – нулями). Лабіринт являє собою граф.

54

Вершинами дерева варіантів у даному завданні є шляхи, що починаються в клітинці (1, 1). Ребра показують хід конструювання цих шляхів і з'єднують два шляхи довжини k і k+1, де другий шлях виходить із першого додаванням до шляху ще одного ходу.

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

Way.

Також необхідний масив Dist, розмірність якого відповідає кількості вершин графа, що зберігає для кожної вершини відстань від неї до вихідної вершини.

Нехай поточною є деяка клітинка ( на початку роботи алгоритму – клітинка (1, 1) ). Якщо для поточної клітинки є клітинка-сусід Neighbor,

відсутня в Way, у яку на цьому шляху ще не ходили, то додаємо Neighbor в Way і поточній клітинці привласнюємо Neighbor, інакше дістати з Way.

Наведений вище опис дає чітко зрозуміти, чому цей метод називається перебором з поверненням. Поверненню тут відповідає операція "дістати з

Way ", яка зменшує довжину Way на 1.

Перебір закінчується, коли Way порожній і робиться спроба повернення назад.

Way є поточним шляхом, але в процесі роботи необхідно зберігати й оптимальний шлях Optimalway.

Удосконалення алгоритму можна зробити в такий спосіб: не дозволяти,

щоб довжина Way була більше або дорівнює довжині Optimalway. У цьому випадку, якщо й буде знайдений якийсь варіант, він свідомо не буде оптимальним. Таке вдосконалення в загальному випадку означає, що як тільки поточний шлях стане свідомо неоптимальним, треба повернутися назад. Дане поліпшення алгоритму дозволяє в багатьох випадках сильно скоротити перебір.

55

Рисунок 8.1 - Демонстрація алгоритму перебору з поверненням

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

Цей переборний алгоритм, який заснований на пошуку в ширину,

складається із двох етапів:

1.Поширення хвилі;

2.Зворотний хід.

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

(з початку воно найчастіше неможливо).

56

Рисунок 8.2 - Демонстрація хвильового алгоритму Помітимо, що перебір методом пошуку в ширину в порівнянні з

перебором з поверненням, як правило, вимагає більше допоміжної пам'яті,

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

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

Маршрутний алгоритм, заснований на обчисленні відстані між точками

Робота алгоритму починається від початкового елемента. При цьому навколо початкового елемента розглядається 8-мі елементна околиця. Від кожного елемента околиці до кінцевого елемента оцінюється довжина шляху.

При цьому відстань між точками обчислюється по формулі:

D=|xi-xb|+|yi-yb|

де (Xi,Yi) - координати точки околиці. (XВ,YВ) - координати кінцевого елемента.

У такий спосіб обчислюється вісім значень із яких вибирається мінімальне. Елемент від якого відстань виявилася мінімальним вибирається в

якості елемента траси. Довкола нього знову розглядається 8-мі елементна

57

околиця. Процес триває доти поки не буде досягнутий кінцевий елемент.

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

Маршрутний алгоритм, заснований на рекурентному співвідношенні

Маршрутний алгоритм можна побудувати на основі наступного рекурентного співвідношення:

y(x) = 2y(x + h) + y(x + 2h) + d

де x,y(x) - абсциса й ордината елемента займаного трасою на даному кроці.

(x + h) - ордината елемента займаного трасою на попередньому кроці.

(x + 2h) - ордината елемента віддаленого від, що обчислюється на 2

кроку.

h - величина зміни абциси на кожному кроці.

d (delta) - це функція визначає вид траси. Якщо d=0, то будується прямолінійна траса, якщо d=const то будується параболічна траса.

Ордината чергового елемента траси обчислюється по рекурентній формулі, а абсциса траси обчислюється по формулі :

D=Xn=Xn-1+h

Знак "+" або "-" у рекурентной формулі вибирається виходячи з того звідки починається побудова траси, з початкового елемента "+", і відповідно з кінцевого "-".

По цій формулі щоб обчислити 3-й елемент траси необхідно знати два попередні. Першим елементом є вихідний елемент A(XA,YA), тоді ордината другого елемента обчислюється по формулі :

Y(X)=Y(XA)+ ((Y(XA)-Y(XB))/(XA-XB))*h

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

58

Евристика лівої руки

Щоб пройти лабіринт до виходу з нього або повернутися в точку входу,

якщо проходу з даної початкової точки немає (тобто не заблукати), необхідно рухатися, увесь час торкаючись стіни лівою рукою.

Вхідні дані. Бінарна матриця L (M,N)‚ де: M – кількість рядків (висота лабіринту), N – кількість стовпців (ширина лабіринту), s – індекс рядка, k –

індекс стовпця, L (s, k) = 1 - прохід, L (s, k) = 0 – стіна

V, наприклад, V = L(1,2) - точка входу,

Н - напрямок, з якого ввійшли в лабіринт (далі - у поточну точку)

Н::= 1, якщо прибув зверху,

Н::= 2, якщо прибувсправа,

Н::= 3, якщо прибув знизу й Н::= 4, якщо прибув зліва.

Вихідні дані. Маршрут через лабіринт у вигляді послідовності координат

(X(i) – горизонтальна, Y(i) – вертикальна) прохідних крапок лабіринту аж до досягнення граничної точки.

59

Граничною точкою або точкою виходу з лабіринту є точка, для якої s=1

або s=m або k=1 або k=n, тобто умовою завершення роботи є досягнення граничної точки:

if s=1 or s=m or k=1 or k=n then

<знайдений вихід з лабіринту, друкувати маршрут> else

<продовжувати пошук>

fi

Евристика лівої руки – рухатися в лабіринті, увесь час тримаючись стіни лівою рукою:

1)гарантує відшукання виходу, якщо він є, або повернення у вихідну точку, якщо виходу немає,

2)не гарантує знаходження глобального экстремума, тобто знайдений маршрут не обов'язково є найкоротшим (наприклад, з V(1,2) може бути знайдений тільки вихід W1 за 12 кроків 1-2-3-4-5-4-3-6-7-8-9-10, а

найближчий вихід W2, доступний за 7 кроків 1-2-3-6-7-13-14, знайти неможливо:

прибуття>. Дійсно, абстрактний оператор <рухатися увесь час тримаючись

60