Алгоритм пошуку
Алгори́тм по́шуку ― в інформатиці ― формальні правила, що визначають стратегію пошуку інформації, яка зберігається в певній структурі даних. Дані можуть бути представлені рядком, масивом, зв’язаним списком, деревом пошуку, хеш-таблицею, неструктурованим набором тощо.
Характеристика
Пошук є однією з найчастіше використовуваних операцій у програмуванні.
Вхідними даними пошукових алгоритмів є пошуковий ключ (поле запису, використовуючи значення якого, відбувається пошук) та функція, яка визначає відповідність знайденого результату заданому ключу. Це може бути значення булевої функції «так» або «ні», функція обчислення еквівалентності, функції релевантності та пертинентності тощо. Постановку завдання пошуку здійснюють за допомогою графового або аналітичного опису, який базуються на елементах теорії графів, моделей, алгебр та алгебраїчних систем.
Ефективність алгоритму пошуку залежить від типу використовуваних даних та методів їх обробки. Її оцінюють на основі складності алгоритму або максимального часу виконання. Складність визначають максимальною кількістю операцій порівняння пошукового ключа для найбільш песимістичного випадку. Це значення позначають як On, де n – кількість виконаних порівнянь. Варіанти виконання пошукових алгоритмів ― найкращий, середній, найгірший варіанти. Значення середнього варіанту поведінки пошукового алгоритму визначає корисність алгоритму.
Класифікація
Видів алгоритмів пошуку дуже багато, і вони різняться способом організації даних. Виділяють пошук поінформований, коли алгоритм виконує пошук поміж своїми даними, і непоінформований, коли програма крім пошуку має виконувати розпізнавальні функції.
Алгоритми пошуку як набір інструкцій, що описують порядок дій виконавця, можна поділити на класи, які залежать від мети пошуку, критеріїв відповідності, методів ранжування результатів та механізму зворотного зв’язку для оцінювання отриманих результатів: зіставляння із взірцем (лінійний, бінарний, інтерполяційний пошуки), комбінаторні алгоритми (пошук на графах, пошук у масиві даних, пошук у рядках), хеш-функції. Загальна класифікація алгоритмів пошуку:
- віртуально-просторовий пошук;
- пошук підструктур заданої структури;
- пошук максимуму функції;
- імовірнісна модель пошуку;
- пошук методами логічного виведення;
- нейромережі;
- генетичні алгоритми;
- евристична модель пошуку.
Виокремлюють також інформаційний пошук залежно від завдання: семантичний інформаційний пошук, пошук у структурах, пошук оптимального розв’язання, пошук шляху, пошук закономірностей у даних, пошук подібності (розбіжностей) у мультимедійних даних ― пошук облич, розпізнавання образів тощо. Алгоритми пошуку часто використовують разом з алгоритмами сортування.
Література
- Глушков В. М., Цейтлин Г. Е., Ющенко Е. Л. Алгебра. Языки. Программирование. Киев: Наукова думка, 1974. 327 с.
- Цейтлин Г. Е. Поиск и сортировка: классификация, трансформация, синтез. II, // Автоматика и телемеханика, 1992, №5, с.156–165. URL: : http://www.mathnet.ru/links/a47bb959c70c88156a6205a87769bc2a/at3305.pdf
- Кнут Д. Э. Искусство программирования. Том 3. Сортировка и поиск / Пер. с англ. М. Р. Саит-Аметова /2-е изд. Киев: Вильямс, 2007. 832 с.
- Вирт Н. Алгоритмы и структуры данных. Новая версия для Оберона: пер. с англ./2-е изд., испр. Москва : ДМК Премм, 2016. 271 с.
- Грехов А. М. Інтелектуальні інформаційні технології в бізнесі. Дюссерльдорф : Lambert, 2018, 335 с.
Автор ВУЕ
Покликання на цю статтю: Гришанова І. Ю. Алгоритм пошуку // Велика українська енциклопедія. URL: https://vue.gov.ua/Алгоритм пошуку (дата звернення: 6.05.2024).
Статус гасла: Оприлюднено
Оприлюднено: 26.12.2017
Важливо!
Ворог не зупиняється у гібридній війні і постійно атакує наш інформаційний простір фейками.
Ми закликаємо послуговуватися інформацією лише з офіційних сторінок органів влади.
Збережіть собі офіційні сторінки Національної поліції України та обласних управлінь поліції, аби оперативно отримувати правдиву інформацію.
Отримуйте інформацію тільки з офіційних сайтів
Офіс Президента України
Верховна Рада України
Кабінет Міністрів України
Служба безпеки України
Міністерство оборони України
Міністерство внутрішніх справ України
