Vendar je med informiranimi in neinformiranimi tehnikami iskanja obveščeno iskanje učinkovitejše in stroškovno učinkovitejše.
Primerjalna tabela
| Podlaga za primerjavo | Informirano iskanje | Neinformirano 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ški | Nizka | Primerjalno visoka |
| Izvedba | Hitreje najde rešitev | Hitrost je počasnejša od informiranega iskanja |
| Algoritmi | Iskanje po globini, iskanje po širini in iskanje z najnižjimi stroški | Heuristič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
- 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.
- Učinkovitost informiranega iskanja je boljša od neinformiranega iskanja.
- Neinformirano iskanje porabi več časa in stroškov, saj nima nobene ideje o rešitvi v primerjavi z obveščenim iskanjem.
- 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.
