Tartalom

• Összehasonlító táblázat
• Az informált keresés meghatározása
• Heurisztikus mélység első keresése
• A nem informált keresés meghatározása
• Mélység első keresése
• Következtetés

A keresés egy lépés sorozatának megkeresése, amely szükséges a problémák megoldásához. A tájékozott és a nem informált keresés közötti korábbi különbség az, hogy a tájékozott keresés útmutatást ad arra, hogy hol és hogyan lehet megtalálni a megoldást. Ezzel szemben az informálatlan keresés nem ad további információkat a problémáról, kivéve a specifikációt.

A tájékozott és a nem informált keresési technikák között azonban a tájékozott keresés hatékonyabb és költséghatékonyabb.

1. 1. Összehasonlító táblázat
   2. Meghatározás
   3. Főbb különbségek
   4. Következtetés

Összehasonlító táblázat

Az összehasonlítás alapja	Informált keresés	Tisztítatlan keresés
Alapvető	Tudást használ a megoldás lépéseinek megtalálásához.	Nincs tudás felhasználás
Hatékonyság	Nagyon hatékony, mivel kevesebb időt és költségeket igényel.	A hatékonyság meditációs
Költség	Alacsony	Viszonylag magas
Teljesítmény	Gyorsabban talál megoldást	A sebesség lassabb, mint az informált keresésnél
algoritmusok	Heurisztikus mélység első és szélesség első keresés és A * keresés	Mélység első keresés, szélesség első keresés és legalacsonyabb költségű első keresés

Az informált keresés meghatározása

A tájékozott keresési technika a probléma-specifikus ismereteket használja fel a probléma megoldásának megismerésére. Az ilyen típusú keresési stratégia valójában megakadályozza, hogy az algoritmusok megbotlakozzanak a cél és a megoldás iránya felé. Az informált keresés előnyös lehet a költség szempontjából, ha az optimálisság alacsonyabb keresési költségek mellett érhető el.

Az optimális útköltség kereséséhez egy grafikonon a tájékozott keresési stratégia végrehajtásával a legígéretesebb n csomópontokat illesztik be a h (n) heurisztikus függvénybe. Ezután a függvény egy nem-negatív valós számot ad vissza, amely az n csomóponttól a célcsomópontig kiszámított hozzávetőleges út költség.

Itt a tájékozott technika legfontosabb része a heurisztikus függvény, amely megkönnyíti a probléma további ismereteinek továbbadását az algoritmushoz. Ennek eredményeként elősegíti a célhoz vezető utat a különböző szomszédos csomópontokon keresztül. A tájékozott keresésen alapuló különféle algoritmusok léteznek, például heurisztikus mélység előtti keresés, heurisztikus szélesség első keresés, A * keresés, stb. Most értjük meg a heurisztikus mélyreható keresést.

Heurisztikus mélység első keresése

Az alábbiakban megadott mélység-keresési módszerhez hasonlóan a heurisztikus mélység-keresés egy útvonalat választ, de a kiválasztott útvonal összes útját áthaladja, mielőtt egy másik útvonalat választana. Helyi viszont megválasztja a legjobb utat. Azokban az esetekben, amikor a határ prioritása a legkisebb heurisztikus érték, akkor ezt nevezik az első legjobb keresésnek.

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 az útköltséget, mind a heurisztikus információkat a kibontandó út keresése és kiválasztása során. Becsült teljes útköltség, amelyet a határokon az elejétől a célcsomópontig tartó útvonalon használnak. Ezért két funkciót használ egyszerre - költség (p) a felfedezett út költsége, h (p) pedig a kezdő csomóponttól a cél csomópontig tartó út költségének becsült értéke.

A nem informált keresés meghatározása

A nem informált keresés abban különbözik a megalapozott kereséstől, hogy csak a probléma meghatározását biztosítja, de nem lép tovább a probléma megoldásának megtalálásában. A nem informált keresés elsődleges célja a cél- és a nem célállapot megkülönböztetése, és teljes mértékben figyelmen kívül hagyja az úton haladó rendeltetési helyet, amíg fel nem fedezi a célt, és beszámol az utódjáról. Ezt a stratégiát vak keresésnek is nevezik.

Különböző keresési algoritmusok léteznek ebben a kategóriában, mint például az első mélységű keresés, az egységes költségkeresés, az első szélességű keresés és így tovább. Most mélyebben tanulmányozzuk meg az informálatlan keresés mögött meghúzódó koncepciót.

Mélység első keresése

A mélyreható első keresés során a Last in first out verem a csomópontok hozzáadásához és eltávolításához szolgál. Egyszerre csak egy csomópontot adunk hozzá vagy távolítunk el, és a verem határából eltávolított első elem lenne az utolsó elem, amelyet hozzáadunk a veremhez. Ha a halomban verem kerül felhasználásra, az utak keresése az első mélységben folytatódik. Amikor a legrövidebb és optimális utat keresik a mélység első keresés segítségével, akkor a szomszédos csomópontok által létrehozott út először befejeződik, még akkor is, ha nem a kívánt. Ezután az alternatív utat visszakereséssel keressük.

Más szavakkal, az algoritmus minden csomóponton kiválasztja az első alternatívát, majd visszalép egy másik alternatívára, amíg az összes választási útvonalon nem halad át az első kiválasztástól. Ez egy olyan problémát vet fel, amelyben a keresés abbahagyhatja a grafikonban lévő végtelen hurkok (ciklusok) miatt.

1. A korábbi tájékozott keresési technika ismereteket használ a megoldás megtalálására. Másrészt az utóbbi nem tájékozott keresési technika nem használja a tudást. Egyszerűbben fogalmazva: a megoldásról nincs további információ.
2. A tájékozott keresés hatékonysága jobb, mint az informálatlan keresés.
3. A nem informált keresés több időt és költségeket igényel, mivel a tájékozott kereséshez viszonyítva semmit sem tud a megoldásról.
4. A mélység előtti keresés, a szélesség első keresés és a legalacsonyabb költségű első keresés az algoritmusok a nem informált keresés kategóriájába tartoznak. Ezzel szemben az informált keresés kiterjed az olyan algoritmusokra, mint a heurisztikus mélység első, a heurisztikus szélesség első keresés és az A * keresés.

Következtetés

A tájékozott keresés megadja az irányt a megoldáshoz, míg a nem informált keresés során nem adunk javaslatot a megoldásra. Ez az informálatlan keresést hosszabbá teszi az algoritmus megvalósításakor.