Mesterséges intelligencia keresési stratégiák

Az informált keresési stratégiák konkrét információt használnak a cél eléréséhez, míg a nem informáltak csak a keresési teret vizsgálják, anélkül hogy bármilyen hasznos információt felhasználnának.

A heurisztikus függvények olyan becslések, amelyek segítenek meghatározni, hogy egy adott állapot mennyire közelít a célhoz, és irányítják a keresési folyamatot.

A legjobb első keresési algoritmusok az UCS, greedy, és A*, mivel ezek a leginkább hatékony módon találják meg a legkisebb költségű utat a célhoz.

<p>Az autonóm robotok keresési módszereket használnak a cselekvések kiválasztására, az ütközések előrejelzésére és az utazási trajektóriák megtervezésére.</p> Signup and view all the answers

<p>További informált keresési stratégiák az IDA*, RBFS és SMA*, amelyek különböző módon kezelik a memóriahasználatot és a keresési költségeket.</p> Signup and view all the answers

<p>A konzisztens heuristika h(n) azt jelenti, hogy minden n csúcs és annak utódja n' esetén a h(n) ≤ c(n, a, n') + h(n') egyenlőség teljesül.</p> Signup and view all the answers

<p>h1 dominálja h2-t, ha h1(n) ≥ h2(n) minden n csúcsra igaz.</p> Signup and view all the answers

<p>Az A* keresés optimális megoldást garantál, ha a költség c(n) ≥ ε, ahol ε &gt; 0, és minden csúcs elágazási foka végleges.</p> Signup and view all the answers

<p>Ha h(n) konzisztens, akkor az A* keresés optimális a látogatott lista használatakor.</p> Signup and view all the answers

<p>Egy domináló heuristika alkalmazása során kevesebb csúcsot bővítünk az A* keresés során.</p> Signup and view all the answers

<p>A fő cél az, hogy három misszionárius és három kannibál átkeljen a folyón úgy, hogy a kannibálok soha ne számbelileg felülmúlják a misszionáriusokat sehol.</p> Signup and view all the answers

<p>Jó heuristikák tükrözik a problémát, mint például az Euclidean távolság vagy a megszorítások lazítása, mint az 8-puzzle esetében.</p> Signup and view all the answers

<p>A jó heuristikák megtalálása nehéz lehet, mivel implicit módon rejtőzhetnek a problémákban vagy nehezen számíthatók ki.</p> Signup and view all the answers

<p>Az effektív elágazási tényező a keresési fa elágazási sebessége, és a megoldás mélysége, valamint az előre bővített csomópontok számának függvényében számítjuk ki.</p> Signup and view all the answers

<p>A BFS stratégia 24,464 lépést igényel.</p> Signup and view all the answers

<p>A fő hátránya a memóriahasználat, mivel minden meglátogatott csomópontot rögzíteni kell.</p> Signup and view all the answers

<p>Az IDA* kontúrok alapján definiál és fokozatosan növeli a limitet, minden egyes iterációban a korábbi iterációk legkisebb f(n) értékével végzi a vágást.</p> Signup and view all the answers

<p>Az RBFS a legjobb első módszer, amely a bővített csomópontok alternatív megoldásait is tárolja és elhanyagolja a gyenge megoldásokat.</p> Signup and view all the answers

<p>A heurisztika bonyolultsága szoros kapcsolatban áll az elágazási tényezővel, mivel a gyengébb heurisztika növelheti a bővített csomópontok számát.</p> Signup and view all the answers

<p>A f(n) érték a csomópontok költségét és a heurisztikát kombinálja, hogy megtaláljuk a legjobb megoldást.</p> Signup and view all the answers

<p>Az A* keresés, h2(x) relaxációs követelményei alapján 40 lépést igényel.</p> Signup and view all the answers

<p>Az RBFS kevesebb csomópont regenerálást igényel, mivel a következő legjobb f() kontúrt tárolja, miután az utódokat már felfedezték.</p> Signup and view all the answers

<p>A tárgykorlát B a memória korlátját jelöli, amely megadja, hogy a legrosszabb levélcsomópontot el kell dobni, ha a memória megtelt.</p> Signup and view all the answers

<p>Ha B túl alacsony, akkor thrashing léphet fel, amely a jelölt csomópontok kis készletén belül folyamatos váltást okoz.</p> Signup and view all the answers

<p>Az A* kiterjesztései közé tartozik az inkrementális heurisztikus keresés, a Fringe saving A*, és a D* algoritmusok.</p> Signup and view all the answers

<p>Ezek az algoritmusok nem tudják ellenőrizni az ismétlődő állapotokat más, csak a jelenlegi úton belül.</p> Signup and view all the answers

<p>Az SMA* optimális, ha bármely optimális megoldás elérhető, és a megfelelő keresési eredményeket ad.</p> Signup and view all the answers

<p>Az 'admissible' heurisztikák garantálják, hogy ne becsüljük túl a költségeket, míg a 'consistent' heurisztikák biztosítják a költségek konzisztenzáját az útvonalak mentén.</p> Signup and view all the answers

<p>Az IDA* és RBFS algoritmusok nehezen jellemezhetők, mivel a keresési térbeli variációk és a csomópont regenerálás mértéke széles spektrumon változhat.</p> Signup and view all the answers

<p>A keresési eljárások feladata a legjobb útvonal vagy megoldás megtalálása különböző problémákban.</p> Signup and view all the answers

<p>A világ statikus, diszkretizálható és megfigyelhető, valamint az akciók determinisztikusak.</p> Signup and view all the answers

<p>A legjobb első keresés a minimális költség funkció f() alapján választja ki a csomópontokat.</p> Signup and view all the answers

<p>A felnin kívüli állapotok még nem lettek kibővítve, míg a belüli állapotokat már expandálták és értékelték.</p> Signup and view all the answers

<p>A Monte Carlo fa keresés célja a keresési mélység csökkentése és a cselekvések számának minimalizálása.</p> Signup and view all the answers

<p>A heurisztika admissible, ha soha nem becsüli túl a költséget a célcsomóponthoz vezető úton.</p> Signup and view all the answers

<p>A Greedy keresés a legkisebb heurisztikai értékű csomópontokat bővíti, míg a Uniform Cost Search a legkisebb költségű csomópontokra összpontosít.</p> Signup and view all the answers

<p>Az A* keresés az Uniform Cost Search és a Greedy Search kombinációja, amely az f(n) = g(n) + h(n) képletet használja.</p> Signup and view all the answers

<p>Ha a állapot tér végtelen, a keresés általában nem teljes, és ha a véges állapot térben a korábban látogatott állapotok nem kerülnek elvetésre, a keresés szintén nem teljes.</p> Signup and view all the answers

<p>A 'blind alley effect' akkor fordulhat elő, amikor a becslések hibásak, ami nem optimális megoldásokhoz vezethet.</p> Signup and view all the answers

<p>A Uniform Cost Search hatékony, ha az összes akció költsége pozitív és a cél az, hogy a legkisebb költséget találjuk.</p> Signup and view all the answers

<p>Heurisztikus funkciók kifejlesztéséhez használható módszer lehet a matematikai modellezés, introspekció vagy programok elemzése.</p> Signup and view all the answers

<p>Keresési heurisztikák alkalmazhatók útvonaltervezésre, csomaglogisztikára és sok más optimalizálási feladatra.</p> Signup and view all the answers

A mesterséges intelligencia (MI) egyik kulcsfontosságú eszköze, amely lehetővé teszi a szoftverek számára, hogy felfedezzék a lehetséges megoldásokat és megtalálják a legjobb útvonalat. Ez az eljárás a probléma megoldásához lépésről lépésre megvizsgálja a lehetséges megoldásokat.

A kereső algoritmusok egy csoportja, amelyek további információkat használnak a probléma megoldásához. Ezek az algoritmusok a probléma megoldásának valószínűségére alapoznak a már felfedezett információk felhasználásával.

Egy becslő függvény, amely megadja a probléma megoldásához szükséges valószínű lépések számát. A heurisztika segít az algoritmusoknak megtalálni a legjobb megoldást a lehető leggyorsabban.

Egy keresési stratégiában (pl. A* algoritmusban) a megtalált út becsült hossza

Egyfajta kereső algoritmus, amely minimalizálja a becsült költséget a kezdőponttól a célpontig. Ez a stratégiát gyakran használják a legrövidebb útvonal keresésére.

A keresési probléma megoldásához szükséges lépések sorozata.

A kereszettől még nem feldolgozott csomópontok összessége.

A keresési fa egy adott pontjának értéke, amely a ponttól a célhoz vezető optimális feltételezett költséget jelenti.

A keresési fa egy adott pontjának értéke, amely a ponttól a gyökér pontig vezető út költségét jelenti.

Azonosítja a következő feldolgozandó csomópontot, amely általában a legkisebb költségre becsült pont.

A végső megoldáshoz vezető, adott ponttól kiinduló, minimális költségű út.

Egy algoritmus, amely biztosítja, hogy minden érvényes megoldást megtalál.

Egy algoritmus, amely biztosítja, hogy az adott megoldás az adott célhoz vezető, minimális teljes költségű út.

A keresés minden pontján mindig a legkisebb g(n) értékkel rendelkező pontot választja ki feldolgozásra.

A keresés minden pontján mindig a legkisebb h(n) értékkel rendelkező pontot választja ki feldolgozásra.

A keresési fa egy pontjának értéke, amely a g(n) és h(n) értékek összegét jelenti.

A keresés minden pontján a legkisebb f(n) értékkel rendelkező pontot választja ki feldolgozásra.

A h(n) érték nem becsülheti túl az adott ponttól a célig tartó út költségét.

A keresés során újra feldolgozhatók a már látogatott csomópontok.

A keresés során a már látogatott csomópontok nem feldolgozhatók újra.

Ha egy heurisztikus függvény h(n) konzisztens (monoton), akkor minden csomópont n és minden utód csomópont n' esetén, amelyet az a akció generál, teljesül, hogy h(n) ≤ c(n, a, n') + h(n').

Ha h1(n) ≥ h2(n) minden csomópont n esetén, akkor a h1 heurisztika dominálja a h2 heurisztikát.

A* algoritmus mindig megtalálja az optimális megoldó utat (még nem-megengedett heurisztikák esetén is), ha véges számú csomópont van, ahol f(n) ≤ f*, ahol f* az optimális útvonal költsége. Ezt biztosítja, ha:

• Minden akció költség ≥ ε (valamilyen fix ε > 0 esetén), és
• Minden csomópont ágazási foka véges.

Ha h(n) megengedett heurisztika, akkor A* algoritmus optimális, anélkül hogy látogatott lista lenne.

Ha h(n) konzisztens heurisztika, akkor Az A* algoritmus optimális, látogatott listát használva.

Ha h(n) megengedett heurisztika, akkor az A* algoritmus optimálisan hatékony: adott heurisztika esetén nincs más keresési stratégia, amely kevesebb csomópontot bővít.

Ha h és h' heurisztikus függvények, és h dominálja h'-t, akkor az A* algoritmus által h heurisztikával bővített csomópontok mind bővítve lesznek A* h' használata esetén is.

A misszionáriusok és a kannibálok probléma egy klasszikus keresési probléma, amelyet a heurisztikus keresési algoritmusok illusztrálására használnak. A feladat a következő: három misszionárius és három kannibálnak át kell kelnie egy folyón, egy olyan csónakot használva, amely legfeljebb két embert szállíthat. A cél az, hogy megtalálják a műveletek sorrendjét, amely biztosítja, hogy a kannibálok soha ne túlszárnyalják a misszionáriusokat a folyó bármelyik oldalán.

A keresési fa ágainak átlagos száma egy adott szinten. Azt mutatja, hogy a keresés milyen gyorsan terjed.

Egy keresési algoritmus hatékonyságának mérése, amely számolja a megoldás elérése során kibővített csomópontok számát. Minél kisebb a szám, annál hatékonyabb a keresés.

Ha a keresési probléma bonyolultságát és a heurisztika pontosságát egyensúlyozni kell. Minél komplexebb a heurisztika, annál pontosabb lehet, de annál lassabban lehet kiszámítani.

A keresési algoritmusok egy csoportja, amelyeknek a feladata a legrövidebb vagy legköltséghatékonyabb út megtalálása.

Egy adatszerkezet, amelyben a csomópontok a g-érték (utazás költsége) és az h-érték (Becsült költség a célig) összegével vannak rendezve (f = g + h).

A mesterséges intelligencia (MI) által használt keresési technika, amely a legjobb f() értékkel rendelkező csomópontok felfedezésére összpontosít, és a következő f() kontúr vizsgálatára. Ez lehetővé teszi a megoldáshoz vezető út megtalálásának gyorsabb és hatékonyabb módját.

A RBFS a legjobb első keresési algoritmus, amely a legjobb következő f() értékkel rendelkező csomópont meglátogatására összpontosít. A kiterjesztett f() kontúrra vonatkozó eredményeket a csomópontokban tárolják, ami hatékonyabbá teszi a keresést.

A RBFS szintén szenved a csomópontújra-generálás problémájától. Az IDA* -hoz hasonlóan a RBFS sem hatékony a grafikonokon, mivel nem tudja ellenőrizni az ismétlődő állapotokat.

A SMA* egy korlátozott memóriájú A* algoritmus. A megadott memóriakorlát (B) felett a legrosszabb gyalogos csomópontot (a legalacsonyabb f() értékkel) eldobja, a csomópont értékét a szülőjének másolja.

Egy SMA* lehetővé teszi, hogy komplex problémákat oldjon meg az A*-nál. Ez nem feltétlenül talál meg minden megoldást, de képes lesz minden megtalálható megoldást megtalálni.

Az SMA* algoritmus esetén, ha a B (memóriakorlát) túl alacsony, a keresés „remegő” lehet, ami azt jelenti, hogy a keresési algoritmus a kisméretű jelölt csomópontok között szaladgál.

Az A*-hoz hasonló technika, amelyet az algoritmusok hatékonyságának növelésére használnak, ha a következő keresési problémák hasonlóak a jelenlegi keresési problémákhoz.

Az incrementális heurisztikus keresés egy speciális alkalmazása, amely a korábbi keresési eredményeket tárolja, és felhasználja azokat a következő keresés során. Ez a technika lehetővé teszi az alkalmas heurisztikák felhasználását.

Az A* algoritmusok további fejleményei, amelyek párhuzamos számítástechnikai megoldásokat használnak a komplex problémák megoldásában. A multi-core architektúrákra és a nagyon nagyméretű állapotterekre is érvényesek.