Алгоритмите за търсене са една от най-важните области на изкуствения интелект. Тази тема ще обясни всичко за алгоритмите за търсене в AI.

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

В изкуствения интелект техниките за търсене са универсални методи за решаване на проблеми. Рационални агенти или Агенти за решаване на проблеми в AI използва най-вече тези стратегии за търсене или алгоритми за решаване на конкретен проблем и осигуряване на най-добрия резултат. Агентите за решаване на проблеми са базирани на цели агенти и използват атомно представяне. В тази тема ще научим различни алгоритми за търсене за решаване на проблеми.

Терминология на алгоритъма за търсене:

Търсене:Търсенето е процедура стъпка по стъпка за решаване на проблем с търсене в дадено пространство за търсене. Проблемът с търсенето може да има три основни фактора:
Пространство за търсене:Пространството за търсене представлява набор от възможни решения, които една система може да има.Начално състояние:Това е състояние, от което агентът започва търсенето .Целеви тест:Това е функция, която наблюдава текущото състояние и връща дали целевото състояние е постигнато или не.
Дърво за търсене:Дървовидното представяне на проблема с търсенето се нарича дърво на търсенето. Коренът на дървото за търсене е коренният възел, който съответства на първоначалното състояние.Действия:Той дава описание на всички налични действия на агента.Преходен модел:Описание на това какво прави всяко действие може да бъде представено като модел на преход.Цена на пътя:Това е функция, която присвоява числова цена на всеки път.Решение:Това е последователност от действия, която води от началния възел до целевия възел.Оптимално решение:Ако едно решение има най-ниската цена сред всички решения.

Свойства на алгоритмите за търсене:

Следват четирите основни свойства на алгоритмите за търсене, за да се сравни ефективността на тези алгоритми:

Пълнота: Казва се, че алгоритъмът за търсене е пълен, ако гарантира, че ще върне решение, ако съществува поне някакво решение за всеки случаен вход.

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

Времева сложност: Времевата сложност е мярка за времето, за което алгоритъмът трябва да изпълни своята задача.

Космическа сложност: Това е максималното място за съхранение, което се изисква във всеки един момент по време на търсенето, като сложността на проблема.

Видове алгоритми за търсене

Въз основа на проблемите с търсенето можем да класифицираме алгоритмите за търсене на алгоритми за неинформирано (сляпо търсене) и информирано търсене (евристично търсене).

форматирайте датата в java

Неинформирано/сляпо търсене:

Неинформираното търсене не съдържа никакви знания за домейн като близост, местоположение на целта. Той работи по начин на груба сила, тъй като включва само информация за това как да преминете през дървото и как да идентифицирате листни и целеви възли. Неинформираното търсене прилага начин, по който дървото за търсене се търси без никаква информация за пространството за търсене като оператори за първоначално състояние и тест за целта, така че се нарича още сляпо търсене. То изследва всеки възел на дървото, докато достигне целевия възел.

Може да се раздели на пет основни вида:

• Търсене в широчината
• Единно търсене на разходите
• Първо търсене в дълбочина
• Итеративно задълбочаващо се търсене в дълбочина
• Двупосочно търсене

Информирано търсене

Алгоритмите за информирано търсене използват знания за домейна. При информирано търсене е налична информация за проблема, която може да насочи търсенето. Информираните стратегии за търсене могат да намерят решение по-ефективно от неинформираната стратегия за търсене. Информираното търсене се нарича още евристично търсене.

Евристиката е начин, който може да не винаги е гарантиран за най-добри решения, но гарантиран за намиране на добро решение в разумен срок.

Информираното търсене може да реши много сложен проблем, който не може да бъде решен по друг начин.

Пример за информирани алгоритми за търсене е проблем с пътуващ търговец.

1. Алчно търсене
2. A* Търсене