Recomandat, 2020

Alegerea Editorului

Diferența dintre căutarea informată și cea neinformată

Căutarea este un proces de găsire a unei secvențe de pași necesare pentru a rezolva orice problemă. Diferența anterioară între căutarea informată și cea neinformată este că căutarea informată oferă îndrumări cu privire la locul și modalitatea de găsire a soluției. În schimb, căutarea neinformată nu oferă informații suplimentare despre problemă, cu excepția caietului de sarcini.

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țieCă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
CostScăzutComparativ de mare
PerformanţăGăsește soluția mai repedeViteza 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ă

  1. 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.
  2. Eficiența căutării informate este mai bună decât căutarea neinformată.
  3. 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ă.
  4. 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.

Top