Проте, між інформаційними та неінформованими методами пошуку, поінформований пошук є більш ефективним та економічно ефективним.
Діаграма порівняння
| Основа для порівняння | Інформований пошук | Неінформований пошук |
|---|---|---|
| Основний | Використовує знання для пошуку кроків до рішення. | Немає знань |
| Ефективність | Висока ефективність, оскільки споживає менше часу та витрат. | Ефективність є посередницькою |
| Вартість | Низький | Порівняно високий |
| Продуктивність | Швидше знаходить рішення | Швидкість повільніше, ніж інформований пошук |
| Алгоритми | Пошук по глибині, пошук по ширині і пошук за найнижчою вартістю | Евристична глибина першого та першого пошуків у ширині, а також пошук * |
Визначення інформаційного пошуку
Метод інформованого пошуку використовує конкретні знання проблеми, щоб дати ключ до розв'язання проблеми. Цей тип стратегії пошуку фактично заважає алгоритмам спотикатися про мету і напрямок до рішення. Інформований пошук може бути вигідним з точки зору вартості, коли оптимальність досягається при зниженні витрат на пошук.
Для пошуку оптимальної вартості шляху в графі за допомогою реалізації інформованої стратегії пошуку найважливіші вузли n вставляються в евристичну функцію h (n). Потім функція повертає неотрицательное дійсне число, яке є приблизною ціною шляху, обчисленої від вузла n до цільового вузла.
Тут найважливішою частиною інформованої техніки є евристична функція, яка полегшує передачу додаткових знань про проблему алгоритму. В результаті, це допомагає знайти шлях до мети через різні сусідні вузли. Існують різні алгоритми, засновані на поінформованому пошуку, такі як евристичний пошук по глибині, евристичний пошук по ширині, пошук A * і т.д. Давайте тепер зрозуміємо евристичний перший пошук.
Евристична глибина першого пошуку
Подібно до методу пошуку глибини, наведеного нижче, евристична глибина першого пошуку вибирає шлях, але проходить всі шляхи від обраного шляху до вибору іншого шляху. Тим не менш, він вибирає найкращий шлях локально. У тих випадках, коли найменше евристичне значення є пріоритетом для кордону, то воно називається найкращим першим пошуком.
Інший поінформований алгоритм пошуку - це пошук *, який поєднує в собі концепцію найменшої вартості перших і найкращих перших пошуків. Цей метод розглядає як вартість шляху, так і евристичну інформацію в процесі пошуку і вибору шляху для розширення. Орієнтовна загальна вартість шляху, яка використовується для кожного шляху, що знаходиться на кордоні від початку до цільового вузла. Тому вона використовує дві функції одночасно - вартість (p) - вартість виявленого шляху, а h (p) - розрахункове значення вартості шляху від початкового вузла до цільового вузла.
Визначення неінформованого пошуку
Неінформований пошук відрізняється від поінформованого пошуку таким чином, що він просто дає визначення проблеми, але не робить подальшого кроку для пошуку рішення проблеми. Основною метою неінформованого пошуку є розмежування між цільовим і нецільовим станом, і воно повністю ігнорує призначення, на яке він рухається, поки не виявить наступника цілі та звітів. Ця стратегія також відома як сліпий пошук.
Існують різні алгоритми пошуку під цією категорією, такі як пошук по глибині, пошук однорідної вартості, пошук по ширині і так далі. Давайте тепер зрозуміємо концепцію необізнаного пошуку за допомогою глибокого пошуку.
Глибина першого пошуку
У першому пошуку по глибині стек "Останній перший" використовується для додавання і видалення вузлів. Тільки один вузол додається або видаляється одночасно, а перший елемент, вилучений з кордону стека, буде останнім елементом, доданим до стека. Використовуючи стек в прикордонних результатах, пошук шляхів проходив у глибину першого способу. Коли виконується пошук найкоротшого і оптимального шляху за допомогою пошуку по глибині, шлях, створений сусідніми вузлами, завершується першим, навіть якщо він не є бажаним. Потім шукається альтернативний шлях через зворотне відстеження.
Іншими словами, алгоритм вибирає першу альтернативу на кожному вузлі, після чого повертається до іншої альтернативи, поки не пройде всі шляхи від першого вибору. Це також викликає проблему, коли пошук може припинитися через нескінченних циклів (циклів), наявних на графіку.
Ключові відмінності між інформованим та неінформованим пошуком
- Колишня методика інформованого пошуку використовує знання для пошуку рішення. З іншого боку, остання неінформована техніка пошуку не використовує знання. У простіших термінах немає додаткової інформації про рішення.
- Ефективність поінформованого пошуку краще, ніж неінформований пошук.
- Неінформований пошук споживає більше часу та витрат, оскільки не має жодного уявлення про рішення, порівняно з поінформованим пошуком.
- Пошук по глибині, пошук по ширині і пошук за найнижчою вартістю - це алгоритми, що входять до категорії неінформованого пошуку. На відміну від цього, поінформований пошук охоплює такі алгоритми, як евристична глибина-перша, евристичний пошук по ширині і A * пошук.
Висновок
Інформований пошук дає напрямок щодо рішення, а в неінформованому пошуку не дається жодних пропозицій щодо рішення. Це робить необізнаний пошук більш тривалим, коли реалізований алгоритм.
