Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Що таке алгоритм. Означення алгоритму. Приклади алгоритмів
Алгоритм - це будь-яка коректно визначена обчислювальна процедура, на вхід якої подається деяка величина або набір величин, і результатом виконання якої є вихідне значення або набір значень.Алгоритм можна також розглядувати як інструмент, призначений для вирішення коректно поставленої обчислювальної задачі
1. ввести значення числа a
2. ввести значення числа b
3. обрахувати значення числа c за формулою с=a+b
4. вивести значення числа с
Алгоритм. Його властивості
Алгоритм - це будь-яка коректно визначена обчислювальна процедура, на вхід якої подається деяка величина або набір величин, і результатом виконання якої є вихідне значення або набір значень.Алгоритм можна також розглядувати як інструмент, призначений для вирішення коректно поставленої обчислювальної задачі /
– детермінованість (визначеність) – завдяки використанню повністю однозначних правил та дій при створені алгоритму, його застосування до однакових вхідних даних повинно приводити до отримання однакового результату (кожен крок алгоритму має інтерпретуватися виконавцем однозначно);
– дискретність – процес, що описується алгоритмом, можна розділити на окремі елементарні етапи, кожен з яких називається кроком алгоритму;
– ефективність – під час розв’язання задачі, алгоритмом може використовуватися лише обмежений обсяг комп’ютерних ресурсів і результат повинен бути досягнутий за певний ліміт часу;
– масовість –алгоритм повинен бути придатним для розв’язування всіх задач певного типу.
– результативність – обчислювальний процес, що реалізується за наданим алгоритмом, повинен через скінчену кількість етапів (кроків) зупинитись і надати результат, що відповідає заданим вхідним даним, або ж повідомити про неможливість розв’язання даного екземпляру задачі
Алгоритм. Способи запису алгоритмів
Алгоритм - це будь-яка коректно визначена обчислювальна процедура, на вхід якої подається деяка величина або набір величин, і результатом виконання якої є вихідне значення або набір значень.Алгоритм можна також розглядувати як інструмент, призначений для вирішення коректно поставленої обчислювальної задачі .
– вербальна – алгоритм описується при допомозі звичайної
– символьна – алгоритм описується при допомозі певного набору символів
– графічна –при допомозі блок-схем
Опис алгоритмів при допомозі блок-схем
Етапи повної побудови алгоритму
Постановка задачі..побудова моделі..розробка алгоритму..перевірка правильності алгоритму..реалізувати алгоритм..аналіз алгоритму та його складності..перевірити програму.. аналіз алгоритму та його складності..перевірити програму..інструкція .
Етапи постановки задачі та побудови моделі
1)які моделі підходять для цієї задачі.2)чи існують вже вирішення аналог задач ……1)чи вся вхідна інформ. Добре описана.2)чи існує матем величина асоційована з результатом..3)чи існують якісь корисні відношення в рамках цієї моделі..
Етапи розробки та перевірки правильності алгоритму
Вибір методу розробки, як правило, сильно залежить від вибору моделі, і може в значній мірі впливати на ефективність алгоритму розвязку. Два різних алгоритму можуть бути вірними, але дуже сильно відрізнятися по ефективності.Загальною методикою доведення правильності алгоритму є його опис у вигляді послідовності кроків, наприклад від 0 до m і знаходження деякої правомірності для кожного такого кроку. Далі намагаються надати докази скінченності алгоритму, при цьому розглядаються усі варіанти вхідних даних і отримання всіх підходящих вихідних даних.
Класифікація мов програмування
Мови програмування високого рівня оперують сутностями ближчими людині, такими як об'єкти, змінні, функції. Мови програмування нижчого рівня оперують сутностями ближчими машині: байти, адреси, інструкції. Текст програми на мові високого рівня зазвичай набагато коротший ніж текст такої самої програми на мові низького рівня, проте програма має більший розмір.
Універсальні та спеціалізовані.
Об'єктно-орієнтовані, логічні, функційні, структурні…
Поняття програми. Час виконання програми
Програма — передбачений хід подій у часі та порядок правил, що повинні застосуватись для проведення запланованого. Технічні програми обмежені у своєму виконанні та реагують на непередбачувані події лише в рамках запрограмованого.
На час виконання програми впливають наступні чинники.
1. Введення початкової інформації в програму.2. Якість скомпільованого коду виконуваної програми.3. Машинні інструкції (звичайні і спеціальні), використовувані для виконання програми.4. Часова складність алгоритму відповідної програми.
Метрика часу виконання програми
Асимптотичні співвідношення як метод аналізу якості алгоритму
На практиці для опису швидкості росту функції використовується О-символіка.
Коли говорять, що час виконання T(n) деякої програми має порядок O(n2), то мається на увазі, що існують такі додатні константи c і n0 що для всіх n більших і рівних n0 виконується нерівність T(n)≤cn2. Припускається, що всі функції часу виконання програми визначені на множені невід’ємних чисел і їх значення є також невід’ємними, але не обов’язково цілими. Кажуть, що T(n) має порядок O(f(n)) якщо існують такі константи c і n0 при яких для всіх n≥n0 виконується нерівність T(n)≤cf(n)
О-символіка. Функції часу виконання алгоритму
Для опису швидкості росту функції використовується О-символіка.
1 – більшість інструкцій більшості програм мають час виконання пропорційний деякій константі;
log N – коли час виконання програми є логарифмічним, програма стає повільнішою із ростом N. Такий час виконання як правило мають програми, що розбивають велику задачу на декілька під задач, зменшуючи при цьому на кожному кроці розмір задачі на деяке постійне число (при N=1000, log N=3).
N – коли час виконання програми є лінійним. (означає, що кожен вхідний елемент підлягає деякій обробці)
NlogN – час виконання пропорційний NlogN, виникає, коли алгоритм розв’язку задачі розбиває її на менші під задачі, розв’язує їх незалежно, а потім об’єднує.
N2 – час виконання задачі є квадратичним, Практичного застосовується лише для відносно невеликих задач. Отримується у випадку обробки алгоритмом всіх пар елементів вхідних даних. (При N=1000, N2 = 1 міл. При х2 – час виконання х4)
N3 – схожий алгоритм, обробляє трійки елементів даних і має кубічний час росту. (При N=100, N3 = 1 міл. При х2 – час виконання х8)
2n – має експоненціональний час виконання. З’являється при спробах прямого розв’язку поставлених задач. (При N=20, N3 = 1 міл. При х2 – час виконання х*x)
Обчислення часу виконання програми. Правила.
Правило сум : O(max(f(n),g(n))).
Правило добутку : O(f(n)*g(n)).
1. Час виконання операторів присвоювання, читання і запису зазвичай має порядок О(1).
2. Час виконання послідовності операторів визначається з допомогою правила сум. Тому степінь росту часу виконання послідовності операторів без визначення констант пропорційно співпадає з найбільшим часом виконання оператора в даній послідовності.
3. Час виконання умовного оператора складається із часу виконання умовно виконуваних операторів і часу обрахунку самого логічного виразу. Час обрахунку логічного виразу зазвичай має порядок О(1). Час обрахунку для всіє конструкції if-then-else складається із часу обрахунку логічного виразу та найбільшого з часів, необхідних для виконання операторів, виконуваних при значені логічного виразу true і при значенні false.
4. Час виконання циклу є сумою часів всіх виконуваних ітерацій циклу, які в свою чергу складаються із часів виконання операторів циклу і часу обрахунку умови припинення циклу. (зазвичай О(1)).
Правила аналізу часу виконання алгоритмів.
1. Час виконання операторів присвоювання, читання і запису зазвичай має порядок О(1).
2. Час виконання послідовності операторів визначається з допомогою правила сум. Тому степінь росту часу виконання послідовності операторів без визначення констант пропорційно співпадає з найбільшим часом виконання оператора в даній послідовності.
3. Час виконання умовного оператора складається із часу виконання умовно виконуваних операторів і часу обрахунку самого логічного виразу. Час обрахунку логічного виразу зазвичай має порядок О(1). Час обрахунку для всіє конструкції if-then-else складається із часу обрахунку логічного виразу та найбільшого з часів, необхідних для виконання операторів, виконуваних при значені логічного виразу true і при значенні false.
4. Час виконання циклу є сумою часів всіх виконуваних ітерацій циклу, які в свою чергу складаються із часів виконання операторів циклу і часу обрахунку умови припинення циклу. (зазвичай О(1)).
Тип даних “Список”, його властивості
списком називають послідовність елементів певного типа, Основою властивістю списків, є можнливість лінійного впорядкування його елементів, тобто ми можемо стверджувати, що елемент ai передує елементу ai+1 (для i=1,2,3,…n-1) і слідує за елементом ai-1 (для n=2,3,…n).
Оператори для роботи із АТД “Cписок”
END(L) – повертає позицію, яка слідує одразу після позиціх n в n-елементному списку.
INSERT (x, p, L) – оператор вставляє елемент x в позицію p в
LOCATE (x, L) – визначає позицію елемента x в списку L.
RETRIEVE (p, L) – повертає елемент, що знаходиться в позиції p в списку L.
DELETE (p, L) – видаляє елемент в позиції p із списку L.
NEXT (p, L) і PREVIOUS (p, L) – повертає наступну і попередню позиції від позиції p в списку L
MAKENULL(L) – робить список порожнім, і повертає позицію END(L).
FIRST (L) – повертає першу позицію в списку,
PRINTLIST (L) – друк всі елементи в списку L в порядку їх слідування.
Реалізація АТД “Список” при допомозі масивів
При реалізації списку при допомозі масиву елементи списку розташовуються в суміжних комірка масиву.Така реалізація дозволяє легко проглядати список і вставляти нові елементи в його кінець. Але вставка нового елементу в його середину потребує переміщення всіх послідуючих елементів на одну позицію до кінця масиву. Видалення елементу також потребує зсуву всіх решти елементів на одну позицію.При використанні масиву ми визначимо структуру типу LIST з двома значеннями: перше поле – elements, яке визначає масив елементів, друге поле –last - ціле число яке вказує на позицію останнього елементу в масиві.
Реалізація АТД “Список” при допомозі вказівників. Однозв’язні списки.
В даному випадку, для реалізації зв’язку між елементами списку використовується вказівники, що звільняє нас від необхідності використовувати неперервну ділянку пам’яті, а відповідно і віднеохідності пересування всіх елементів при вставці чи видаленні одного із них.Список складається з комірок, кожна з яких містить значення елементу списку і вказівник на наступний елемент цього списку.
Реалізація АТД “Список” при допомозі вказівників. Двозв’язні списки.
В даному випадку, для реалізації зв’язку між елементами списку використовується вказівники, що звільняє нас від необхідності використовувати неперервну ділянку пам’яті, а відповідно і віднеохідності пересування всіх елементів при вставці чи видаленні одного із них.Список складається з комірок, кожна з яких містить значення елементу списку і вказівник на наступний елемент цього списку.
Реалізація АТД “Список” при допомозі курсорів
Курсорами називатимемо - цілі числа, які вказують на положення елемента в масиві.
Представлено два масиви L = a, b, c і M = d, e. Вкладені в один масив SPACE:
Всі комірки масиву, незайняті елементами списку, утворюють окремий список, що називається вільним і використовується як джерело вільних комірок при вставці нових елементів.
Тип даних “Стек”. Оператори для роботи із АТД “Cтек”
Стек – це спеціальний тип списку, в якому всі вставки і видалення елементів виконуються тільки на одному з його кінців, який називається вершиною стеку (top).
MAKENULL(S) – робить стек порожнім.
TOP (S) – повертає елемент, що знаходиться на вершині стеку S.
POP(S) – видаляє елемент з вершини стеку (виштовхує із стеку).
PUSH(x, S) – встановлює елемент x на вершину стеку S (заштовхує елемент в стек).
EMPTY(S) – повертає значення true, якщо стек порожній, і значення false – в противному випадку.
Реалізація АТД “Стек” при допомозі массиву
function MAKENULL (STACK S)
S.top = maxlenght+1
function EMPTY (STACK S) {
if S.top > maxlenght
then return true
else return false
function TOP (STACK S)
if EMPTY(S)
then error (“стек порожній”)
else return S.elementtype[S.top] }
function POP (STACK S)
if EMPTY(S)
then error (“стек порожній”)
else S.top = S.top + 1 }
function PUSH (elementtype x, STACK S)
if S.top == 1
then error (“Стек повний”)
else
S.top = S.top – 1;
S.elements[S.top] = x;
Тип даних “Черга”. Оператори для роботи з АТД “Черга”
Черга (queue) – спеціальний тип списку, де елементи додаються з одного кінця,який назив. хвостом (tail або rear), а вилучаються з іншого, який називається головою.
MAKENULL(Q) – очищає чергу Q, роблячи її порожньою.
FRONT(Q) – функція повертає перший елемент черги Q.
ENQUEUE(x,Q) – ставить елемент x в кінець черги Q.
DEQUEUE (Q) – видаляє перший елемент із черги Q.
EMPTY(Q) – повертає значення true тоді і лише тоді коли чергою Q є порожньою.
Реалізація АТД “Черга” при допомозі вказівників
function MAKENULL (QUEUE Q)
new Q.front
Q.front->next = NULL
Q.rear = Q.front;
function EMPTY (QUEUE Q)
if Q.front == Q.rear
then return true
else return false;
function FRONT (QUEUE Q)
if EMPTY(Q)
then error (“черга порожня”)
else return Q.front->next->element
function ENQUEUE (elementtype x, QUEUE Q)
new Q.rear->next
Q.rear = Q.rear->next
Q.rear->element = x
Q.rear->next = NULL
function DEQUEUE (QUEUE Q)
if EMPTY(Q)
then error (“черга пуста”)
else Q.front = Q.front->next;
Реалізація АТД “Черга” при допомозі циклічного массиву
Для вставки нового елементу в чергу необхідно перемістити вказівник Q.rear на одну позицію за годинниковою стрілкою і записати елемент в цю позицію.
При видаленні елементу з черги достатньо просто перемістити вказівник Q.front за годинниковою стрілкою.
function addone (int i) // додавання одиниці до позицій i
return (i mod maxlenght) + 1; // в циклічному сенсі
function MAKENULL (QUEUE Q)
Q.front = 1;
Q.rear = maxleght;
function EMPTY (QUEUE Q)
if addone(Q.rear) == Q.front
then return true;
else return false;
function FRONT (QUEUE Q) {
if EMPTY (Q)
then error (“Черга пуста”);
else Q.elements[Q.front] }
function ENQUEUE (elementtype x, QUEUE Q)
if addone(addone(Q.rear)) == Q.front
then error (“Черга повна”);
else
Q.rear = addone (Q.rear)
Q.elements[Q.rear] = x;
function DEQUEUE (QUEUE Q) {
if EMPTY(Q)
then error (“Черга пуста”);
else Q.front = addone(Q.front);
Тип даних “Відображення”. Оператори для роботи із АТД “Відображення”
Відображення – це функція, яка визначена на деякій множині елементів одного типу і яка приймає значення із множини елементів іншого типу.
MAKENULL (M) – робить відображення порожнім.
ASSIGN (M, d, r) – робить M(d) рівним r незалежно від того, як M(d) було визначено до цього
COMPUTE(M, d, r) – повертає значення true і присвоює змінній r значення M(d), якщо відображення M(d) є визначеним і повертає false в противному випадку.
Реалізація АТД “Відображення” при допомозі массиву
domaintype lastvalue = const
domaintype firstvalue = const
struct MAPPING
rangetype elem[lastvalue]
function MAKENULL (MAPPING M)
domaintype i;
for i from firstvalue to lastvalue do
M.elem = невизначений;
function ASSIGN (MAPPING M, domaintype d, rangetype r) {
M.elem[d] = r; }
function COMPUTE (MAPPING M, domaintype d, rangetype r) {
if M.elem[d] == невизначений)
then return false;
else
r = M.elem[d];
return true
Реалізація АТД “Відображення” при допомозі списків
function ASSING (MAPPING M, domaintype d, rangetype r)
elementtype x
position p
x.domain = d;
x.range = r;
p = FIRST(M)
while p ≠ END(M) do
if RETRIEVE (p, M).domain == d
then DELETE(p, M);
else p = NEXT(p, M);
INSERT (x, FIRST(M), M);
function COMPUTE (MAPPING M, domaintype d, rangetype r)
position p
p = FIRST (M)
while p ≠ END(M)
if RETRIEVE (p, M).domain == d
then
r = RETRIEVE(p,M).range
return true
p = NEXT(p, M);
return false
Тип даних “Множина”. Основні дії над множинами
Множиною називається деяка сукупність елементів, кожен елемент якої або сам є множиною або є примітивним елементом, який має назву - атом. Припускається, що всі елементи множини є різними, тобто в будь-якій множині немає двох копій одного і того самого елементу.
Об’єднанням множин А і В (АÈВ) називається множина, яка складається із елементів, що належать хоча б одній із множин А чи В.
Перетином множин А і В (АÇВ) називається множина, яка складається із елементів, що належать і до множини А і до множини В.
Різницею множин А і В (А\В) називається множина, яка складається із елементів, що належать множині А, але не належать множині В.
Оператори для роботи із АТД “Множина”. Моделі представлення.
MERGE(A, B, C) – об’єднання множин, що неперетинаються. Присвоює С=АÈВ
MEMBER(x, A) – повертає значення true, якщо елемент х належить множині А і значення false, якщо
MAKENULL(A) – присвоює множині А значення порожньої множини.
INSERT(x, A) – робить х елементом множини А. Або іншими словами АÈ{x}.
DELETE(x,A) – видаляє елемент х з множини А. А\{x}.
ASSIGN(A, B) – присвоює множині А в якості значення множину В.
MIN(A) – повертає найменший елемент множини А.
EQUAL (A, B) – повертає значення true, якщо множини А і В складаються з одних і тих самих елементів.
FIND (x) – функція може бути визначена в середовищі, де є деякий набір множин, що не перетинаються. Повертає ім’я множини, в якій міститься елемент х.
Представлення при допомозі двійкових векторів і при допомозі зв’язаних списків
Реалізація АТД “Множина” при допомозі двійкових векторів
Якщо множина, яку ми розглядаємо, є підмножиною деякої великої універсальної множини цілих чисел 1..N, то можна застосувати реалізацію АТД SET при допомозі двійкового вектора (який називають буловим).В такому випадку, множина є представлена двійковим вектором, в якому і-й біт рівний 1(true), якщо i є елементом множини.Перевагою такої реалізації є те, що оператори MEMBER, INSERT і DELETE можна виконати за фіксований проміжок часу. А якщо універсальна множина настільки мала, що двійковий вектор займає не більше розміру змінної, то оператори UNION, INTERSECTION і DIFFERENCE можна виконати з допомогою простих логічних операцій над двійковими векторами (and, or, andnot).
function UNION (SET A, SET B, SET C)
for I from 0 to NUM do
C = A or B;
Для реалізації операторів INTERSECTION чи DIFFERENCE необхідно логічну операцію or замінити на and чи and not відповідно.
Реалізація АТД “Множина” при допомозі зв’язаних списків
Множини можна представляти у вигляді зв’язаного списку, коли елементи, що знаходяться в списку вважаються елементами, що містяться в множині.
На відміну від представлення при допомозі двійкових векторів, в даному випадку простір, який займає АТД пропорційний розміру, який займає сама множини, а не розміру її універсальної множини. Крім того таке представлення є більш загальним, оскільки тут множини не повинні бути підмножинами деякої універсальної множини.
function INTERSECTION (celltype↑ ahead, celltype↑ bhead, celltype↑ pc) {
celltype↑ acurrent, bcurrent, ccurrent;
acurrent = ahead->next;
bcurrent = bhead->next;
ccurrent = pc;
while (acurrent ≠ NULL) and (bcurrent ≠ NULL) do
if acurrent->element == bcurrent->element
then
new ccurrent->next
ccurrent = ccurrent->next
ccurrent->element = accurent->element;
acurrent = acurrent->next;
bcurrent = bcurrent->next;
else
if acurrent->element < bcurrent->element
then acurrent = acurrent->next;
else bcurrent = bcurrent->next;
ccurrent->next=NULL; }
АТД “Словник”. Реалізація словників
Словники можна представити при допомозі відсортованих чи не відсортований списків. Інша можлива реалізація словників з використанням двійкових векторів, за умови, що елементи даної множини є цілими числами 1,…,N.Ще один варіант реалізації - з використанням масивів фіксованої довжини з вказанням на останню заповнену комірку цього масиву. Така реалізація можлива, якщо нам точно відомо, що розмір словника не стане більшим за задану розмірність масиву.
struct DICTIONARY
int last
nametype data[1..maxsize]
function MAKENULL (DICTIONARY A)
A.last = 0;
function MEMBER (nametype x, DICTIONARY A)
for i from 1 to A.last do
if A.data == x
then return true
return false;
function INSERT (nametype x, DICTIONARY A)
if MEMBER (x, A) == false
then
if A.last < maxsize
then
A.last = A.last +1;
A.data[A.last] = x;
Else error (“словник заповнений”);
function DELETE (nametype x, DICTIONARY A)
int i;
if A.last > 0
then
for i=1 to A.last do
if A.data == x
then
A.data = A.data[last]
A.last = A.last - 1
Хешування та хеш-таблиці
Хеш-таблиця являє собою узагальнення звичайного масиву. Можливість прямої індексації елементів звичайного масиву забезпечує доступ до будь-якої позиції в масиві за час 0(1).
Проте, якщо кількість ключів, що реально зберігаються в масиві, мала в порівнянні з кількістю можливих значень ключів, то зберігання такого масиву є не ефективним, а в деяких випадках і неможливим.
Альтернативою в цьому випадку стає хеш-таблиця, яка для зберігання елементів використовує масив з розміром, пропорційним кількості ключів, що реально в ній зберігаються.
А замість безпосереднього використання ключа як індекс елементу в масиву, індекс обчислюється за значенням цього ключа.
У випадку прямої адресації, елемент з ключем k зберігається в комірці під номером k. При хешуванні ж, цей елемент зберігається в комірці з номером h(k), тобто ми використовуємо хеш-функцію h() для обчислення номеру комірки для даного ключа k.
Хешування. Розв’язання колізій при хешування
Хешування— перетворення вхідного масиву даних довільної довжини у вихідний бітовий рядок фіксованої довжини.При використанні даного методу ми об'єднуємо всі елементи, хешовані в одну і ту ж комірку в зв'язаний список, а сама комірка містить покажчик на заголовок такого списку;
якщо ж елементів, ключ яких хешується в номер цієї комірки – немає, то комірка містить null.
Методика відкритого хешування
Хеш-функція. Приклади хеш-функцій
Хеш-функція — функція, що перетворює вхідні дані будь-якого (як правило, великого) розміру в дані фіксованого розміру. int h(nametype x){ int sum = 0; for (unsigned int i = 0; i<strlen(x); i++)
sum = sum+(int)x[i]; return sum%(dict_size) ;}
Закрите хешування
При закритому хешування в таблиці елементів містяться безпосередньо самі значення елементів а не заголовки списків. Тому в кожному сегменті хеш-таблиці може зберігатися лише один елемент.
Якщо ж ми намагатимемося помістити елемент x в сегмент з номером h(x) який уже зайнятий іншим елементом, то відповідно із методикою повторного хешування вибираємо послідовність інших номерів сегментів h1(x), h2(x),… куди ми можемо помістити елемент. Якщо ж вільних сегментів немає, то відповідно хеш-таблиця заповнена і елемент x вставити ми не можемо.
Реалізації хеш-функцій при закритому хешуванні
Лінійне дослідження
При такому методі для визначення послідовності досліджень використовують хеш-функцію:
де i – приймає значення від 0 до m-1.h(k) – називається допоміжною хеш-функцією.
Квадратичне дослідження
Квадратичне дослідження використовує хеш-функцію вигляду:
де – допоміжні константи відмінні від нуля, i – приймає значення від 0 до m-1.
Подвійне хешування є одним з найкращих способів використання закритого хешування, оскільки отримувані при ньому перестановки є достатньо випадковими.
Подвійне хешування використовує хеш-функцію вигляду:
де – допоміжні хеш-функці i – приймає значення від 0 до m1.
Наприклад в якості хеш-функцій для цього методу можна вибрати такі:
де m` - повинно бути трішки меншим за m
Тип даних “Дерево”. Основні означення. Обхід дерева в прямому порядку
Дерево (tree) – це сукупність елементів, які називаються вузлами та відношень між цими елементами, що утворюють ієрархічну структуру дерева.Початковий вузол дерева називається його коренем (root).
Вершина ступеню нуль має назву кінцевої(terminal) або листа (leaf).
Некінцева вершина також має назву вершини розгалуження (branch node).
Нащадки та предки вершини x, що не співпадають з нею самою, називаються власними нащадками та предками.Якщо вершина x є предком y та не існує вершин поміж ними (тобто x та y з'єднані одним ребром), а також існують предки для x (тобто x не є коренем), то вершина x називаєтьсябатьком (parent) до y, а y — дитиною(child) x.Коренева вершина єдина не має батьків. Вершини, що мають спільного батька, називаються братами (siblings).Вершини, що мають дітей, називаються внутрішніми (internal).
Глибиною вершини x називається довжина шляху від кореня до цієї вершини.
Максимальна глибина вершин дерева називається висотою.
Лісом (forest) називають множину дерев, які не перетинаються.
при проходженні в прямому порядку вузлів дерева T, спочатку відвідується корінь n, далі всі вузли під дерева T1, всі вузли під дерева T2, і т.д. Останнім відвідуються вузли під дерева Tk
Тип даних “Дерево”. Основні означення. Обхід дерева в симетричномупорядку
Дерево (tree) – це сукупність елементів, які називаються вузлами та відношень між цими елементами, що утворюють ієрархічну структуру дерева.Початковий вузол дерева називається його коренем (root).
Вершина ступеню нуль має назву кінцевої(terminal) або листа (leaf).
Некінцева вершина також має назву вершини розгалуження (branch node).
Нащадки та предки вершини x, що не співпадають з нею самою, називаються власними нащадками та предками.Якщо вершина x є предком y та не існує вершин поміж ними (тобто x та y з'єднані одним ребром), а також існують предки для x (тобто x не є коренем), то вершина x називаєтьсябатьком (parent) до y, а y — дитиною(child) x.Коренева вершина єдина не має батьків. Вершини, що мають спільного батька, називаються братами (siblings).Вершини, що мають дітей, називаються внутрішніми (internal).
Глибиною вершини x називається довжина шляху від кореня до цієї вершини.
Максимальна глибина вершин дерева називається висотою.
Лісом (forest) називають множину дерев, які не перетинаються.
при симетричному обході вузлів дерева T, спочатку відвідуються в симетричному порядку всі вузли під дерева T1, далі корінь n, а потім послідовно в симетричному порядку всі вузли під дерев T2,…,Tk.
Тип даних “Дерево”. Основні означення. Обхід дерева в зворотному орядку
Дерево (tree) – це сукупність елементів, які називаються вузлами та відношень між цими елементами, що утворюють ієрархічну структуру дерева.Початковий вузол дерева називається його коренем (root).
Вершина ступеню нуль має назву кінцевої(terminal) або листа (leaf).
Некінцева вершина також має назву вершини розгалуження (branch node).
Нащадки та предки вершини x, що не співпадають з нею самою, називаються власними нащадками та предками.Якщо вершина x є предком y та не існує вершин поміж ними (тобто x та y з'єднані одним ребром), а також існують предки для x (тобто x не є коренем), то вершина x називаєтьсябатьком (parent) до y, а y — дитиною(child) x.Коренева вершина єдина не має батьків. Вершини, що мають спільного батька, називаються братами (siblings).Вершини, що мають дітей, називаються внутрішніми (internal).
Глибиною вершини x називається довжина шляху від кореня до цієї вершини.
Максимальна глибина вершин дерева називається висотою.
Лісом (forest) називають множину дерев, які не перетинаються.
при обході в зворотному порядку, спочатку відвідуються всі вузли під дерева T1, потім послідовно відвідуються всі вузли під дерев T2,…,Tk, також в зворотному порядку, останнім відвідується корінь n.
Порядок вузлів в дереві. Реалізація алгоритмів обходу дерев
Як правило, сини вузла впорядковуються зліва-на-право І такі дерева називаються впорядкованими.Якщо порядок синів ігнорується, то такі дерева називаються невпорядкованими
Дерева з мітками. Дерева-вирази
Досить часто буває корисно кожному вузлу дерева надати певну мітку або значення, так само як і елементам списку надаються певні значення.
Дерево для його кожному із його вузлів поставлено у відповідність певну мітку(label), називається поміченим деревом (labeled tree).
Мітка вузла – це не ім’я вузла, а значення яке в ньому міститься.
Оператори для роботи із АТД “Древо”
PARENT (n, T) – функція повертає предка вузла n в дереві T.
LEFTMOST_CHILD (n, T) – функція повертає самого лівого сина вузла n в дереві T.
RIGHT_SIBLING (n, T) – функція повертає правого брата вузла n в дереві T
LABEL (n, T) – повертає мітку вузла n дерева T
CREATE (v, T1, T2,…,Ti) – створює новий корінь r з міткою v і кожне із під дерев T стає його сином.
ROOT(T) – повертає вузол, що є коренем дерева.
MAKENULL(T) – оператор робить дерево T порожнім.
Реалізація АТД “Дерево” при доомозі массиву
Одним з найпростіших представлень абстрактного типу даних TREE, є лінійний масив A, де кожен елемент A[i] є вузлом дерева і містить вказівник чи курсор на свого батька.Корінь дерева відрізняється від інших вузлів тим, що має нульовий вказівник, або ж вказує сам на себе.Таке представлення використовує ту особливість дерева, що кожен з його вузлів має лише одного батька, тому батька будь-якого вузла можна знайти за фіксований час.
Для реалізації оператора LABEL (помічені дерева) можна скористатися ще одним масивом L, в якому елемент L[i] буде містити мітку i-го вузла дерева, або ж описати елементи масиву Aяк структуру, що складатиметься із двох полів вказівника на батька та мітки вузла.
Реалізація АТД “Дерево” при дпомозі списків синів
сellspace array [1..maxnodes] of struct
int node
int next
// повертає самого лівого сина вузла n дерева Т
function LEFTMOST_CHILD (node n, TREE T):node
int L; // курсор на початок списку синів вузла n
L = T.header[n]
if EMPTY(L) // n є листком
then return 0
else return cellspace[L].node
// повертає батька вузла n дерева T
function PARENT (node n, TREE T):node
node p;
position i;
for p from 1 to maxnodes do
i = T.header[p];
while i ≠ 0) do // перевірка на наявність синів у вузла p
if cellspace.node == n
then return p
else i = cellspace.next;
return 0
Двійкові дерев
Бінарним (двійковим) деревом називається таке дерево в якого кожен вузол або немає синів, або має чи лівого, чи правого, або має обидва.Той факт, що кожен син вузла дерева визначений як лівий або правий суттєво відрізняє бінарне дерево від впорядкованого орієнтованого дерева.Обхід бінарного дерева в прямому, симметричному і зворотньому порядках відповідає таким же обходам для звичайних дерев.
Постановка задачі сортування. Види сортування. Алгоритми сортування
Сортуванням або впорядкуванням списку об’єктів називається розташування цих об’єктів по зростанню чи спаданню.В загальному розрізняють два види сортування – внутрішнє і зовнішнє.При внутрішньому сортуванні, усі дані розміщуються в оперативній пам’яті комп’ютера, де можна отримати доступ до них у будь-якому порядку.Зовнішнє сортування застосовується тоді, коли об’єм даних, що необхідно впорядкувати, надто великий не може бути перенесений в оперативну пам’ять комп’ютера.При розгляді алгоритмів сортування, будемо вважати, що ми сортуємо певні об’єкти. В якості представлення таких об’єктів будемо використовувати структуру, що складається з одного або декількох полів і одне з полів такої структури називатиметься ключем і міститеме тип, для якого визначено відношення лінійного порядку.
В загальному, задача сортування полягає у впорядкуванні послідовності записів таким чином, щоб значення полів з ключами складали не спадаючу прогресію.
Бульбашкове сортування, Сортування вставками, Сортування через вибір,Швидке сортування, Пірамідальне сортування,“Кишенькове” сортування
Схема “бульбашкового” сортування
Щоб описати схему роботи даного алгоритму, уявимо собі що структури, які необхідно посортувати лежать в масиві, розташованому вертикально.Структури з малим значенням ключового поля більш легкі і в спливають догори як бульбашки. При першому проході масиву, береться перший об’єкт і значення його ключа порівнюється із ключовими полями усіх іншими об’єктів в масиві. Коли зустрічається об’єкт із більш легким значенням ключа, то об’єкти міняються місцями, і вже цей об’єкт стає еталоном для порівняння.
В результаті структура з найменшим значенням ключа виявляється на вершині. Під час другого проходу, знаходиться об’єкт із другим по величині ключем і він розміщується на позиції одразу під вершиною.
for (int i=0; i<n; i++)
for (int j = n-1; j>i; j--)
if (A[j].key<A[j-1].key)
swap (A[j].key, A[j-1].key);
Схема сортування через вибір
При такому сортуванні, на і-му етапі вибирається об’єкт, з найменшим значенням ключа серед об’єктів A[i]…A[n] і міняється місцем із об’єктом A[i]. В результаті, після виконання цього кроку, всі об’єкти A[1],…A[i] будуть впорядковані. для i від 0 до n-1 вибрати серед A[i],…,A[n] елемент із найменшим ключем і поміняти його місцями із A[i]. Реалізувати такий алгоритм можна наступним чином:
int lowindex, lowkey;
for (int i = 0; i < (n-1); i++) {
lowindex = i;
lowkey = A;
for (int j = i+1; j < n; j++)
if (A[j].key< lowkey) {
lowkey = A[j].key;
lowindex = j; }
swap (A.key, A[lowindex].key); }
Схема сортування вставками
При сортуванні вставками на і-тому кроці ми вставляємо і-тий елемент А[i] в потрібну позицію серед елементів A[1], A[2],…, A[i-1], які вже впорядковані. Після цієї вставки перші іелементів будуть впорядкованими.Алгоритм роботи можна описати так:
для i від 1 до n перемістити A[i] на позицію j≤і таку, що A[i]<A[k] для j≤k≤i
for (int i = 1; i<n; i++) {
j = i;
while (A[j]<A[j-1]) {
swap (A[j], A[j-1]);
if (--j == 0)
break;}}
Швидке сортування
Для сортування елементів A[1]…A[n], вибирається значення ключа v в якості опорного елементу, відносно якого перевпорядковується всі елементи масиву.Значення опорного елементу необхідно вибрати близьким по значенню до медіани розподілу значень ключів, так щоб опорний елемент розбивав множину значень ключів на дві приблизно рівні частини.Далі елементи масиву переставляються так, щоб для деякого індексу j всі переставлені елементи A[1],…,A[j] мали значення ключів, менше від v, а всі елементи A[j+1],…,A[n] – значення ключів, більше або рівне v.Після цього, процедура швидкого сортування рекурсивно застосовується до множини елементів A[1],…,A[j] та A[j+1],…,A[n] для впорядкування цих множин окремо.
Функція знаходження опорного елементу та функція перестановки елементів для методу швидкого сортування
Важливим елементом даного сортування є знаходження значення опорного ключа, відносно якого буде проведено перерозподіл елементів масиву.
int findpivot (int i, int j) {
keytype firstkey;
fk = A.key;
for (int k=i+1; k<=j; k++) {
if (A[k].key>firstkey)
return k;
else if (A[k].key<firstkey)
return i; }
return -1;}
Фунkція partition (розділення), яка виконує перестановку елементів і повертає індекс l, що вказує на точку розділення фрагменту масиву A на основі заданого опорного значення pivot, може бути реалізована наступним чином:
int partition (int i, int j, int pivot) {
int l, r;
l = i;
r = j;
do {
swap (A[l],A[r]);
while (A[l].key < pivot)
l++;
while (A[r].key >= pivot)
r--;} while (l<=r);return l;}
Пірамідальне сортування.
Перевагою пірамідального сортування є те, що його час виконання в найгіршому випадку такий же як і в середньому, і має порядок O(nlogn).елемент з найменшим пріоритетом (значенням) є коренем дерева.Проте забравши цей елемент, ми видалимо корінь і тим самим зруйнуємо дерево. Алгоритм пірамідального сортування корисний в тих випадках, коли потрібно не сортувати всі елементи n елементів, а тільки відібрати k найменших елементів з нього, і при цьому kнабагато менше n. В такому випадку, на виконання операції затратиться час порядку O(n).
Для проштовхування нового елементу A[1] (старий A[i]) в пірамідальному сортування використовується функція pushdown:
void pushdown (int first, int last) {
int j;
int r = first;
while (r<=(last/2)) {
if ((2*r==last)||(A[r*2].key<A[2*r+1].key))
j = 2*r;
else
j=2*r+1;
if (A[r].key>A[j].key) {
swap(A[r],A[j]);
r = j; }
else break; }}
Тепер саму функцію сортування можна описати як:
void heapsort (int n) {
// створення частково впорядкованого дерева
for (int i=1; i<=(n/2); i++)
pushdown (i, n);
for (i = n; i > 1; i--) {
swap (A[1], A); // видалення мінімального елементу
pushdown(1,i-1);}} //відновлення часткової впорядкованості
“Кишенькове” сортування
кишенькового сортування, коли створюються кишені для збереження записів з певними значеннями ключів. Ми перевіряємо, чи має даний запис ключ із значення k і якщо має, то поміщаємо цей запис в кишеню для записів, чиї значення ключів рівні k.
Але в загальному випадку ми повинні бути готовими до того, що в одній кишені може зберігатися декілька записів, а також повинні вміти об’єднувати вміст декількох кишень в одну, розташовуючи елементи в об’єднаній кишені в правильному порядку.
Для цього організуємо кишені у вигляді списків. Найкраще для цього підійдуть зв’язані списки, оскільки загальна кількість елементів, що будуть міститися в даній кишені на наперед не відома. Також нам потрібно масив В типу listtype, який буде містити вказівники на кишені.
Для об’єднання кишень використовуватиме функцію CONCATENATE(L1, L2), яка з двох списків L1: a1,a2,…,ai L2: b1,b2,…,bj формує результуючий список a1,a2,…,ai,b1,b2,…,bj.
void binsort () {
int I;
keytype v;
for (int i=0; i<n; i++)
// записує елемент A[i] на початок кишені,
// яка відповідає ключу цього елементу
INSERT (A, FIRST(B[A.key]), B[A.key]);
for (v = lowkey+; v <= highkey; v++)
// конкатенація всі кищень
CONCATENATE (B[lowkey], B[v]);}
Сортування злиттям.
В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву.
Постановка задачі пошуку. Методи пошуку.
Під оптимальністю пошуку будемо розуміти середній час, що необхідно витратити для знаходження елементу в масиві.Масив даних в якому здійснюється пошук може бути дійсним (порядок елементів не змінювався) і перетвореним (порядок елементів спеціальним чином впорядковано). Відповідно для першого випадку, для порівняння елементів можна застосовувати лише операцію ==, а в другому ще й операцію <.
Також можливе існування елементів із дубльованими ключами. В деяких програмах існування дубльованих ключів не припускається, тому ключі можна використовувати в якості курсорів на необхідні дані (номери кредитних карточок), але в деяких програмах може допускатися наявність декількох елементів з однаковими ключами (пошук по ключовому слову в базі даних телефонів).Обробка елементів з ключами що дублюються можна виконувати одним із декількох способів. Один із способів – це залишення в масиві даних лише одного елементу з дублюючими ключами, і щоб він посилався на масив, а якому містилися всі решта елементів з таким же ключем. В даному випадку, ми знаходимо всі елюенти одразу. Другий спосіб – це розташування дублюючих елементів в одному масиві і повернення в результаті пошуку першого із них. Такий підхід можливий для програм, що обробляють елементи по одному і порядок слідування елементі із однаковими ключами неважливий.Пошук з використанням індексації по ключах,,Послідовний пошук,,Бінарний пошук
Пошук із використання індексації по ключах
Припустивши, що ключі – це окремий набір невеликих чисел, найпростіший алгоритм пошуку можна організувати, якщо зберігати елементи в масиві індексуючи їх по ключах.В даному випадку при виконанні операції вставки нового елементу, ми одразу отримуємо відсортований по зростанню масив. Якщо елементи як такі відсутні (є лише їх індекси), то можна використовувати таблицю біт, і в такому випадку ця таблиця називається таблицею існування (existence table), оскільки i-й біт можна вважати ознакою існування i в наборі ключів таблиці.
struct Item {
elementtype elem;
keytype key;} A[NUM];
int insert (Item x) {
A[x.key] = x;}
Item search (keytype key) {
return A[key];}
Коли можливо, то варто вибирати метод пошуку з використанням індексації, тому що складно більш ефективно реалізувати функції insert() і search().Для зберігання елементів з однакоми ключами можна використовати зв’язаний список, а перед використанням ключів, можна виконувати їх просте приведення або відображення.
Послідовний метод пошуку
В загальному випадку, коли значення ключів елементів відносяться до дуже великого діапазоку, один із підходів базується на розташуванні елементів в списку один за одним.При виконанні вставки, елемент вставляєтсья в останню вільну позицію в списку (отримаємо невідсортований масив) або вставляється в відповідну позицію, і всі елементи, що слідують за ним, переміщаються на одну позицію. При пошуку, список проглядається послідовно, поки не буде знайдено шуканий елемент, або поки не буде досягнуто кінець списку.Реалізацію списку може бути як і при допомозі массиву, так і при допомозі динамічних структур.
Метод бінарного пошуку
Якщо дані, по який потрібно провести пошук – відсортовані, то можна застосувати набагато ефективніший алгоритм, який називається бінарним пошуком. При використанні цього алгоритму, на початку перевіряється середній елемент. Якщо він більший ключа пошуку, то перевіряється середній елемент першої половини масиву, якщо менше ключа, то середній елемент другої половини. Ця послідовність повторюється доти, поки не буде знайдено спів падіння, чи поки не залишиться елементів, які ще можна перевірити.В найгіршому випадку, бінарний пошук виконується за log2n порівнянь. В середньому – буде виконано трохи менше порівнянь, а в найкращому – одне.
Item binary_search (keytype key) {
keytype low, high, mid;
low= 0; high = maxElem;
while (low<=high) {
mid = (low+high)/2;
if (key < A[mid].key)
high = mid-1;
else if (key>A[mid].key)
low = mid+1;
else return A[mid];}}
Дерево пошуку.
Дерева пошуку призначені для представлення словників як абстрактного типу даних. Як і пріоритетні черги, вони представляють зважені множини, але з іншим набором операцій, а саме:
Вважається, що кожен елемент словника має ключ (вагу), що приймає значення з лінійно впорядкованої множини. Такою множиною може бути, наприклад, числова множина або множина слів в деякому алфавіті. В останньому випадку в якості лінійного порядку можна розглядати лексикографічний порядок. Таким чином, дерево пошуку може бути використано і як словник, і як пріоритетна черга. Час виконання основних операцій пропорційний висоті дерева. Якщо кожен внутрішній вузол двійкового дерева має рівно двох нащадків, то його висота і час виконання основних операцій пропорційні логарифму числа вузлів. І навпаки, якщо дерево являє собою лінійний ланцюжок з n вузлів, цей час виростає до Ο(n). Відомо, що висота випадкового двійкового дерева є Ο(log n), так що в цьому випадку час виконання основних операцій є Ο(log n). Звичайно, що виникаючі на практиці двійкові дерева пошуку можуть бути далекі від випадкових. Однак, прийнявши спеціальні заходи по балансуванню дерев, можна гарантувати, що висота дерев з n вузлами буде O(log n).
Типові методи розробки алгоритмів
1. Алгоритм “розділяй і володарюй”
2. Динамічне програмування
3. "Жадібні" алгоритми
4. Пошук з поверненням
5. Алгоритми локального пошуку
На сьогодні фахівці з обчислювальної техніки розробили ряд методів, які нерідко дозволяють отримувати ефективні алгоритми розв'язання великих класів завдань. Деякі з найбільш важливих методів, такі як "розділяй і володарюй" (декомпозиції), динамічне програмування, "жадібні" методи, пошук з поверненням і локальний пошук, розглянуті в цій лекції.
Однак, слід зауважити, що існують задачі (наприклад NP-повні - non-deterministic polynomial), для яких ці та будь-які інші відомі методи не забезпечують ефективних рішень. Коли зустрічається подібна завдання, нерідко буває корисно визначити, чи володіють вхідні дані для цього завдання якими-небудь особливими характеристиками, якими можна скористатися при спробах знайти рішення, і чи можна скористатися будь-яким наближеним рішенням замість точного, одержати яке буває дуже важко.
Алгоритми “розділяй і володарюй”
Можливо, найважливішим і найбільш широко застосовуваним методом проектування ефективних алгоритмів є метод, що називається методом декомпозиції (або метод "розділяй і володарюй", або метод розбиття). Цей метод передбачає таку декомпозицію (розбиття) завдання розміру nна більш дрібні завдання, що на основі рішень цих більш дрібних завдань можна легко отримати рішення вихідної завдання. Ми вже знайомі з рядом застосувань цього методу, наприклад - бінарний пошук. Саме легкість розробки алгоритмів за методом декомпозиції зумовила величезну популярність цього методу; до того ж, у багатьох випадках ці алгоритми виявляються більш ефективними, ніж алгоритми, розроблені традиційними методам.
Динамічне програмування
Коли не вдається розбити задачу на невелике число підзадач, об'єднання рішень яких дозволяє отримати рішення вихідної задачі. У таких випадках ми можемо спробувати розділити завдання на стільки підзадач, скільки необхідно, потім кожну підзадачу розділити на ще дрібніші підзадачі і т.д. Якщо б весь алгоритм зводився саме до такої послідовності дій, ми б в результаті отримали алгоритм з експоненціальним часом виконання.Але часто вдається отримати лише поліноміальний число підзадач і тому ту або іншу підзадачу доводиться вирішувати багато разів. Якщо б замість цього ми запам’ятовували розв'язок кожної вже вирішеної підзадачі і в разі необхідності просто відшукували його, то б отримали алгоритм з поліноміальним часом виконання.З точки зору реалізації іноді буває простіше створити таблицю рішень всіх підзадач, які нам коли-небудь доведеться вирішувати. Ми заповнюємо цю таблицю незалежно від того, чи потрібна нам насправді конкретна підзадача для отримання загального рішення. Заповнення таблиці підзадач для отримання рішення визначеної задачі отримало назву динамічного програмування (ця назва походить з теорії управління).Форми алгоритму динамічного програмування можуть бути різними - загальною їх "темою" є лише таблиця і порядок заповнення її елементів.
"Жадібні" алгоритми
Ще одна задача, припустимо, що у нас є монети номіналу 25, 10, 5 копійок і 1 копійка і потрібно повернути здачу 63 копійки. Майже не роздумуючи, ми перетворимо цю величину в дві монети по 25 копійок, одну монету в 10 копійок і три монети по одній копійці. Нам не тільки вдалося швидко визначити перелік монет потрібного номіналу, а й, по суті, ми склали найкоротший список монет необхідного номіналу.
Алгоритм, полягав у виборі монети самого великої гідності (25 копійок), але не більше 63 копійок, додаванню її в список здачі і відніманню її вартості з 63 (виходить 38 копійок). Потім знову вибираємо монету самого великого номіналу, але не більше залишку (38 копійок): цією монетою знову виявляється монета в 25 копійок. Цю монету ми знову додаємо до списку здачі, віднімаємо її вартість із залишку і т.д.Цей метод називається "жадібним" алгоритмом. На кожній окремій стадії "жадібний" алгоритм вибирає той варіант, який є локально оптимальним у тому чи іншому сенсі. Слід підкреслити, що не кожен "жадібний" алгоритм дозволяє отримати оптимальній результат в цілому. Як нерідко буває в житті, "жадібна стратегія" забезпечує лише миттєву вигоду, у той час як в цілому результат може виявитися несприятливим.
Пошук з поверненням
Іноді доводиться мати справу із завданням пошуку оптимального рішення, коли неможливо застосувати жоден з відомих методів, здатних допомогти відшукати оптимальний варіант рішення, і залишається вдатися до останнього засобу – повного перебору, який ще називають пошуком з поверненням.
Розглянемо будь-яку гру за участю двох гравців, наприклад шахи, шашки або "хрестики-нулики". Гравці поперемінно роблять ходи, і стан гри відображається відповідним положенням на дошці. Припустимо, що є кінцеве число позицій на дошці і в грі передбачено певне "правило зупинки", що є критерієм її завершення. З кожною такою грою можна асоціювати дерево, яке називають деревом гри.Кожен вузол такого дерева представляє певну позицію на дошці. Початкова позиція відповідає кореню дерева. Якщо позиція х асоціюється з вузлом n, тоді нащадки вузла n відповідають сукупності допустимих ходів з позиції x і з кожним нащадком асоціюється відповідна результуюча позиція на дошці.Листки цього дерева відповідають таким позиціям на дошці, з яких неможливо зробити хід, - чи тому, що хтось з гравців вже здобув перемогу, чи тому, що всі клітини заповнені і гра закінчилася внічию.Кожному вузлу дерева відповідає певна ціна. Спочатку призначається ціни листкам. Припустимо, мова йде про гру в "хрестики-нулики". У такому разі листкам призначається ціна -1, 0 або 1 в залежності від того, чи відповідає даній позиції програш, нічия або виграш гравця 1 (який ставить "хрестики").Ці ціни поширюються вгору по дереву у відповідності з наступним правилом. Якщо будь-який вузол відповідає позиції, з якої повинен зробити хід гравець 1, тоді відповідна ціна є максимальною серед цін нащадків даного вузла. При цьому припускаємо, що гравець 1 зробить самий вигідний для себе хід, тобто такий, який принесе йому найцінніший результат. Якщо ж вузол відповідає ходу гравця 2, тоді відповідна ціна є мінімальною серед цін нащадків даного вузла. При цьому ми припускаємо, що гравець 2 також зробить самий вигідний для себе хід, тобто такий, який за найсприятливішого результату призведе до програшу гравця 1, а при менш бажаному результаті - до нічиєї. Якщо ціна кореня дорівнює 1, то виграшна стратегія знаходиться в руках гравця 1. Дійсно, коли настає його черга ходити, він гарантовано може вибрати хід, який призведе до позиції, що має ціну 1. Коли ж настає черга гравця 2 робити свій хід, йому не залишається нічого іншого, як вибрати хід, що веде до все тієї ж позиції з ціною 1, що для нього означає програш. Якщо ж ціна кореня дорівнює 0, як у випадку гри в "Хрестики-нулики", тоді жоден з гравців не має в своєму розпорядженні виграшної стратегією і може гарантувати собі лише нічию, якщо буде грати без помилок. Якщо ж ціна кореня дорівнює -1, то виграшна стратегія знаходиться в руках гравця 2.
Алгоритм локального пошуку
Описана нижче стратегія нерідко призводить до оптимального рішення задачі.
1. Почніть з довільного рішення.
2. Для поліпшення поточного рішення застосуєте до нього будь-яке перетворення з деякої заданої сукупності перетворень. Ця поліпшене рішення стає новим "поточним" рішенням.
3. Повторюйте зазначену процедуру до тих пір, поки жодне з перетворень з заданої їх сукупності не дозволить поліпшити поточне рішення.
Результуюче рішення може, хоча і необов'язково, виявитися оптимальним. У принципі, якщо "задана сукупність перетворень" охоплює всі перетворення, які беруться в якості вихідного - одне рішення і замінюють його яким-небудь іншим, процес "поліпшень" не закінчиться до тих пір, поки ми не отримаємо оптимальне рішення. Але в такому випадку час виконання пункту (2) виявиться таким самим, як і час, потрібний для аналізу всіх рішень, тому описуваний підхід в цілому виявиться досить безглуздим.Якщо сукупність перетворень невелика, природно розглядати рішення, які можна перетворювати одне в інше за один крок, як "близькі". Такі перетворення називаються "локальними", а відповідний метод називається локальним пошуком.
Алгоритми локального пошуку проявляють себе з найкращого боку як євристичні алгоритми для вирішення завдань, точні рішення яких вимагають експоненційних затрат часу. Загальноприйнятий метод пошуку полягає в наступному: почати слід з ряду довільних рішень, застосовуючи до кожного з них локальні перетворення до тих пір, поки не буде отримано локально-оптимальний розв’язок, тобто такий, який не можна поліпшити жодним перетворенням.