Алгоритми пошуку - це алгоритми пошуку в масиві даних (або в якійсь структурі) певного елемента або елементів з визначеними параметрами, які називаються, параметрами пошуку.

Алгоритми пошуку розрізняють:

- Лінійний пошук;

- Евристичний пошук;

- Ймовірнісний пошук;

- Неявний пошук.

Лінійний пошук.

Існує певна структура даних (масив, список…) і треба знайти в цій структурі елемент з певними властивостями. Цей пошук простий, але не ефективний, коли ми маємо велику кількість даних.

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

Питання №9

Алгоритм пошуку, «Ймовірнісний пошук».

Алгоритми пошуку розрізняють:

- Лінійний пошук;

- Евристичний пошук;

- Ймовірнісний пошук;

- Неявний пошук.

Ймовірнісний пошук.

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

Переваги:

1. Скорочення часу пошуку;

2. Якщо кількість перевірених об’єктів в результаті пошуку пропорційна загальному обсягу масиву, то точність приблизно 80%.

Недоліки:

1. Наближена точність;

2. Не працює з відносно малими масивами даних.

Питання №10

Алгоритм пошуку, «Неявний пошук».

Алгоритми пошуку розрізняють:

- Лінійний пошук;

- Евристичний пошук;

- Ймовірнісний пошук;

- Неявний пошук.

Неявний пошук.

Неявний пошук..............

Питання №11

Алгоритм пошуку, «Евристичний пошук».

Алгоритми пошуку розрізняють:

- Лінійний пошук;

- Евристичний пошук;

- Ймовірнісний пошук;

- Неявний пошук.

Евристичний пошук.

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

Для алгоритму евристичного пошуку будується дерево майбутніх варіантів (станів), кожен з варіантів оцінюється за допомого евристичної функції: f(g)=g+h(g), де

g – поточний стан ситуації;

h(g) – евристична складова.

Питання №12

Стратегії пошуку на графах (пошук в довжину, пошук в ширину…).

Графи являються універсальним формальним описом будь-якої прикладної форми та задачі. Графи можуть представлятися матрицями суміжності та інцедентності. Ці графи дуже легко перетворити в необхідні структури даних. І відповідно дуже легко можливо перетворити в різні допоміжні структури (списки, дерева…). Існує багато типів алгоритмів на графах з пошуком оптимальних частин графа, частина пов’язана з побудовою нових графів на основі даних, які закладені в базовому графі.

В основу алгоритмів на графах покладена процедура пошуку відповідних вершин або ребер. Пошук цей здійснюється за допомогою різних стратегій:

- Пошук в ширину;

Пошук в глибину;

- Пошук з поверненням;

«Жадібний» пошук.

Пошук в ширину.

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

Пошук в глибину.

Починається з обирання глибини пошуку.

Пошук з поверненням.

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

«Жадібний» пошук.

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

Питання №13

Алгоритм Дейкстри.

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

Алгоритм Дейкстри – це послідовна ітераційна процедура, в основу якої покладений пошук в ширину, це перший крок. На наступному кроці процедура повторюється. Але для перевірки на другому кроці, використовують пошук в глибину, задаються глибиною 3-4 і обраховують довжину шляху до всіх вершин цього рівня. Обирають ту вершину цього рівня, шлях до якої є коротшим.

Питання №14

Алгоритм Прима-Краскала.

Каркас – це під-граф на базовому рівні графа, в якому не має циклів.

Алгоритм складається з двох частин:

- Виписуються всі ребра і сортуються за зростанням починаючи з мінімального;

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

Питання №15

1 234