Пошук із використання індексації по ключах

Припустивши, що ключі – це окремий набір невеликих чисел, найпростіший алгоритм пошуку можна організувати, якщо зберігати елементи в масиві індексуючи їх по ключах.В даному випадку при виконанні операції вставки нового елементу, ми одразу отримуємо відсортований по зростанню масив. Якщо елементи як такі відсутні (є лише їх індекси), то можна використовувати таблицю біт, і в такому випадку ця таблиця називається таблицею існування (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().Для зберігання елементів з однакоми ключами можна використовати зв’язаний список, а перед використанням ключів, можна виконувати їх просте приведення або відображення.

Послідовний метод пошуку

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

Метод бінарного пошуку

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

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];}}

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

• Search — пошук елемента із заданим ключем.

• Minimum — пошук елемента з мінімальним ключем.

• Maximum — пошук елемента з максимальним ключем.

• Predecessor — пошук елемента з попереднім ключем.

• Successor — пошук елемента з наступним ключем.

• Insert — вставка елемента зі своїм ключем.

• Delete — видалення зазначеного елемента.

Вважається, що кожен елемент словника має ключ (вагу), що приймає значення з лінійно впорядкованої множини. Такою множиною може бути, наприклад, числова множина або множина слів в деякому алфавіті. В останньому випадку в якості лінійного порядку можна розглядати лексикографічний порядок. Таким чином, дерево пошуку може бути використано і як словник, і як пріоритетна черга. Час виконання основних операцій пропорційний висоті дерева. Якщо кожен внутрішній вузол двійкового дерева має рівно двох нащадків, то його висота і час виконання основних операцій пропорційні логарифму числа вузлів. І навпаки, якщо дерево являє собою лінійний ланцюжок з 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) виявиться таким самим, як і час, потрібний для аналізу всіх рішень, тому описуваний підхід в цілому виявиться досить безглуздим.Якщо сукупність перетворень невелика, природно розглядати рішення, які можна перетворювати одне в інше за один крок, як "близькі". Такі перетворення називаються "локальними", а відповідний метод називається локальним пошуком.

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