Алгоритм пошуку!!!

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

Опис

Алгоритми пошуку класифікуються на основі їх механізму пошуку. Лінійний пошук працює достатньо повільно, відносно бінарного пошуку, але на практиці часто зустрічається. Алгоритм лінійного пошуку порівнює кожний елемент в структурі даних зі значенням котре потрібно знайти. Існує також бінарний пошук, або половинно-інтервальний пошук, однак він працює лише з відсортованими елементами, один з найшвидших алгоритмів, який повторно порівнює пошуковий елемент з центральним елементом заданої структури, якщо знайшов то кінець, якщо ні, то порівнює елементи та продовжує пошук в лівій чи правій частині структури даних поки не знайде потрібний. Реалізація алгоритму пошуку для хеш-таблиці — складне завдання, бо в такій структурі даних кожному елементу відповідає певний ключ (key), та данні відсортовані по цим ключам.[3] Потрібно досить гарно реалізувати хеш-функцію для пошуку елементу по ключу,[4] бо алгоритм пошуку буде шукати спочатку ключ, а потім отримуватиме значення по ключу.

Реалізація бінарного пошуку, псевдокод:

BinarySearch(A[0..N-1], value, low, high) {
     if (high < low)
         return -1; // не знайдено
     mid = (low + high) / 2;
     if (A[mid] > value) 
         return BinarySearch(A, value, low, mid-1); рекурсивно обходимо праву частину масива
     else if (A[mid] < value)
         return BinarySearch(A, value, mid+1, high); рекурсивно обходимо ліву частину масива
     else
         return mid; // знайдено
   }

Класифікація

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

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

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

Пошук максимуму функції

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

Developed by Інститут Програмних Систем