Алгоритми і структури даних Опорний конспект лекцій для студентів заочно-дистанційної форми навчання спеціальності „Економічна кібернетика”



Сторінка19/19
Дата конвертації20.11.2016
Розмір1.02 Mb.
1   ...   11   12   13   14   15   16   17   18   19

11.5.Програмування з поверненнями назад


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

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

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

Листки цього дерева відповідають таким позиціям на дошці, з яких неможливо виконати хід, – або тому, що хтось з гравців вже отримав перемогу, або тому, що усі можливі ходи вже вичерпані. Кожному вузлу дерева відповідає певна ціна. На початку назначають ціни листкам. Нехай мова йде про гру „хрестики-нулики”. В такому випадку листкам назначається ціна -1, 0 і 1 в залежності від того, чи відповідає даній позиції програш, нічия або виграш.

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

Цей алгоритм покажемо на прикладі задачі, яка має назву „хід коня”.

На шахівниці nхn стоїть на полі (x, y) шаховий кінь. Слід знайти такий маршрут коня (який ходить згідно шахових правил), коли він обходить усю шахівницю, побувавши у кожній клітинці рівно один раз.

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

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

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

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


  1. Виграші є дійсними числами з обмеженого інтервалу, наприклад [-1, 1].

  2. Константа  більша, ніж будь-який додатній виграш, а - менша, ніж будь-який від’ємний виграш.

  3. Дані типу modetype (тип режиму) можуть приймати два фіксовані значення – MIN, або MAX.

  4. Передбачений тип даних boardtype (тип ігрової дошки), яка визначається способом представлення позицій на дошці.

  5. Передбачена функція payoff (виграш), яка обчислює виграш для будь-якої позиції, яка є листком дерева.

Одна дуже проста умова дозволяє позбавитися від розгляду значної частини типового дерева гри.

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



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

  2. Якщо орієнтовне значення вузла в режимі MAX рівне v1, а кінцеве значення одного з його нащадків рівне v2, тоді встановити приблизне значення вузла рівним max(v1,v2). Якщо вузол знаходиться в режимі MIN – min(v1,v2).

  3. Якщо p є вузлом в режимі MAX, і має батька q, а приблизні значення вузлів рівні v1 і v2, відповідно, причому v1<v2, тоді можна відсікти всіх нерозглянутих нащадків вузла p, якщо p є вузлом в режимі MAX, а q є, таким чином в режимі MIN, і v2<v1.

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

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

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

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

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

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

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

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

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

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

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

11.6.Евристичні алгоритми


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

Наприклад, в шахах звичайною евристикою є „посилення переваги”. Якщо у супротивника менше сильних фігур і однакова кількість інших, то слід йти на розмін при кожній нагоді. Зменшення кількості фігур робить дерево рішень коротшим і може збільшити відносну перевагу. Ця стратегія не гарантує виграшу, але підвищує його вірогідність.

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

Якщо якість рішення не так важлива, то прийнятним може бути результат, отриманий за допомогою евристики. В деяких випадках точність вхідних даних може бути недостатньою. Тоді хороше евристичне рішення може бути таким же правильним, як і теоретично „якнайкраще рішення”.

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

Отже, евристичні алгоритми – це алгоритми, які мають такі властивості:



  • Вони дозволяють знайти добрі, хоча і не завжди найкращі розв’язки з усіх, що існують.

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

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

У цьому розумінні усі умови, що висуваються до розв’язку, звичайно ділять на дві групи щодо витрат праці:



  • ті, які легко задовольнити;

  • ті, що вимагають великої роботи.

З іншої сторони, вони поділяються на такі групи щодо їхньої важливості для кінцевої якості:

  • ті, які обов’язково слід задовольнити;

  • ті, що можуть бути послаблені або змінені.

Цю ситуацію образно показано в таблиці



1

2

a

Слід задовольнити

?

b

?

Варто відмовитися

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

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

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

Частіше за все евристичні алгоритми базуються на методі сходження або на методі частинних цілей.


11.7.Імовірнісні алгоритми


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

Серед усієї гами цих алгоритмів розглянемо лише один для прикладу - обчислення площі фігури методом Монте-Карло.

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

,

то S ділить Q на долі пропорційно



Якщо за допомогою датчика випадкових чисел генерувати точки , які б рівномірно заповнювали прямокутник Q, то кількість тих точок, що потраплять усередину області S, та тих, що потраплять за її межі, буде відноситися приблизно так само



тоді

Кількість NS та NQ підраховуються під час експерименту.

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

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



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

Контрольні запитання


  1. Структурування алгоритмів.

  2. Структурування даних.

  3. Інкапсуляція, як засіб структуризації.

  4. Концепція структур даних.

  5. Класифікація структур даних.

  6. Базові операції над структурами даних.

  7. Дані арифметичного типу.

  8. Дані перерахованого типу.

  9. Властивості статичних структур даних.

  10. Масив, як структура даних

  11. Розріджені масиви.

  12. Множина, як структура даних.

  13. Структурний тип даних.

  14. Об’єднання, як структура даних.

  15. Бітовий тип даних.

  16. Таблиця, як структура даних.

  17. Особливості напівстатичних структур даних.

  18. Стек, як структура даних.

  19. Черга, як структура даних.

  20. Дек, як структура даних.

  21. Лінійні списки.

  22. Однонаправлений лінійний список.

  23. Двонаправлений лінійний список.

  24. Основні поняття мультисписків.

  25. Стрічка, як структура даних.

  26. Зв’язне представлення даних.

  27. Представлення графа, як структури даних.

  28. Дерево, як структура даних.

  29. Алгоритм перетворення дерева в бінарне.

  30. Представлення дерев в пам’яті.

  31. Операції над деревами.

  32. Алгоритми обходу дерева.

  33. Принципи формалізації алгоритмів.

  34. Покрокове проектування алгоритмів.

  35. Основні характеристики алгоритмів.

  36. Поняття складності алгоритму.

  37. Ефективність алгоритмів.

  38. Правила аналізу складності алгоритмів.

  39. Постановка задачі сортування.

  40. Класифікація алгоритмів сортування.

  41. Сортування вибіркою.

  42. Сортування включенням.

  43. Сортування розподілом.

  44. Сортування злиттям.

  45. Принципи рандомізації.

  46. Постановка задачі пошуку.

  47. Послідовний пошук.

  48. Бінарний пошук.

  49. Пошук методом інтерполяції.

  50. Пошук методом „золотого перерізу”.

  51. Алгоритми пошуку послідовностей.

  52. Хешування даних.

  53. Алгоритми розв’язання колізій при хешуванні.

  54. Організація даних для пошуку.

  55. Метод часткових цілей.

  56. Метод динамічного програмування.

  57. Метод сходження.

  58. Дерева розв’язків.

  59. Програмування з поверненням назад.

  60. Евристичні алгоритми.

  61. Імовірнісні алгоритми.




Список рекомендованої літератури


1. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы – М.: Изд. Дом «Вильямс», 2001. – 384с.

2. Браунси К. Основные концепции структур данных и реализация в С++. – М.: Изд. Дом «Вильямс», 2002. – 320с.

3. Проценко В.С. Техніка програмування мовою Сі: Навчальний посібник – К.: Либідь, 1993. – 224 с.

4. Шилдт Г. Теория и практика С++ – СПб.: BHV – Санкт-Питербург, 1996. – 416 с.

5. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: «Мир», 1979. - 536с.

6. Вирт Н. Алгоритмы + структуры данных = программы. - М.: "Мир", 1985. - 544 с.

7. Гудман С. Хидетниеми С. Введение в разработку и анализ алгоритмов. - М.: "Мир", 1981. - 366 с.

8. Кнут Д. Искусство программирования для ЭВМ. т.3. Сортировка и поиск. М.:Мир, 1976. - 678 с.

9. Мейер Б., Бодуэн К. Методы программирования: В 2-х томах – М.: Мир, 1982. – 356+368с.

Зміст


ВСТУП 3

1. АЛГОРИТМИ і дані 4

2. ПРОСТІ СТРУКТУРИ ДАНИХ 8

3. СТАТИЧНІ СТРУКТУРИ ДАНИХ 9

4. НАПІВСТАТИЧНІ СТРУКТУРИ ДАНИХ 14

5. ДИНАМІЧНІ СТРУКТУРИ ДАНИХ 25

6. НЕЛІНІЙНІ СТРУКТУРИ ДАНИХ 26

7. Побудова і аналіз алгоритмів 30

8. Алгоритми сортування 35

9. АЛГОРИТМИ пошуку 42

10. Методи швидкого доступу до даних 45

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

Контрольні запитання 62

Список рекомендованої літератури 63

Зміст 64






1   ...   11   12   13   14   15   16   17   18   19


База даних захищена авторським правом ©lecture.in.ua 2016
звернутися до адміністрації

    Головна сторінка