Mindazonáltal mind a tájékozott, mind a tájékozatlan keresési technikák között a tájékozott keresés hatékonyabb és költséghatékonyabb.
Összehasonlító táblázat
| Az összehasonlítás alapja | Informált keresés | Informálatlan keresés |
|---|---|---|
| Alapvető | A tudás segítségével megoldást talál a megoldáshoz. | Nincs tudás |
| Hatékonyság | Nagyon hatékony, mivel kevesebb időt és költséget fogyaszt. | A hatékonyság közvetítő |
| Költség | Alacsony | Összehasonlítóan magas |
| Teljesítmény | Gyorsabban talál megoldást | A sebesség lassabb, mint a tájékozott keresés |
| algoritmusok | Mélység-első keresés, széles körű keresés és a legalacsonyabb költségű első keresés | Heurisztikus mélység első és szélességi első keresés, és A * keresés |
A tájékozott keresés meghatározása
A tájékozott keresési technika kihasználja a probléma-specifikus ismereteket annak érdekében, hogy a probléma megoldására utaljon. Ez a fajta keresési stratégia valójában megakadályozza, hogy az algoritmusok megbomlódjanak a cél és a megoldás irányába. A tájékozott keresés előnyös lehet, ha a költségeket alacsonyabb keresési költségek mellett érik el.
Ahhoz, hogy egy grafikonban optimális útvonal költségeket kereshessünk a tájékozott keresési stratégia végrehajtásával, a legígéretesebb n csomópontok a h (n) heurisztikus függvénybe kerülnek. Ezután a függvény egy nem negatív valós számot ad vissza, amely az n csomóponttól a cél csomópontig számított megközelítő útköltség.
Itt az informált technika legfontosabb része a heurisztikus funkció, amely megkönnyíti a probléma további ismeretének átadását az algoritmushoz. Ennek eredményeképpen a különböző szomszédos csomópontok segítségével segít megtalálni a célt. A tájékozott keresésen alapuló különböző algoritmusok, például a heurisztikus mélység-első keresés, a heurisztikus kiterjedésű első keresés, A * keresés, stb. Most értsük meg a heurisztikus mélység-első keresést.
Heurisztikus mélység első keresés
A mélység-első keresési módszerhez hasonlóan a heurisztikus mélységben az első keresés egy utat választ, de az összes útvonalat átmásolja a kiválasztott útvonalról egy másik út kiválasztása előtt. Azonban a legjobb helyet választja helyben. Abban az esetben, ha a legkisebb heurisztikus érték a határ elsőbbsége, akkor a legjobb első keresés.
Egy másik tájékozott keresési algoritmus az A * keresés, amely egyesíti a legalacsonyabb költségű első és a legjobb első keresések fogalmát. Ez a módszer figyelembe veszi mind a pálya költségét, mind a heurisztikus információkat a kibővítendő útvonal keresésében és kiválasztásában. A becsült teljes útvonal költsége a határon a kezdőponttól a célcsomópontig elhelyezkedő egyes útvonalakhoz használt útvonalon. Ezért két funkciót használ ugyanabban az időben - a költség (p) a felfedezett út költsége, és h (p) az útvonal költségének becsült értéke a kezdő csomóponttól a célcsomópontig.
A nem informált keresés meghatározása
A nem tájékozott keresés különbözik attól, ahogyan a tájékozott keresést csak a problémameghatározás adja, hanem további lépést jelent a probléma megoldásához. Az informálatlan keresés elsődleges célja, hogy megkülönböztesse a cél- és a nem célállapotot, és teljesen figyelmen kívül hagyja azt az úticélt, amely felé az út felé halad, amíg meg nem találja a cél és a jelentések utódját. Ezt a stratégiát vakkeresésnek is nevezik.
E kategóriában különböző keresési algoritmusok találhatók, mint például a mélység-első keresés, az egységes költségkeresés, a széles körű keresés és így tovább. Most már a mélység-első keresés segítségével értsük meg az informálatlan keresés mögötti koncepciót.
Mélység első keresés
Az első keresés alapértelmezés szerint a csomópontok hozzáadásához és eltávolításához használjuk a Last in first out stacket. Egyszerre csak egy csomópont kerül hozzáadásra vagy eltávolításra, és az első elem, amelyet a verem határáról eltávolítottak, az az utolsó elem, amely hozzáadódik a veremhez. A határok eredményeinek felhasználásával az ösvények keresésében mélyen először folytatódott. Amikor egy legrövidebb és optimálisabb útvonalat keresünk mélység-első keresés segítségével, akkor a szomszédos csomópontok által létrehozott útvonal először is befejeződik, még akkor is, ha nem a kívánt. Ezután az alternatív útvonalat visszafelé keresjük.
Más szavakkal, az algoritmus minden egyes csomóponton választja ki az első alternatívát, majd visszafelé halad egy másik alternatívára, amíg az első útvonaltól nem halad át. Ez is problémát vet fel, amikor a keresés abbahagyja a grafikonban lévő végtelen ciklusok (ciklusok) miatt.
Kulcsfontosságú különbségek a tájékoztatott és a nem tudott keresés között
- A korábbi tájékozott keresési technika tudást használ a megoldás megtalálásához. Másrészt, az utóbbi nem tájékozott keresési technika nem használja a tudást. Egyszerűbb értelemben nincs további információ a megoldásról.
- A tájékozott keresés hatékonysága jobb, mint az informálatlan keresés.
- A nem tájékozott keresés több időt és költséget fogyaszt, mivel nincs tudomása a megoldásról a tájékozott kereséshez képest.
- A mélység-első keresés, a szélesség-első keresés és a legalacsonyabb költségű első keresés az algoritmusok az informálatlan keresés kategóriájába tartoznak. Ellenben a tájékozott keresés kiterjed az algoritmusokra, mint például a heurisztikus mélység-első, a heurisztikus kiterjedésű első keresés és az A * keresés.
Következtetés
A tájékozott keresés biztosítja a megoldás irányát, míg a tájékozatlan keresés során a megoldásra vonatkozóan nincs javaslat. Ezáltal az algoritmus végrehajtásakor hosszabb ideig tart az informálatlan keresés.
