Cu toate acestea, între tehnicile de căutare informate și neinformate, căutarea informată este mai eficientă și mai eficientă din punct de vedere al costurilor.
Diagramă de comparație
| Bazele de comparație | Căutare informată | Căutarea neinformată |
|---|---|---|
| De bază | Folosește cunoștințe pentru a găsi pașii către soluție. | Nu folosiți cunoștințele |
| Eficienţă | Foarte eficient deoarece consumă mai puțin timp și costuri. | Eficiența este mediatorie |
| Cost | Scăzut | Comparativ de mare |
| Performanţă | Găsește soluția mai repede | Viteza este mai lentă decât căutarea informată |
| algoritmi | Căutarea în profunzime, prima căutare și prima căutare la cel mai mic preț | Adâncimea euristică este prima și cea de-a lungul primei căutări, și căutarea A * |
Definiția Informed search
Tehnica de căutare informată utilizează cunoștințele specifice problemei pentru a da un indiciu soluției problemei. Acest tip de strategie de căutare împiedică algoritmii să se împiedice în legătură cu scopul și direcția spre soluție. Căutarea informată poate fi avantajoasă din punctul de vedere al costului în care se obține optimitatea la costuri mai mici de căutare.
Pentru a căuta un cost optim al traseului într-un grafic prin implementarea strategiei de căutare informate, nodurile cele mai promițătoare n sunt inserate în funcția euristică h (n). Apoi, funcția returnează un număr real negativ, care este un cost aproximativ al traseului calculat de la nodul n la nodul țintă.
Aici cea mai importantă parte a tehnicii informate este funcția euristică care facilitează transmiterea cunoștințelor adiționale ale problemei către algoritm. Ca rezultat, ajută la găsirea modului de atingere a obiectivului prin diferitele noduri vecine. Există diferiți algoritmi bazați pe căutarea informată, cum ar fi căutarea în profunzime euristică, prima căutare euristică, prima căutare, A * căutare, și așa mai departe. Să înțelegem acum căutarea heuristică în adâncime.
Euristic Depth Prima căutare
Similar metodei de căutare de adâncime, dată mai jos, adâncimea euristică prima căutare alege o cale dar traversează toate căile din calea selectată înainte de a alege altă cale. Cu toate acestea, alege calea cea mai bună la nivel local. În cazurile în care cea mai mică valoare euristică este prioritatea frontierei, atunci este cunoscută ca cea mai bună prima căutare.
Un alt algoritm de căutare informat este căutarea A *, care combină primul concept de cel mai mic cost cu cel mai bun număr de căutări. Această metodă ia în considerare atât costul călătoriei, cât și informațiile euristice în procesul de căutare și de selectare a căii de extindere. Costul total al traseului estimat utilizat pentru fiecare cale care se află la frontieră de la început până la nodul țintă. Prin urmare, utilizează două funcții în același timp - costul (p) este costul căii descoperite și h (p) este valoarea estimată a costului căii de la nodul de pornire la nodul de țintă.
Definiția Căutării neinformate
Căutarea neinformată este diferită de căutarea informată în modul în care oferă doar definiția problemei, dar nu mai face nici un pas către găsirea soluției la problemă. Obiectivul principal al căutării neinformate este diferențierea dintre statul țintă și cel nețintă și ignoră în totalitate destinația în care se îndreaptă în cale până când descoperă obiectivul și raportează succesorul. Această strategie este, de asemenea, cunoscută ca o căutare orb.
Există algoritmi de căutare diferiți în această categorie, cum ar fi căutare în profunzime, căutare uniformă a costurilor, căutare în lățime, și așa mai departe. Să înțelegem acum conceptul din spatele căutării neinformate cu ajutorul căutării în adâncime.
Depth First Search
În prima căutare în profunzime, o stivă Last out in first out este utilizată pentru a adăuga și elimina nodurile. Se adaugă sau se elimină simultan un singur nod, iar primul element eliminat din granița stiva ar fi ultimul element adăugat la stivă. Prin folosirea stivei în frontieră rezultatele căutării căilor au început în profunzime în primul rând. Atunci când se caută calea cea mai scurtă și optimă folosind căutarea în adâncime, calea creată de nodurile adiacente este terminată prima, chiar dacă nu este cea dorită. Apoi calea alternativă este căutată prin backtracking.
Cu alte cuvinte, algoritmul alege prima alternativă la fiecare nod, apoi backtracks la o altă alternativă până când a traversat toate căile de la prima selecție. Acest lucru ridică de asemenea o problemă în care căutarea poate înceta să se oprească datorită buclelor infinite (cicluri) prezente în grafic.
Diferențe cheie între căutare informată și neinformată
- Tehnica anterioară de căutare informată utilizează cunoștințe pentru a găsi soluția. Pe de altă parte, această tehnică de căutare neinformată nu utilizează cunoștințe. În termeni simpli, nu există informații suplimentare despre soluție.
- Eficiența căutării informate este mai bună decât căutarea neinformată.
- Căutarea neinformată consumă mai mult timp și cost, deoarece nu are nici o idee despre soluție în comparație cu căutarea informată.
- Căutarea în profunzime, prima căutare și prima căutare la cel mai mic preț sunt algoritmii care se încadrează în categoria căutării neinformate. Spre deosebire de aceasta, căutarea informată acoperă algoritmii, cum ar fi adâncimea euristică - primul, lățimea euristică - prima căutare și căutarea A *.
Concluzie
Căutarea informată oferă direcția privind soluția în timp ce în căutarea neinformată nu este oferită sugestie cu privire la soluție. Acest lucru face căutarea neinformată mai lungă atunci când algoritmul este implementat.
