Diferența dintre căutarea informată și cea neinformată
Conţinut
- Diagramă de comparație
- Definiția Informed search
- Adâncimea euristică Prima căutare
- Definiția Uninformed search
- Adâncime Prima căutare
- Concluzie
Căutarea este un proces de a găsi o succesiune de pași necesari pentru a rezolva orice problemă. Diferența anterioară dintre căutarea informată și cea neinformată este că căutarea informată oferă îndrumări despre unde și cum se poate găsi soluția. În schimb, căutarea neinformată nu oferă informații suplimentare despre problemă, cu excepția specificațiilor sale.
Cu toate acestea, între tehnici de căutare atât informate, cât și neinformate, căutarea informată este mai eficientă și mai eficientă din punct de vedere al costurilor.
-
- Diagramă de comparație
- Definiție
- Diferențele cheie
- Concluzie
Diagramă de comparație
Baza de comparație | Căutare informată | Căutare neinformată |
---|---|---|
De bază | Utilizează cunoștințe pentru a găsi pașii către soluție. | Fără folos de cunoștințe |
Eficienţă | Foarte eficient, deoarece consumă mai puțin timp și cost. | Eficiența este mediatorie |
Cost | Scăzut | Comparativ ridicat |
Performanţă | Găsește soluția mai rapid | Viteza este mai lentă decât căutarea informată |
algoritmi | Adâncimea euristică prima și lățimea-prima căutare și A * căutarea | Primă căutare în profunzime, primă căutare în lățime și prima căutare cu costuri mai mici |
Definiția Informed search
Tehnica de căutare informată folosește cunoștințele specifice problemei pentru a da un indiciu asupra soluției problemei. Acest tip de strategie de căutare împiedică de fapt algoritmii să se poticnească asupra scopului și direcției către soluție. Căutarea în cunoștință de cauză poate fi avantajoasă în ceea ce privește costul unde optimitatea este obținută la costuri de căutare mai mici.
Pentru a căuta un cost de cale optimă într-un grafic prin implementarea strategiei de căutare informată, cele mai promițătoare noduri n sunt inserate la funcția euristică h (n). Apoi funcția returnează un număr real non-negativ, care este un cost de cale aproximativă 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 suplimentare ale problemei algoritmului. Drept urmare, ajută la găsirea drumului către obiectiv prin diferitele noduri vecine. Există diverse algoritmi bazate pe căutarea în cunoștință de cauză, cum ar fi euristic-prima-căutare, euristică largă-prima căutare, A * căutare, etcetera. Să înțelegem acum prima căutare euristică în profunzime.
Adâncimea euristică Prima căutare
Asemănător metodei de căutare în profunzime, dată sub profunzimea euristică, prima căutare alege o cale, dar traversează toate căile din calea selectată înainte de a alege o altă cale. Cu toate acestea, alege cea mai bună cale pe plan local. În cazurile în care cea mai mică valoare euristică este prioritatea pentru frontieră, atunci este cunoscută sub numele de cea mai bună căutare.
Un alt algoritm de căutare în cunoștință de cauză este A * căutare care îmbină conceptul de primele costuri cu cel mai mic cost și primele căutări. Această metodă ia în considerare atât costul căii, cât și informațiile euristice în procesul de căutare și selectare a căii care trebuie extinsă. Un cost total estimat al traseului utilizat pentru fiecare cale care se află pe 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 traseului de la nodul de pornire la nodul țintă.
Definiția Uninformed search
Căutarea neinformată este diferită de căutarea în cunoștință de cauză, întrucât oferă doar definiția problemei, dar nu este un pas suplimentar pentru a găsi soluția la această problemă. Obiectivul principal al căutării neinformate este diferențierea dintre starea țintă și cea care nu este țintă și ignoră total destinația către care se îndreaptă în traseu până când descoperă obiectivul și raportează succesorul. Această strategie este cunoscută și ca o căutare orbă.
Există diferiți algoritmi de căutare în această categorie, cum ar fi căutare în profunzime, căutare uniformă a costurilor, căutare în primă măsură și așa mai departe. Să înțelegem acum conceptul din spatele căutării neinformate cu ajutorul unei căutări profunde.
Adâncime Prima căutare
În căutarea în profunzime, se folosește o stivă Last in first out pentru a adăuga și elimina nodurile. Un singur nod este adăugat sau eliminat la un moment dat, iar primul element eliminat de frontiera stivei ar fi ultimul element adăugat la stivă. Prin utilizarea stivei în frontieră rezultă căutarea căilor procedate în profunzime. Când o căutare cea mai scurtă și optimă este căutată folosind prima căutare a adâncimii, calea creată de nodurile adiacente este finalizată mai întâi, 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 se întoarce 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ă din cauza buclelor infinite (ciclurilor) prezente în grafic.
- Fosta tehnică de căutare informată folosește cunoștințe pentru a găsi soluția. Pe de altă parte, ultima tehnică de căutare neinformată nu folosește cunoștințe. În termeni mai 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 niciun indiciu despre soluție în comparație cu căutarea informată.
- Primele căutări în profunzime, primele căutări în lățime și primele căutări cu cele mai mici costuri sunt algoritmii care intră în categoria căutării neinformate. Spre deosebire, căutarea în cunoștință de cauză acoperă algoritmii, cum ar fi primul euristic, căutarea euristică pentru prima lărgime și căutarea A *.
Concluzie
Căutarea informată oferă direcția cu privire la soluție, în timp ce în căutare neinformată nu se oferă nicio sugestie cu privire la soluție. Aceasta face căutarea neinformată mai lungă atunci când este implementat algoritmul.