Priporočena, 2022

Izbira Urednika

Razlika med informiranim in neinformiranim iskanjem

Iskanje je proces iskanja zaporedja korakov, ki so potrebni za rešitev katerega koli problema. Predhodna razlika med obveščenim in neinformiranim iskanjem je, da informirano iskanje zagotavlja smernice o tem, kje in kako najti rešitev. Nasprotno pa neinformirano iskanje ne daje dodatnih informacij o problemu, razen njegove specifikacije.

Vendar je med informiranimi in neinformiranimi tehnikami iskanja obveščeno iskanje učinkovitejše in stroškovno učinkovitejše.

Primerjalna tabela

Podlaga za primerjavoInformirano iskanjeNeinformirano iskanje
Osnovno
Uporablja znanje za iskanje korakov rešitve.Brez uporabe znanja
Učinkovitost
Zelo učinkovit, saj porabi manj časa in stroškov.Učinkovitost je posredna
StroškiNizkaPrimerjalno visoka
IzvedbaHitreje najde rešitevHitrost je počasnejša od informiranega iskanja
Algoritmi
Iskanje po globini, iskanje po širini in iskanje z najnižjimi stroškiHeuristična globina iskanja in iskanje po širini ter iskanje A *

Definicija informiranega iskanja

Tehnika informiranega iskanja uporablja specifično znanje o problemu, da bi dobila namig za rešitev problema. Ta vrsta strategije iskanja dejansko preprečuje, da bi se algoritmi spotaknili o cilju in smeri rešitve. Informirano iskanje je lahko ugodno v smislu stroškov, kjer je optimalnost dosežena pri nižjih stroških iskanja.

Za iskanje optimalnih stroškov poti v grafu z izvedbo strategije za obveščeno iskanje se najbolj perspektivna vozlišča n vstavijo v hevristično funkcijo h (n). Nato funkcija vrne ne-negativno realno število, ki je približen strošek poti, izračunan od vozlišča n do ciljnega vozlišča.

Pri tem je najpomembnejši del informirane tehnike hevristična funkcija, ki olajša posredovanje dodatnega znanja o problemu algoritmu. Kot rezultat, pomaga pri iskanju poti do cilja prek različnih sosednjih vozlišč. Obstajajo različni algoritmi, ki temeljijo na informiranem iskanju, kot so heuristično iskanje po globini, heuristično iskanje po širini, iskanje A *, itd. Zdaj razumemo heuristično iskanje po globini.

Hevristična globina prvega iskanja

Podobno kot je metoda iskanja po globini, ki je podana pod hevristično globino, prvo iskanje izbere pot, vendar prečka vse poti iz izbrane poti pred izbiro druge poti. Vendar pa lokalno izbere najboljšo pot. V primerih, ko je najmanjša hevristična vrednost prednostna za mejo, je znana kot najboljše prvo iskanje.

Še en obveščeni iskalni algoritem je iskanje po A *, ki združuje koncept najnižjih stroškov prvega in najboljšega prvega iskanja. Ta metoda upošteva tako stroške poti kot hevristične informacije v procesu iskanja in izbire poti, ki jo je treba razširiti. Ocenjeni skupni strošek poti, uporabljen za vsako pot, ki se nahaja na meji od začetka do ciljnega vozlišča. Zato hkrati uporablja dve funkciji - strošek (p) je strošek odkrite poti, h (p) pa je ocenjena vrednost stroškov poti od začetnega vozlišča do ciljnega vozlišča.

Opredelitev neinformiranega iskanja

Neinformirano iskanje se razlikuje od informiranega iskanja na način, da le podaja definicijo problema, vendar ni nadaljnjega koraka pri iskanju rešitve problema. Primarni cilj neinformiranega iskanja je razlikovanje med ciljnim in neciljnim stanjem in popolnoma zanemari cilj, na katerega se usmerja na poti, dokler ne odkrije naslednika cilja in poročil. Ta strategija je znana tudi kot slepo iskanje.

V tej kategoriji so na voljo različni iskalni algoritmi, kot so iskanje po globini, enotno iskanje stroškov, iskanje po širini in tako naprej. Zdaj bomo razumeli koncept neinformiranega iskanja s pomočjo prvega iskanja.

Globina prvo iskanje

V iskanju po globini se za dodajanje in odstranjevanje vozlišč uporablja niz Last in first out. Naenkrat se doda ali odstrani samo eno vozlišče, prvi element, odstranjen z meje skladov, pa je zadnji element, dodan v sklad. Z uporabo stack v mejnih rezultatih je iskanje poti potekalo v globino na prvi način. Ko najkrajšo in optimalno pot iščemo s pomočjo iskanja po globini, se pot, ki jo ustvarijo sosednja vozlišča, zaključi najprej, tudi če ni želena. Nato se alternativna pot išče skozi povratno sledenje.

Z drugimi besedami, algoritem izbere prvo alternativo na vsakem vozlišču, nato pa se vrne v drugo alternativo, dokler ne prečka vseh poti iz prve izbire. To povzroča tudi problem, ko se lahko iskanje ustavi zaradi neskončnih zank (ciklov), ki so prisotni v grafu.

Ključne razlike med informiranim in neinformiranim iskanjem

  1. Nekdanja tehnika informiranega iskanja uporablja znanje za iskanje rešitve. Po drugi strani pa slednja neinformirana tehnika iskanja ne uporablja znanja. Poenostavljeno pa ni nobenih dodatnih informacij o rešitvi.
  2. Učinkovitost informiranega iskanja je boljša od neinformiranega iskanja.
  3. Neinformirano iskanje porabi več časa in stroškov, saj nima nobene ideje o rešitvi v primerjavi z obveščenim iskanjem.
  4. Iskanje po globini, iskanje po širini in iskanje najnižjih stroškov so algoritmi, ki spadajo v kategorijo neinformiranega iskanja. V nasprotju s tem, informirano iskanje zajema algoritme, kot so heuristično iskanje globine, heuristično iskanje in A * iskanje.

Zaključek

Obveščeno iskanje zagotavlja smer glede rešitve, v neinformiranem iskanju pa ni nobenega predloga glede rešitve. To pomeni, da je neinformirano iskanje daljše, ko je algoritem implementiran.

Top