Soovitatav, 2020

Toimetaja Valik

Erinevus informeeritud ja informeerimata otsingu vahel

Otsimine on protsess, mis aitab leida mistahes probleemi lahendamiseks vajalikke samme. Eelnev erinevus teadliku ja informeerimata otsingu vahel on see, et informeeritud otsing annab juhiseid selle kohta, kus ja kuidas lahendust leida. Vastupidiselt sellele ei anna informeerimata otsing probleemi kohta täiendavat teavet, välja arvatud selle spetsifikatsioon.

Nii informeeritud kui ka informeerimata otsingutehnikate vahel on informeeritud otsing tõhusam ja kulutõhusam.

Võrdluskaart

Võrdluse alusInformeeritud otsingTeavitamata otsing
Põhiline
Kasutab teadmisi lahenduse leidmiseks.Teadmiste kasutamine puudub
Tõhusus
Väga tõhus, kuna tarbib vähem aega ja kulusid.Tõhusus on vahendaja
MaksumusMadalVõrreldes kõrge
ToimivusLeiab lahenduse kiireminiKiirus on aeglasem kui teadlik otsing
Algoritmid
Esimene otsing, laius-esimene otsing ja madalaima hinnaga esimene otsingHeuristiline sügavus esimene ja laius-esimene otsing ja A * otsing

Informeeritud otsingu määratlus

Teadliku otsingu meetod kasutab probleemi spetsiifilisi teadmisi probleemi lahendamiseks. Seda tüüpi otsingustrateegia tegelikult takistab algoritmide komistamist eesmärgi ja lahenduse suunas. Informeeritud otsing võib olla soodne kulude osas, kus optimaalsus saavutatakse madalamate otsingukuludega.

Optimaalse tee maksumuse otsimiseks graafikus teadliku otsingustrateegia rakendamisega lisatakse heuristilisele funktsioonile h (n) kõige lootustandvamad sõlmed n. Siis tagastab funktsioon mitte-negatiivse reaalarvu, mis on ligikaudne tee maksumus, mis on arvutatud sõlme n ja sihtmärkide vahel.

Siin on informeeritud tehnika kõige olulisem osa heuristiline funktsioon, mis hõlbustab probleemi täiendavate teadmiste edastamist algoritmile. Selle tulemusena aitab see leida teed viisile erinevate naabersõlmede kaudu. Teavitatud otsingul põhinevad erinevad algoritmid, nagu heuristiline sügavus-esimene otsing, heuristiline laius-esimene otsing, A * otsing jne. Nüüd mõistame heuristilist sügavust esimest otsingut.

Heuristilise sügavuse esimene otsing

Sarnaselt sügavuse esimesele otsingumeetodile, mis on toodud allpool heuristilist sügavust, valib esimene otsing tee, kuid läbib kõik teed valitud teelt enne teise tee valimist. Siiski valib see parim tee kohalikult. Juhul, kui väikseim heuristiline väärtus on piiri prioriteet, siis tuntakse seda kui esimest parimat otsingut.

Teine informeeritud otsingu algoritm on A * otsing, mis ühendab madalaima maksumusega esimese ja parima esimese otsingu kontseptsiooni. See meetod võtab arvesse nii tee maksumust kui ka heuristilist teavet laiendatava tee otsimisel ja valimisel. Hinnanguline kogumaksumus, mida kasutatakse iga piiril asuva tee alguses sihtmärgini. Seetõttu kasutab ta kahte funktsiooni samal ajal - maksumus (p) on avastatud tee maksumus ja h (p) on tee maksumuse hinnanguline väärtus alates lähtesõlmest eesmärgi sõlme.

Määratlemata otsingu määratlus

Teavitamata otsing erineb teadlikust otsimisest viisil, mis annab lihtsalt probleemi määratluse, kuid ei ole edasine samm probleemi lahenduse leidmiseks. Informeerimata otsingu esmane eesmärk on eristada siht- ja mitte-sihtriiki ning see eirab täielikult sihtpunkti, mida ta tee suunas liigub, kuni see avastab eesmärgi ja aruannete järglase. Seda strateegiat tuntakse ka pime otsinguna.

Selle kategooria all on erinevaid otsingu algoritme, näiteks sügavuse esimene otsing, ühtne kulude otsing, laius-esimene otsing jne. Mõelgem nüüd sügava esimese otsingu abil teadmata otsingu kontseptsiooni.

Esimese otsingu sügavus

Sügavamalt kasutatakse esimest otsingut, viimast esimest välja, et lisada ja eemaldada sõlmed. Ainult üks sõlme lisatakse või eemaldatakse korraga ja esimene element, mis eemaldatakse virna piirist, oleks viimane element, mis lisatakse virnale. Piiride tulemuste kasutamisel radade otsimisel toimus esmalt põhjalikult. Kui otsitakse kõige lühemat ja optimaalsemat teed sügavuse esimese otsingu abil, siis lõpeb külgnevate sõlmede loodud teekond esimesena, isegi kui see ei ole soovitud. Siis otsitakse alternatiivne tee tagurpidi abil.

Teiste sõnadega, algoritm valib iga sõlme esimese variandi, seejärel tagurdab teise alternatiivi, kuni see on läbinud kõik esimesest valikust tulenevad teed. See tõstatab ka probleemi, mille puhul otsimine võib lõpetada graafikust tulenevate lõputute silmuste (tsüklite) tõttu.

Põhilised erinevused informeeritud ja informeerimata otsingu vahel

  1. Endine informeeritud otsingu tehnika kasutab lahenduse leidmiseks teadmisi. Teisest küljest ei kasuta viimane teadmata otsingu tehnika teadmisi. Lihtsamalt ei ole lahenduse kohta täiendavat teavet.
  2. Teadliku otsingu tõhusus on parem kui teadmata otsing.
  3. Teavitamata otsing tarbib rohkem aega ja maksumust, kuna see ei ole lahenduse kohta teadlik otsinguga võrreldes.
  4. Esimene otsing, laius-esimene otsing ja madalaima hinnaga esimene otsing on algoritmid, mis kuuluvad teadmata otsingu kategooriasse. Seevastu informeeritud otsing hõlmab algoritme nagu heuristiline sügavus - esimene, heuristiline laius-esimene otsing ja A * otsing.

Järeldus

Informeeritud otsing annab lahenduse suunda, samas kui teadmata otsingus ei ole lahenduse kohta soovitusi. See muudab algoritmi rakendamisel teadmata otsingut pikemaks.

Top