MI 10 Problémareprezentáció Flashcards
(12 cards)
Mi az állapottér gráf alapú problémareprezentációban?
A csomópontok az állapotokat, az élek a műveleteket jelentik.
Milyen típusú gráfot használhatunk problémareprezentációhoz?
Irányított és akár ciklusos gráfokat.
Mitől lesz vak egy vak-keresési algoritmus?
Attól, hogy nem használnak fel semmileyen előzetes tudást a célról.
Mi jellemzi a szélességi keresést (BFS)?
FIFO sorral dolgozik, teljes és optimális, idő-/memóriaigénye O(b^d).
Mi a mélységi keresés (DFS) hátránya?
Nem teljes és nem optimális, memóriája kedvezőbb, de elakadhat mély ágon.
Mit jelent az iteratív mélyítés (IDS)?
Többször futtatott korlátozott mélységi keresés növekvő korláttal.
Mi jellemzi az egyenletes költségő keresést?
Mindig a legolcsóbb úton halad, és ha minden lépés pozitív költségű, akkor optimális.
Mi a heurisztikus függvény szerepe A* keresésnél?
Becsli a célhoz vezető költséget: f(n) = g(n) + h(n).
Mikor optimális az A* algoritmus?
Ha a heurisztikus függvény optimista, azaz nem becsli túl a költséget.
Mi a hegymászó keresés fő problémája?
Beleragadhat lokális maximumba, mivel mindig a legjobb szomszédot választja.
Mit tesz az alfa-béta metszés?
Gyorsítja a minimax algoritmust azáltal, hogy nem bővíti a felesleges ágakat.
Mi a minimax algoritmus célja?
A legrosszabb eshetőségből választani a legjobbat, feltételezve, hogy az ellenfél a legrosszabbat lépi nekünk.
