TechCodeview

Meklēšanas algoritmi ir viena no vissvarīgākajām mākslīgā intelekta jomām. Šajā tēmā tiks izskaidrots viss par AI meklēšanas algoritmiem.

Problēmu risināšanas aģenti:

Mākslīgajā intelektā meklēšanas metodes ir universālas problēmu risināšanas metodes. Racionālie aģenti vai Problēmu risināšanas aģenti AI pārsvarā izmantoja šīs meklēšanas stratēģijas vai algoritmus, lai atrisinātu konkrētu problēmu un nodrošinātu vislabāko rezultātu. Problēmu risināšanas aģenti ir uz mērķi balstīti aģenti un izmanto atomu attēlojumu. Šajā tēmā apgūsim dažādus problēmu risināšanas meklēšanas algoritmus.

Meklēšanas algoritmu terminoloģijas:

Meklēt:Meklēšana ir soli pa solim procedūra, lai atrisinātu meklēšanas problēmu noteiktā meklēšanas telpā. Meklēšanas problēmai var būt trīs galvenie faktori:
Meklēt vietu:Meklēšanas vieta ir iespējamo risinājumu kopums, kas var būt sistēmai.Sākuma stāvoklis:Tas ir stāvoklis, no kura sākas aģents meklēšana .Vārtu pārbaude:Tā ir funkcija, kas novēro pašreizējo stāvokli un atgriež, vai mērķa stāvoklis ir sasniegts vai nē.
Meklēšanas koks:Meklēšanas problēmas koka attēlojumu sauc par meklēšanas koku. Meklēšanas koka sakne ir saknes mezgls, kas atbilst sākuma stāvoklim.Darbības:Tas sniedz aģentam visu pieejamo darbību aprakstu.Pārejas modelis:Katras darbības aprakstu var attēlot kā pārejas modeli.Ceļa izmaksas:Tā ir funkcija, kas katram ceļam piešķir skaitliskas izmaksas.Risinājums:Tā ir darbību secība, kas ved no sākuma mezgla uz mērķa mezglu.Optimālais risinājums:Ja risinājumam ir viszemākās izmaksas starp visiem risinājumiem.

Meklēšanas algoritmu īpašības:

Tālāk ir norādītas četras galvenās meklēšanas algoritmu īpašības, lai salīdzinātu šo algoritmu efektivitāti.

Pilnīgums: Tiek uzskatīts, ka meklēšanas algoritms ir pabeigts, ja tas garantē risinājuma atgriešanu, ja ir vismaz kāds risinājums jebkurai nejaušai ievadei.

Optimalitāte: Ja algoritmam atrastais risinājums garantēti ir labākais risinājums (zemākās ceļa izmaksas) starp visiem citiem risinājumiem, tad šāds risinājums tiek uzskatīts par optimālu risinājumu.

Laika sarežģītība: Laika sarežģītība ir laika mērs, kurā algoritms pabeidz savu uzdevumu.

Kosmosa sarežģītība: Tā ir maksimālā uzglabāšanas vieta, kas nepieciešama jebkurā meklēšanas brīdī, ņemot vērā problēmas sarežģītību.

Meklēšanas algoritmu veidi

Pamatojoties uz meklēšanas problēmām, mēs varam klasificēt meklēšanas algoritmus neinformētās (aklās meklēšanas) un informētās meklēšanas (heiristiskās meklēšanas) algoritmos.

Neinformēta/akla meklēšana:

Neinformēta meklēšana nesatur nekādas domēna zināšanas, piemēram, tuvumu, mērķa atrašanās vietu. Tas darbojas brutālā veidā, jo ietver tikai informāciju par to, kā šķērsot koku un kā identificēt lapu un mērķa mezglus. Neinformētā meklēšana izmanto veidu, kā tiek meklēts meklēšanas koks bez jebkādas informācijas par meklēšanas telpu, piemēram, sākotnējā stāvokļa operatori un mērķa pārbaude, tāpēc to sauc arī par aklo meklēšanu. Tā pārbauda katru koka mezglu, līdz sasniedz mērķa mezglu.

To var iedalīt piecos galvenajos veidos:

• Meklēšana pirmajā vietā
• Vienota izmaksu meklēšana
• Meklēšana pēc dziļuma
• Iteratīvs padziļināšanas dziļums vispirms meklēšana
• Divvirzienu meklēšana

Informēta meklēšana

Informēti meklēšanas algoritmi izmanto domēna zināšanas. Apzinātā meklēšanā ir pieejama informācija par problēmu, kas var palīdzēt meklēšanā. Informētas meklēšanas stratēģijas var atrast risinājumu efektīvāk nekā neinformētas meklēšanas stratēģija. Informēto meklēšanu sauc arī par heiristisko meklēšanu.

Heiristika ir veids, kas ne vienmēr var tikt garantēts vislabākajiem risinājumiem, bet garantēts, ka saprātīgā laikā tiks atrasts labs risinājums.

Apzināta meklēšana var atrisināt daudzas sarežģītas problēmas, kuras nevar atrisināt citā veidā.

Informētas meklēšanas algoritmu piemērs ir ceļojoša pārdevēja problēma.

1. Mantkārīgā meklēšana
2. A* Meklēt