TechCodeview

Алгоритми пошуку є однією з найважливіших областей штучного інтелекту. У цій темі буде пояснено все про алгоритми пошуку в ШІ.

Агенти з вирішення проблем:

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

Термінологія алгоритму пошуку:

пошук:Пошук — це покрокова процедура вирішення проблеми пошуку в даному просторі пошуку. Проблема пошуку може мати три основні фактори:
Простір пошуку:Простір пошуку являє собою набір можливих рішень, які може мати система.Початковий стан:Це стан, з якого починається агент пошук .Цільовий тест:Це функція, яка спостерігає за поточним станом і повертає інформацію про те, досягнуто цільового стану чи ні.
Дерево пошуку:Деревоподібне представлення задачі пошуку називається деревом пошуку. Корінь дерева пошуку - це кореневий вузол, який відповідає початковому стану.Дії:Він дає агенту опис усіх доступних дій.Модель переходу:Опис того, що робить кожна дія, можна представити як модель переходу.Вартість шляху:Це функція, яка призначає числову вартість кожному шляху.рішення:Це послідовність дій, яка веде від початкового вузла до цільового вузла.Оптимальне рішення:Якщо рішення має найнижчу вартість серед усіх рішень.

Властивості пошукових алгоритмів:

Нижче наведено чотири основні властивості алгоритмів пошуку для порівняння ефективності цих алгоритмів:

Повнота: Алгоритм пошуку вважається повним, якщо він гарантує повернення рішення, якщо існує принаймні будь-яке рішення для будь-якого випадкового введення.

Оптимальність: Якщо рішення, знайдене для алгоритму, гарантовано є найкращим рішенням (найменша вартість шляху) серед усіх інших рішень, то таке рішення для вважається оптимальним рішенням.

Часова складність: Часова складність — це міра часу, за який алгоритм виконує своє завдання.

чому рядок незмінний у java

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

Типи пошукових алгоритмів

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

Неінформований/сліпий пошук:

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

Його можна розділити на п'ять основних типів:

• Пошук вшир
• Уніфікований пошук вартості
• Пошук в глибину
• Ітеративний пошук у глибину з поглибленням
• Двонаправлений пошук

Інформований пошук

Інформовані алгоритми пошуку використовують знання домену. При обґрунтованому пошуку доступна інформація про проблему, яка може керувати пошуком. Стратегії обґрунтованого пошуку можуть знайти рішення ефективніше, ніж стратегія необізнаного пошуку. Інформований пошук також називають евристичним пошуком.

Евристика — це спосіб, який не завжди може гарантувати найкращі рішення, але гарантовано знайде хороше рішення за прийнятний час.

Інформований пошук може вирішити багато складних проблем, які неможливо вирішити іншим шляхом.

Прикладом обґрунтованих алгоритмів пошуку є задача комівояжера.

1. Жадібний пошук
2. A* Пошук