Vsebina

• Primerjalna tabela
• Opredelitev informiranega iskanja
• Prvo iskanje po hevristični globini
• Opredelitev neinformiranega iskanja
• Globina prvo iskanje
• Zaključek

Iskanje je postopek iskanja zaporedja korakov, potrebnih za rešitev katere koli težave. Predhodna razlika med informiranim in neinformiranim iskanjem je, da informirano iskanje ponuja smernice, kje in kako najti rešitev. Nasprotno, neinformirano iskanje ne daje dodatnih informacij o težavi, razen njene specifikacije.

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

1. 1. Primerjalna tabela
   2. Opredelitev
   3. Ključne razlike
   4. Zaključek

Primerjalna tabela

Osnove za primerjavo	Informirano iskanje	Neinformirano iskanje
Osnovni	Uporablja znanje za iskanje korakov do rešitve.	Brez uporabe znanja
Učinkovitost	Zelo učinkovit, saj porabi manj časa in stroškov.	Učinkovitost je posredniška
Cena	Nizka	Primerjalno visoko
Izvedba	Hitro najde rešitev	Hitrost je počasnejša od informiranega iskanja
Algoritmi	Hevristična globina najprej in širina prvo iskanje in A * iskanje	Iskanje po globini, iskanje po širini in prvo iskanje z najnižjimi stroški

Opredelitev informiranega iskanja

Informirana iskalna tehnika uporablja specifično znanje o problemu, da bi namignila na rešitev problema. Ta vrsta iskalne strategije dejansko preprečuje, da bi se algoritmi spotaknili glede cilja in smeri rešitve. Informirano iskanje je lahko ugodno glede na stroške, če je optimalnost dosežena pri nižjih stroških iskanja.

Za iskanje optimalnih stroškov poti v grafikonu z izvajanjem informirane iskalne strategije so najbolj obetavna vozlišča n vstavljena v hevristično funkcijo h (n). Nato funkcija vrne negativno realno število, kar je približno strošek poti, izračunan od vozlišča n do ciljnega vozlišča.

Tu je najpomembnejši del informirane tehnike hevristična funkcija, ki omogoča, da algoritem doda dodatno znanje o problemu. Posledično pomaga pri iskanju poti do cilja skozi različna sosednja vozlišča. Obstajajo različni algoritmi, ki temeljijo na informiranem iskanju, kot so hevristično globinsko iskanje, hevristično iskanje po širini, iskanje * in podobno. Da zdaj razumemo hevristično globinsko iskanje.

Prvo iskanje po hevristični globini

Podobno kot prvi način globine iskanja, ki je pod spodnjo hevristično globino, prvo iskanje izbere pot, vendar prečka vse poti z izbrane poti, preden izbere drugo pot. Vendar pa lokalno izbere najboljšo pot. V primerih, ko je za mejo prednostna najmanjša hevristična vrednost, potem je znan kot najboljše prvo iskanje.

Drugi algoritem informiranega iskanja je iskanje *, ki združuje koncept najnižjih stroškov prvega in najboljšega prvega iskanja. Ta metoda upošteva tako ceno poti kot hevristične informacije v procesu iskanja in izbire poti, ki jo je treba razširiti. Ocenjeni skupni stroški poti, uporabljeni za vsako pot, ki prebiva na meji od začetka do ciljnega vozlišča. Zato hkrati uporablja dve funkciji - strošek (p) je strošek odkrite poti in h (p) 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 po tem, da samo poda definicijo problema, vendar ne bo nadaljeval koraka k iskanju rešitve problema. Primarni cilj neinformiranega iskanja je razlikovati med ciljnim in neciljnim stanjem in popolnoma ignorira cilj, na katerega se usmeri na poti, dokler ne odkrije cilja in poroča o nasledniku. Ta strategija je znana tudi kot slepo iskanje.

V tej kategoriji obstajajo različni algoritmi iskanja, na primer iskanje po globini, enotno iskanje po stroških, iskanje po širini in tako naprej. Naj zdaj razumemo koncept neinformiranega iskanja s pomočjo poglobljenega iskanja.

Globina prvo iskanje

Pri globinskem prvem iskanju se za dodajanje in odstranjevanje vozlišč uporablja sklad skladba Last in first out. Hkrati se doda ali odstrani samo eno vozlišče in prvi element, odstranjen iz meje sklada, bi bil zadnji element, ki je bil dodan v sklad. Z uporabo skladovnice na meji se najprej najprej globinsko iščejo poti. Kadar najdemo najkrajšo in optimalno pot s pomočjo prvega globinskega iskanja, se pot, ki jo ustvarijo sosednja vozlišča, najprej dokonča, tudi če ni želene. Nato se alternativna pot išče s povratnim sledenjem.

Z drugimi besedami, algoritem izbere prvo alternativo na vsakem vozlišču, nato pa nazaj na drugo alternativo, dokler ni prečkal vseh poti iz prve izbire. To povzroča tudi težavo, kadar se iskanje neha ustaviti zaradi neskončnih zank (ciklov) v grafu.

1. Nekdanja informirana tehnika iskanja uporablja znanje, da bi našla rešitev. Po drugi strani pa slednja neinformirana iskalna tehnika ne uporablja znanja. Preprosteje povedano, nadaljnje informacije o rešitvi niso na voljo.
2. Učinkovitost informiranega iskanja je boljša od neinformiranega iskanja.
3. Neinformirano iskanje porabi več časa in stroškov, saj v primerjavi z informiranim iskanjem nima pojma o rešitvi.
4. Iskanje po globini, prvo iskanje po širini in prvo iskanje z najnižjimi stroški so algoritmi, ki spadajo v kategorijo neinformiranega iskanja. V nasprotju s tem informirano iskanje zajema algoritme, kot so hevristična globina najprej, hevristična širina prvo iskanje in A * iskanje.

Zaključek

Informirano iskanje ponuja smer glede rešitve, medtem ko pri neinformiranem iskanju ni podanih predlogov glede rešitve. Zaradi tega je neinformirano iskanje daljše, ko se algoritem izvaja.