Разделы презентаций

Розділ 2. Методи розробки алгоритмів

Содержание

2.1. Вибір методу розв'язку задачіЛітература для самостійного читання: с. 106-108 [2], с. 178-186 [4]

Слайды и текст этой презентации

Слайд 1Розділ 2. Методи розробки алгоритмів

Розділ 2. Методи розробки алгоритмів

Слайд 22.1. Вибір методу розв'язку задачі
Література для самостійного читання:
с. 106-108 [2],

с. 178-186 [4]

2.1. Вибір методу розв'язку задачіЛітература для самостійного читання: с. 106-108 [2], с. 178-186 [4]

Слайд 3 Як розробити хороший алгоритм для розв'язку задачі? З чого починати?

У кожного з нас є сумний досвід, коли дивишся на

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

Слайд 4 Метод проміжних цілей пов’язаний зі зведенням важкої задачі до послідовності

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

задачі легше піддаються обробці порівняно з початковою задачею, а також на те, що розв’язок початкової задачі може бути отриманий із розв’язків цих більш простих задач. Цей метод виглядає досить привабливо, але, як більшість загальних методів рішення задач або розробки алгоритмів, його не завжди легко перенести на конкретну задачу. Свідомий вибір більш простих задач – це скоріше мистецтво або інтуїція, ніж наука. Крім того, не існує загального набору правил для визначення класу задач, які можна розв’язати за допомогою такого підходу.
Метод проміжних цілей пов’язаний зі зведенням важкої задачі до послідовності більш простих задач. Звичайно ми сподіваємося на

Слайд 5 Приклади, що ілюструють метод проміжних цілей:
Розв’язок головоломки «Ханойські вежі»

(с.275-276 [1]).
Множення довгих цілочисельних значень (с.277-278 [1]).
Складання графіка проведення тенісного

турніру (с.279 [1]).

Приклади, що використовують динамічне програмування:
Обчислення шансів на перемогу команд в спортивних турнірах (с.281-283 [1]).
Задача триангуляції (с.283-288 [1]).
Приклади, що ілюструють метод проміжних цілей: Розв’язок головоломки «Ханойські вежі» (с.275-276 [1]).Множення довгих цілочисельних значень (с.277-278 [1]).Складання

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

який часто дозволяє уникнути дослідження всіх можливостей. Цей метод особливо

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

Слайд 7 Приклади, що ілюструють метод пошуку з поверненням:
Задача про джип

(с.109-111 [2]).
Задача про велосипедний замок (с.125 [2]).
Задача головоломка8 (пятнашки) (с.127

[2]).
Гра “хрестики-нулики” (с.291-293 [1]).
Задача комівояжера (с.296-301 [1]).


Приклади, що ілюструють метод пошуку з поверненням: Задача про джип (с.109-111 [2]).Задача про велосипедний замок (с.125 [2]).Задача

Слайд 8 Метод підйому (локального пошуку) починається з прийняття початкового припущення або

обчислення початкового розв’язку задачі. Потім починається наскільки можливо швидке пересування

вгору від початкового розв’язку у напрямку до кращих розв’язків. Коли досягаємо такої точки, з якої неможливо більше рухатися вгору, алгоритм зупиняється.
Взагалі метод підйому являється грубим. На жаль, неможливо завжди гарантувати, що остаточний розв’язок буде оптимальним. Цей «дефект» часто обмежує застосування методу.
Метод підйому може бути корисним, якщо потрібно швидко отримати наближений розв’язок.
Метод підйому (локального пошуку) починається з прийняття початкового припущення або обчислення початкового розв’язку задачі. Потім починається наскільки

Слайд 9 Приклади, що ілюструють метод підйому:
Задача знаходження мінімального остовного дерева

(с.302 [1]).
Задача комівояжера (с.303-306 [1], с.113-117 [2]).
Задача розміщення блоків (с.306-307

[1], с.120-123 [2]).
Приклади, що ілюструють метод підйому: Задача знаходження мінімального остовного дерева (с.302 [1]).Задача комівояжера (с.303-306 [1], с.113-117 [2]).Задача

Слайд 102.2. Метод проміжних цілей
Література для самостійного читання:
Метод проміжних цілей с.

276-287 [1]
Жадібні алгоритми с. 288 [1]
Евристики с. 288-291 [1],

с. 113 [2]

2.2. Метод проміжних цілейЛітература для самостійного читання:Метод проміжних цілей с. 276-287 [1] Жадібні алгоритми с. 288 [1]Евристики

Слайд 11 Метод припускає таку декомпозицію (розбиття) завдання розміру n на дрібніші

завдання, що на основі рішень цих дрібніших задач можна отримати

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

Слайд 12 Міркування над будь-якою конкретною задачею починається з постановки питань. Часткові

цілі можуть бути встановлені, коли отримано відповіді на наступні питання:
Чи

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

Слайд 13 Жадібні алгоритми
Метод внесення змін називається "жадібним" алгоритмом, якщо на кожній

окремій стадії вибирається варіант, який є локально оптимальним в тому

або іншому сенсі.
Прикладами "жадібних" алгоритмів є алгоритмом побудови найкоротшого шляху Дейкстри і алгоритмом побудови остовного дерева мінімальної вартості Краскала. Алгоритм найкоротшого шляху Дейкстри є "жадібним" в тому сенсі, що він завжди вибирає найближчу до джерела вершину серед тих, найкоротший шлях до яких ще невідомий. Алгоритм Краскала також "жадібний“: він вибирає з ребер, що залишаються і які не створюють цикл, ребро з мінімальною вартістю.
Слід підкреслити, що не кожен "жадібний" алгоритм дозволяє отримати оптимальний результат в цілому.
Жадібні алгоритми Метод внесення змін називається

Слайд 14 Приклад. Подивимося, що відбудеться, якщо в алгоритмах Дейкстри і Краскала

допустити наявність ребер з від’ємними вагами. Виявляється, що на алгоритм

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

Тепер розглядаючи ребра від s (або а) до b або c, алгоритм розраховує, що найкоротший шлях від s до b, а саме s→а→b, має довжину 3. Але далі отримуємо, що c має найкоротший шлях від s довжиною 1.
Проте "жадібний" вибір b замість c є невиправданим. Виявляється, що шлях s→а→c→b має довжину лише 2, тому обчислена раніше мінімальна відстань для b є неправильною.

Приклад. Подивимося, що відбудеться, якщо в алгоритмах Дейкстри і Краскала допустити наявність ребер з від’ємними вагами. Виявляється,

Слайд 15 Існують задачі, для яких жоден з відомих "жадібних" алгоритмів не

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

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

Слайд 16 Евристики

Евристичний алгоритм або евристика, визначається як алгоритм з наступними

властивостями:
він зазвичай знаходить хороше, хоча не обов’язково оптимальне рішення;
його

можна швидше і простіше реалізувати, ніж будь-який відомий точний алгоритм (тобто такий, що гарантує оптимальний розв’язок).

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

Слайд 17 Загальний підхід до побудови евристичних алгоритмів складається в перерахунку всіх

вимог до точного розв’язку та поділу вимог на два класи,

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

Слайд 18 Часто дуже хороші алгоритми повинні розглядатися як евристичні.
Наприклад, припустимо,

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

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

Слайд 19 Приклад. Розглянемо грубий алгоритм розв’язку задачі комівояжера, в якому задача

зведена до набору проміжних цілей – знайти на кожному кроці

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

Оптимальний розв’язок задачі комівояжера має дві основні властивості:
Він складається з множини ребер, що разом складають тур
Вартість ніякого іншого туру не буде менше даного.
Алгоритм GTS розглядає властивість 1 як обов’язкову (або легку вимогу), а властивість 2 як складну, відносно якої можна піти на компроміс.
Приклад. Розглянемо грубий алгоритм розв’язку задачі комівояжера, в якому задача зведена до набору проміжних цілей – знайти

Слайд 20Вхідні дані: кількість міст N, матриця вартостей C.
Вихідні дані: порядок

обходу міст TOUR, починаючи з міста U, з найменшою вартістю

MIN.
Вхідні дані: кількість міст N, матриця вартостей C.Вихідні дані: порядок обходу міст TOUR, починаючи з міста U,

Слайд 212
1
5
3
4
вартість 0

21534вартість 0

Слайд 222
1
5
3
4
вартість 1

21534вартість 1

Слайд 232
1
5
3
4
вартість 4

21534вартість 4

Слайд 242
1
5
3
4
вартість 6

21534вартість 6

Слайд 252
1
5
3
4
вартість 7

21534вартість 7

Слайд 262
1
5
3
4
вартість 14
Алгоритм GTS дає тур з вартістю 14, а точний

алгоритм ETS, розглянутий раніше, знайшов тур вартістю 13.

21534вартість 14Алгоритм GTS дає тур з вартістю 14, а точний алгоритм ETS, розглянутий раніше, знайшов тур вартістю

Слайд 27 Звичайно, для алгоритму GTS легко написати програму, але чи є

він швидким? Для довільної задачі комівояжера з n містами потрібно

O(n2) операцій, щоб прочитати або побудувати матрицю вартостей C. Тому нижня границя складності будь-якого алгоритму, здібного дати нетривіальний можливий розв’язок цієї задачі, дорівнює O(n2). Неважко перевірити, що для будь-якої розумної реалізації кроків 1-3 потрібно не більше ніж O(n2) операцій. Тому алгоритм GTS настільки швидкий, наскільки можливо.
Мабуть алгоритм GTS – це хороший евристичний алгоритм. Звичайно поняття хороший – відносне. Оскільки алгоритм ЕТS занадто не ефективний, визначення “хороший” може просто вказувати на той факт, що алгоритм GTS - найкращий серед наявних для великих (в розумних межах) значень n.
Звичайно, для алгоритму GTS легко написати програму, але чи є він швидким? Для довільної задачі комівояжера з

Слайд 28 Якість алгоритму GTS може бути значно покращена простою модифікацією. Найгіршою

властивістю алгоритму є те, що вибір ребер дуже низької вартості

при виконанні кроку 1 на ранніх та середніх стадіях роботи алгоритму може призвести до вибору дуже дорогих ребер в заключній стадії. Один із способів запобігти цьому – застосовувати алгоритм для кожного із p≤n різних, випадково вибраних, початкових міст. Інша модифікація може складатися в повторенні алгоритму для того ж самого початкового міста, але треба починати з другого за вартістю ребра і потім, можливо, повернутися до проходження найдешевших ребер для наступних вершин. Можливі інші варіації. Потім можна вибрати найменший із розглянутих турів, або зберігати тільки найдешевший тур із знайдених на даний момент і відкидати частково побудовані тури, вартості яких вже перевищують вартість поточного найдешевшого тура. Звичайно складність модифікованого алгоритму GTS2 може досягати порядку O(pn2).
Якість алгоритму GTS може бути значно покращена простою модифікацією. Найгіршою властивістю алгоритму є те, що вибір ребер

Слайд 29 Алгоритм GTS2 (грубий комівояжер версія 2).
Створити тури з 1≤P≤N різних

початкових міст для задачі комівояжера з N містами. Послідовно будуються

P турів і запам’ятовується кращий з них на поточний момент.
Вхідні дані: кількість всіх міст N; кількість початкових міст P; матриця вартостей C; список P початкових міст {V1, V2, …,VP}.
Алгоритм GTS2 (грубий комівояжер версія 2). Створити тури з 1≤P≤N різних початкових міст для задачі комівояжера з N

Слайд 30 Приклади, що ілюструють евристичні алгоритми:
Ще один варіант розв’язку задачі

комівояжера (с.297 [1]).
Приклад евристичного алгоритму про навантаження набору процесорів (мінімізація

часу роботи) з оцінками ресурсоємності (с.117 [2])
Приклад евристичного алгоритму про навантаження набору процесорів (мінімізація кількості процесорів) з оцінками ресурсоємності (с.120 [2])
Приклади, що ілюструють евристичні алгоритми: Ще один варіант розв’язку задачі комівояжера (с.297 [1]).Приклад евристичного алгоритму про навантаження

Слайд 312.3. Метод пошуку з поверненням
Література для самостійного читання:
с. 291-301 [1]

2.3. Метод пошуку з поверненнямЛітература для самостійного читання: с. 291-301 [1]

Слайд 32 Іноді доводиться мати справу із завданням пошуку оптимального рішення, коли

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

варіант рішення, і залишається вдатися до останнього засобу - повного перебору.

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

Слайд 33 Гравці по черзі роблять ходи, і стан гри відображається відповідним

положенням на дошці. Допустимо, що є кінцеве число позицій на

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

Слайд 35 Листки дерева відповідають таким позиціям на дошці, з яких неможна

зробити хід, - чи то тому, що хтось з гравців

вже отримав перемогу, чи то тому, що всі клітки заповнені і гра закінчилася внічию. Кожному вузлу дерева відповідає певна ціна. Спочатку призначаються ціни листкам. Листу призначається ціна -1, 0 або 1 залежно від того, чи відповідає даній позиції програш, нічия або виграш гравця 1 (який ставить "хрестики").
Ціни розповсюджуються вгору по дереву відповідно до наступного правила. Якщо який-небудь вузол відповідає такій позиції, з якої повинен зробити хід гравець 1, тоді відповідна ціна є максимальною серед цін нащадків даного вузла (при цьому припускаємо, що гравець 1 зробить найвигідніший для себе хід). Якщо ж вузол відповідає ходу гравця 2, тоді відповідна ціна є мінімальною серед цін нащадків даного вузла (при цьому припускаємо, що гравець 2 також зробить самий вигідний для себе хід, тобто такий, який при найсприятливішому результаті приведе до програшу гравця 1, а при менш переважному результаті - до нічиєї).
Листки дерева відповідають таким позиціям на дошці, з яких неможна зробити хід, - чи то тому, що

Слайд 36 Ідею дерева гри, вузли якого мають ціну -1, 0 або

1, можна узагальнити на дерева, листкам яких присвоюються будь-які числа

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

Слайд 37 Приклад. Реалізація пошуку з поверненням.
Рекурсивна програма search (пошук) виконує обхід

дерева за допомогою послідовності рекурсивних викликів. Ця програма припускає виконання

наступних умов:
1. Виграші є дійсними числами з кінцевого інтервалу, наприклад від -1 до +1.
2. Константа ∞ більше, ніж будь-який позитивний виграш, а -∞ менше, ніж будь-який негативний виграш.
3. Тип даних modetype (тип режиму) визначається таким чином:
type modetype = (MIN, MAX)
4. Передбачено тип даних boardtype (тип ігрової дошки), який визначається способом, відповідним для представлення позицій на ігровій дошці.
5. Передбачено функцію payoff (виграш), яка обчислює виграш для будь-якої позиції, яка є листом.
Приклад. Реалізація пошуку з поверненням. Рекурсивна програма search (пошук) виконує обхід дерева за допомогою послідовності рекурсивних викликів. Ця

Слайд 38function search (B: boardtype; mode: modetype): real;
{оцінює і повертає

виграш для позиції B в припущенні, що наступним повинен ходити

гравець 1 (mode = МАХ) або гравець 2 (mode = MIN)}
var C: boardtype; { син позиції В }
value: real; {для тимчасового зберігання мінімального або максимального значення}
begin
if В є листом
then return(payoff(В))
else begin
if mode = MAX
then value:= -∞
else value: = ∞;
for для кожного сина C позиції В do
if mode = MAX
then value:= max(value, search(C, MIN))
else value:= min(value, search(C, MAX));
return(value);
end;
end; { search }
function search (B: boardtype; mode: modetype): real; {оцінює і повертає виграш для позиції B в припущенні, що

Слайд 39 Метод гілок і границь
Алгоритми, що базуються на методі пошуку

з поверненнями, спрямовані на знаходження однієї або всіх конфігурацій, що

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

Слайд 40 При розгляді задач, в яких дерево розв'язку, будучи, в принципі

кінцевим, настільки велике, що будь-які спроби оцінити його по методу

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

Слайд 41 Як приклад, де зручно застосувати концепцію виграшів, розглянемо складну гру

(наприклад, шахи). Будь-які шахові програми діють, по суті, шляхом побудови

для кожної проміжної позиції на шахівниці дерева гри. Коренем цього дерева є поточна позиція; гілки від кореня розповсюджується вниз на декілька рівнів. Точна кількість рівнів залежить від швидкодії конкретного комп'ютера. Коли більшість листків дерева проявляють "неоднозначність" (тобто не ведуть ні до виграшу, ні до нічиєї, ні до програшу), кожна програма використовує певну функцію позицій на дошці, яка намагається оцінити вірогідність виграшу комп'ютера в цій позиції. Наприклад, на таку оцінку в значній мірі впливає наявність у однієї із сторін матеріальної переваги і такі чинники, як міцність захисту королів. Використовуючи подібну функцію виграшу комп'ютер може оцінити вірогідність виграшу після виконання ним кожного з можливих чергових ходів і вибрати хід з найвищим виграшем.
Як приклад, де зручно застосувати концепцію виграшів, розглянемо складну гру (наприклад, шахи). Будь-які шахові програми діють, по

Слайд 42 Ряд правил, відповідно до яких діють хороші шахові програми:
1.

Використання евристик, щоб виключити з розгляду певні ходи, які навряд

чи можна вважати хорошими. Це допомагає збільшити кількість рівнів дерева, що переглядаються за фіксований час.
2. Розповсюдження "ланцюжків взяття", які є послідовностями ходів, що супроводжуються взяттям фігур супротивника, за межі останнього рівня, до якого зазвичай розповсюджується дерево. Це допомагає точніше оцінити відносну матеріальну силу позицій.
3. Скорочення пошуку на дереві методом альфа-бета відсікання.
Ряд правил, відповідно до яких діють хороші шахові програми: 1. Використання евристик, щоб виключити з розгляду певні

Слайд 43 Альфа-бета відсікання
Цикл перебору нащадків вузла можна організувати так, щоб він

проігнорував певних синів - нерідко досить велике їх число. Припустимо,

розглядаємо вузол n, і вже визначили, що ціна c1 першого з синів вузла n дорівнює 20.
Альфа-бета відсікання Цикл перебору нащадків вузла можна організувати так, щоб він проігнорував певних синів - нерідко досить велике

Слайд 44 Оскільки вузол n знаходиться в режимі МАХ (тобто хід 1-го

гравця), то його значення не менше 20. Допустимо тепер, що,

продовжуючи пошук, знайшли, що у сина с2 є нащадок d з виграшем 15. Оскільки вузол с2 знаходиться в режимі MIN (тобто хід 2-го гравця), то значення вузла с2 не може бути більше 15. Таким чином, яке б не було значення вузла с2, воно не може впливати на ціну вузла n і будь-якого предка вузла n. Таким чином, можна проігнорувати розгляд тих нащадків вузла с2, які ще не розглядалися.
Оскільки вузол n знаходиться в режимі МАХ (тобто хід 1-го гравця), то його значення не менше 20.

Слайд 45 Загальне правило пропуску або "відсікання" вузлів пов'язано з поняттям кінцевих

і орієнтовних значень для вузлів. Кінцеве значення - це те,

що просто називаємо "значенням" (виграшем). Орієнтовне значення - це верхня межа значень вузлів в режимі MIN або нижня межа значень вузлів в режимі МАХ.

Правила обчислення кінцевих і орієнтовних значень.
1. Якщо вже розглянули або відсікли всіх нащадків вузла n, зробити орієнтовне значення вузла n кінцевим значенням.
Загальне правило пропуску або

Слайд 462. Якщо орієнтовне значення вузла n в режимі МАХ рівне

v1, а кінцеве значення одного з його нащадків дорівнює v2,

тоді встановити орієнтовне значення вузла n рівним max(v1,v2). Якщо ж вузол n знаходиться в режимі MIN, тоді орієнтовне значення вузла n встановити рівним min(v1,v2).
3. Якщо р є вузлом в режимі MIN, має батька q (у режимі МАХ), а орієнтовне значення вузлів р і q дорівнюють v1 і v2 відповідно, причому v1≤v2, тоді можна відсікти всіх нерозглянутих нащадків вузла р. Можна також відсікти нерозглянутих нащадків вузла р, якщо р є вузлом в режимі МАХ, а q є, таким чином, вузлом в режимі MIN, і v2≤v1.
2. Якщо орієнтовне значення вузла n в режимі МАХ рівне v1, а кінцеве значення одного з його

Слайд 47 Приклад. Використання альфа-бета відсікання.
Розглянемо дерево, показане на малюнку. Вважаючи, що

значення листків відповідають значенням, вказаним на малюнку, хочемо обчислити значення

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

Слайд 48 Починаємо обхід дерева в зворотному порядку. Досягнувши вузла D, у

відповідності з правилом (2) призначаємо вузлу C орієнтовне значення 2,

яке являється кінцевим значення вузла D. Проглядаємо вузол Е і повертаємося у вузол C, а потім переходимо у вузол В. Відповідно до правила (1) кінцеве значення вузла C дорівнює 2, орієнтовне значення вузла В - 2. Обхід далі продовжується вниз до вузла G, а потім назад у вузол F. Орієнтовне значення вузла F рівне 6. У відповідності з правилом (3) можна відсікти вузол Н, оскільки орієнтовне значення вузла F зменшитися не може і воно вже більше значення вузла В, яке не може збільшитися.
Починаємо обхід дерева в зворотному порядку. Досягнувши вузла D, у відповідності з правилом (2) призначаємо вузлу C

Слайд 49 Для вузла А призначаємо орієнтовне значення 2 і переходимо до

вузла К. Для вузла J призначається орієнтовне значення 8. Значення

вузла L не впливає на значення вузла J. Для вузла I призначається орієнтовне значення 8. Переходимо у вузол N, вузлу М призначається орієнтовне значення 5. Необхідно виконати перегляд вузла О, оскільки 5 (орієнтовне значення вузла М) менше, ніж орієнтовне значення вузла I. Далі переглядаються орієнтовні значення вузлів I і А. Переходимо до вузла R. Виконується перегляд вузлів R і S, вузлу Р призначається орієнтовне значення 4. Перегляд вузла Т і всіх його нащадків проводити не потрібно, оскільки це може тільки знизити значення вузла Р, яке вже і без того дуже низьке, щоб вплинути на значення вузла А.
Для вузла А призначаємо орієнтовне значення 2 і переходимо до вузла К. Для вузла J призначається орієнтовне

Слайд 50 Приклади, що ілюструють метод гілок та границь для задачі комівояжера

:

алгоритм Литла, Мерті, Суіні і Карела (с. 131-144 [2])
алгоритм,

що використовує альфа-бета відсікання (с.296-301 [1]).
Приклади, що ілюструють метод гілок та границь для задачі комівояжера : алгоритм Литла, Мерті, Суіні і Карела

Слайд 512.4. Метод підйому (локального пошуку)
Література для самостійного читання:
с. 302-308 [1]

2.4. Метод підйому (локального пошуку)Література для самостійного читання: с. 302-308 [1]

Слайд 52 Алгоритми локального пошуку проявляють себе з якнайкращого боку як евристичні

алгоритми для вирішення задач, точні рішення яких вимагають експоненційних витрат

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

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

Слайд 53 Цей метод має сенс лише у тому випадку, коли можемо

обмежити сукупність перетворень невеликою її підмножиною, що дає можливість виконати

всі перетворення за відносно короткий час: якщо "розмір" задачі дорівнює n, то доцільно використати O(n2) або O(n3) перетворень. Якщо сукупність перетворень невелика, природно розглядати рішення, які можна перетворювати одне в інше за один крок, як "близькі". Такі претворення називаються "локальними", а відповідний метод називається локальним пошуком.
Цей метод має сенс лише у тому випадку, коли можемо обмежити сукупність перетворень невеликою її підмножиною, що

Слайд 54 На основі більшості (або навіть всіх) довільних початкових рішень нерідко

отримуватимемо різні локально-оптимальні рішення. На практиці можемо і не знайти

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

Слайд 55 Приклад. Задача знаходження мінімального остовного дерева методом локального пошуку.

Локальне

перетворення: беремо те або інше ребро, що не відноситься до

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

Слайд 57 Приклад. Задача комівояжера методом локального пошуку.
Простим перетворенням, яким можна

в цьому випадку скористатися, є так званий "подвійний вибір". Він

полягає в тому, що вибираємо будь-які два ребра, наприклад ребра (А,В) і (С,D), видаляємо їх і "перекомутуємо" крапки, що з'єднувалися ними, так, щоб утворився новий маршрут. Якщо сума довжин (А,С) і (В,D) виявляється менше суми довжин (А,В) і (С,D), то вдалося отримати покращений маршрут.
Приклад. Задача комівояжера методом локального пошуку. Простим перетворенням, яким можна в цьому випадку скористатися, є так званий

Слайд 592.5. Структурне програмування згори-вниз
Література для самостійного читання:
Опис методики с. 30-47 [2],


с. 106 [2],
с. 178-186 [4]
Приклад використання методики
для розв’язку

задачі «Тур коня» с. 36-44 [2]
2.5. Структурне програмування згори-внизЛітература для самостійного читання:Опис методики с. 30-47 [2], с. 106 [2], с. 178-186 [4]Приклад використання

Слайд 60 На сьогодні найпопулярнішою методикою раціональної розробки реалізацій алгоритмів можна вважати

структурне програмування згори-вниз (або низхідне проектування).

Методологія структурного програмування — це

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

Методологія структурного програмування ґрунтується на трьох методах: низхідного проектування, модульного програмування і структурування програм.

На сьогодні найпопулярнішою методикою раціональної розробки реалізацій алгоритмів можна вважати структурне програмування згори-вниз (або низхідне проектування). Методологія структурного

Слайд 61 Низхідне проектування програм

В основу методу низхідного проектування покладено алгоритмічну декомпозицію,

згідно з якою велика задача поділяється на дрібніші підзадачі, що

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

Слайд 62 Програма, що розв'язує загальну задачу, спочатку розглядається як незалежний модуль.

Згодом вона поділяється на підпрограми, які декомпонуються на підмодулі наступного

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

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

Слайд 63 Абстрагування — це спрощений опис системи, в якому зосереджують увагу

на певних властивостях і деталях, а на інші не зважають.



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

Слайд 64 Специфікація інтерфейсів — це формалізований опис входів, виходів і функцій,

що мають бути реалізовані програмним модулем.

Коли інтерфейс модуля специфіковано,

можна спробувати в явному вигляді записати його код. Якщо це зробити неможливо, модуль поділяють на певну кількість невеликих підмодулів. Коли модуль не можна ані закодувати, ані декомпонувати, його вважають модулем-заглушкою, інтерфейс якого відомий, а реалізація — ні.

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

Слайд 65 Одним із прийомів формалізованого підходу до низхідного проектування є метод

ієрархічних діаграм, що позначається абревіатурою НІРО (від англ. Hierarchical Input

Processing Output — діаграма входу, обробки, виходу). Згідно з цим методом структура всієї програми подається у вигляді дерева, в якому підпрограми зображуються вузлами, а їхні виклики — ребрами.
Одним із прийомів формалізованого підходу до низхідного проектування є метод ієрархічних діаграм, що позначається абревіатурою НІРО (від

Слайд 66 Модульне програмування

Модульне програмування — це організація програми у вигляді сукупності

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

блоки називаються модулями.

Модульне програмування дає можливість:
спростити процес тестування і налагодження програми;
розробити програму зусиллями більше ніж одного програміста;
локалізувати дію змін і доповнень до програми в межах одного модуля;
скоротити термін і вартість розробки програми.
Модульне програмування Модульне програмування — це організація програми у вигляді сукупності незалежних блоків, структура і функції яких підпорядковуються

Слайд 67 Програму можна вважати модульною, якщо її логічна і фізична структура

відповідає таким умовам:

модулі є незалежними програмними блоками, код яких логічно

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

Слайд 68 Незалежність модулів є визначальним принципом модульного програмування. Це означає, що

програма має бути поділена на модулі таким чином, щоб зв'язки

між модулями були слабкими, а зв'язки всередині модулів — сильними.
Модулі можуть вважатися незалежними, якщо вони задовольняють таким вимогам:
кожен модуль можна замінити іншим функціонально еквівалентним модулем, що має той самий інтерфейс;
взаємозв'язки між модулями встановлені за ієрархічним принципом;
усі структури даних інкапсульовані в модулі, тобто доступ до даних може здійснюватися лише через процедури та функції модуля;
модуль має одну точку входу та одну точку виходу;
модуль повертає керування тому програмному блоку, що його викликав.
Незалежність модулів є визначальним принципом модульного програмування. Це означає, що програма має бути поділена на модулі таким

Слайд 69 Методи структурування програм

Методи низхідного проектування та модульного програмування регламентують процес

побудови архітектури програм на макрорівні. Методи структурування, навпаки, працюють на

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

Слайд 70 Методи структурування ґрунтуються на поняттях функціонального вузла, а також на

поняттях простої, елементарної і складеної програми.
Функціональним вузлом називається частина алгоритму,

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

Слайд 71 Елементарна програма — це проста програма, що не містить підпрограм,

які складаються більше ніж з одного вузла. Існує обмежена кількість

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

Слайд 72 Якщо функціональний вузол елементарної програми замінити елементарною програмою, утвориться складена

програма.
Якщо вузол складеної програми замінити елементарною програмою, знов утвориться

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

Слайд 73 Покрокове перетворення програми на структуровану здійснюється за такими правилами.

Правило простоти:

створення програми слід починати із простої програми;
Правило пакетування: кожну дію

можна замінити двома послідовними діями;
Правило вкладання — кожну дію можна замінити будь-якою структурою керування;
Правила 2 і 3 можна застосовувати у будь-якій послідовності необмежену кількість разів.
Покрокове перетворення програми на структуровану здійснюється за такими правилами.Правило простоти: створення програми слід починати із простої програми;Правило

Слайд 74 Приклад. Принцип застосування правил пакетування та вкладання до простої програми

Приклад. Принцип застосування правил пакетування та вкладання до простої програми

Слайд 75 Для перетворення неструктурованих програм у структуровані використовуються такі методи:
дублювання

кодів
введення змінної стану
метод булевих ознак.

Метод дублювання кодів застосовується

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

Слайд 76 Приклад. Процес перетворення неструктурованої програми у структуровану; дублювання кодів.

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

Слайд 77 Метод введення змінної стану застосовується до неструктурованих програм, що містять

цикли. Процес перетворення неструктурованої програми у структуровану складається з таких

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

Слайд 78 Приклад. Процес перетворення неструктурованої програми у структуровану; введення змінної стану.

Приклад. Процес перетворення неструктурованої програми у структуровану; введення змінної стану.

Слайд 79 Метод булевої ознаки використовується для перетворення неструктурованих програм, що містять

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

чи false. Доки змінна ознаки зберігає це значення, виконання циклу триває. Значення змінної ознаки всередині циклу модифікується лише за певних умов.
Метод булевої ознаки використовується для перетворення неструктурованих програм, що містять цикли. В програму вводиться додаткова змінна, яка

Слайд 80 Приклад. Процес перетворення неструктурованої програми у структуровану; метод булевої ознаки.

Приклад. Процес перетворення неструктурованої програми у структуровану; метод булевої ознаки.

Слайд 81 Домашнє завдання

Прочитати c.276-306 [1], c.113-145 [2]

Підготуватися до виконання практичної

роботи №2.

Домашнє завдання Прочитати c.276-306 [1], c.113-145 [2] Підготуватися до виконання практичної роботи №2.

Похожие презентации

Композиция и структура сочинения Композиция и структура сочинения 255
Школа ЗОЖ Школа ЗОЖ 176
"На поляне Лукоморья" 296
Квест – игра Летнее приключение Квест – игра Летнее приключение 205
Урок 8: РЕАНИМАЦИЯ МЛАДЕНЦЕВ РОЖДЕННЫХ ПРЕЖДЕВРЕМЕННО Neonatal Resuscitation Урок 8: РЕАНИМАЦИЯ МЛАДЕНЦЕВ РОЖДЕННЫХ ПРЕЖДЕВРЕМЕННО Neonatal Resuscitation 223
Healthy & unhealthy food Healthy & unhealthy food 309
Региональный Круглый стол ОБРАЗОВАНИЕ И ЗДОРОВЬЕ ГАУ ДПО СОИРО, 25 октября Региональный Круглый стол ОБРАЗОВАНИЕ И ЗДОРОВЬЕ ГАУ ДПО СОИРО, 25 октября 213
What is Web of Science? Impact factor - is the average citations per ARTICLES What is Web of Science? Impact factor - is the average citations per ARTICLES 221
Гуситское движение в Чехии § 25 Начать урок Гуситское движение в Чехии § 25 Начать урок 151
ДОБРО ДОБРО 419
Оподаткування суб’єктів малого підприємництва Оподаткування суб’єктів малого підприємництва 214
Christmas and New Year Christmas and New Year 176
Сквернословие Сквернословие 244
Энергия магнитного поля Энергия магнитного поля 262
Лекция 5 Лекция 5 197
LIMITED EDITION LIMITED EDITION 184
Применение информационно-коммуникативных технологий на занятиях по развитию речи Применение информационно-коммуникативных технологий на занятиях по развитию речи 183
СОЗНАНИЕ – его происхождение и сущность СОЗНАНИЕ – его происхождение и сущность 338
Современные проблемы науки в области защиты окружающей среды Современные проблемы науки в области защиты окружающей среды 193
Метод проекта в обучении русскому языку Презентацию выполнила: Борисова А.С., Метод проекта в обучении русскому языку Презентацию выполнила: Борисова А.С., 211

Обратная связь

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.

Для правообладателей

Яндекс.Метрика