Vyhledávací algoritmy jsou jednou z nejdůležitějších oblastí umělé inteligence. Toto téma vysvětlí vše o vyhledávacích algoritmech v AI.

zkuste datovou strukturu

Agenti pro řešení problémů:

V umělé inteligenci jsou techniky vyhledávání univerzálními metodami řešení problémů. Racionální agenti nebo Agenti pro řešení problémů v AI většinou používaly tyto vyhledávací strategie nebo algoritmy k vyřešení konkrétního problému a poskytnutí nejlepšího výsledku. Agenti řešící problémy jsou agenty založené na cíli a používají atomovou reprezentaci. V tomto tématu se naučíme různé vyhledávací algoritmy pro řešení problémů.

Terminologie vyhledávacích algoritmů:

Vyhledávání:Vyhledávání je postup krok za krokem k vyřešení problému hledání v daném vyhledávacím prostoru. Problém s vyhledáváním může mít tři hlavní faktory:
Vyhledat prostor:Vyhledávací prostor představuje množinu možných řešení, která systém může mít.Počáteční stav:Je to stav, kde agent začíná výzkum .Cílový test:Je to funkce, která sleduje aktuální stav a vrací, zda je cílový stav dosažen nebo ne.
Hledat strom:Stromová reprezentace vyhledávacího problému se nazývá vyhledávací strom. Kořenem vyhledávacího stromu je kořenový uzel, který odpovídá počátečnímu stavu.Akce:Poskytuje agentovi popis všech dostupných akcí.Model přechodu:Popis toho, co každá akce dělá, může být reprezentován jako přechodový model.Cena trasy:Je to funkce, která každé cestě přiřadí číselnou cenu.Řešení:Je to akční sekvence, která vede od počátečního uzlu k cílovému uzlu.Optimální řešení:Pokud má řešení nejnižší cenu ze všech řešení.

Vlastnosti vyhledávacích algoritmů:

Níže jsou uvedeny čtyři základní vlastnosti vyhledávacích algoritmů pro porovnání účinnosti těchto algoritmů:

Úplnost: Algoritmus hledání je považován za úplný, pokud zaručuje, že vrátí řešení, pokud pro jakýkoli náhodný vstup existuje alespoň nějaké řešení.

Optimalita: Pokud je řešení nalezené pro algoritmus zaručeno jako nejlepší řešení (nejnižší náklady na cestu) ze všech ostatních řešení, pak se takové řešení považuje za optimální řešení.

Časová náročnost: Časová složitost je měřítkem času, za který algoritmus dokončí svůj úkol.

Prostorová složitost: Je to maximální úložný prostor požadovaný v kterémkoli okamžiku během vyhledávání podle složitosti problému.

Typy vyhledávacích algoritmů

Na základě vyhledávacích problémů můžeme rozdělit vyhledávací algoritmy na neinformované (slepé vyhledávání) a informované (heuristické vyhledávání) algoritmy.

Neinformované/slepé vyhledávání:

Neinformované vyhledávání neobsahuje žádné doménové znalosti jako blízkost, umístění cíle. Funguje způsobem hrubé síly, protože obsahuje pouze informace o tom, jak procházet strom a jak identifikovat uzly listů a cílů. Neinformované vyhledávání používá způsob, kdy je vyhledávací strom prohledáván bez jakýchkoli informací o vyhledávacím prostoru, jako jsou operátory počátečního stavu a test na cíl, takže se také nazývá slepé vyhledávání. Zkoumá každý uzel stromu, dokud nedosáhne cílového uzlu.

Dá se rozdělit do pěti hlavních typů:

• Hledání do šířky
• Jednotné hledání nákladů
• Hledání do hloubky
• Iterativní prohlubování hloubka-nejprve hledání
• Obousměrné vyhledávání

Informované vyhledávání

Informované vyhledávací algoritmy využívají znalost domény. Při informovaném vyhledávání jsou k dispozici informace o problémech, které mohou hledání vést. Informované vyhledávací strategie mohou najít řešení efektivněji než neinformované vyhledávací strategie. Informované vyhledávání se také nazývá heuristické vyhledávání.

Heuristika je způsob, který nemusí vždy zaručit nejlepší řešení, ale zaručit nalezení dobrého řešení v rozumném čase.

Informované vyhledávání může vyřešit mnoho složitých problémů, které nelze vyřešit jiným způsobem.

np tečka

Příkladem informovaného vyhledávacího algoritmu je problém cestujícího prodejce.

1. Greedy Search
2. Hledání