Nem informált keresések Flashcards
Mit jelent az, hogy vak (nem informált) keresés?
A probléma definiálásakor megadott információkat használja fel. Működésük során csak következő állapotokat generál és a cél állapotot különbözteti a többitől.
Mi a perem? Adott adatszerkezetet peremként használva milyen keresési módszereket kapunk?
A csúcsok tárolására felhasznált adatszerkezet.
Szélességi keresés (a perem az sor FIFO).
Egyenletes költségű keresés, mélységi keresést, mélységkorlátozott keresés, iteratívan mélyülő mélységi keresés (itt a perem az verem LIFO).
Adja meg a lényeges különbségeket a különféle nem informált keresési módszerek között!
- Szélességi keresés: legkisebb mélységű még ki nem terjesztett csúcsot terjeszti ki.
- Egyenletes költségű keresés: legkisebb költségű még ki nem terjesztett csúcsot terjeszti ki
- Mélységi keresés: a legmélyebb ki nem fejtett csúcsot fejti ki
- Mélységkorlátozott keresés: mélységi keresés változata, n mélységben lévő csúcsoknak nincs rákövetkezőjük
- Iteratívan mélyülő mélységi keresés: mélységkorlátozott keresés iteratív változata
Melyek a teljes fakeresési módszerek (milyen feltételek mellett)?
Kiegészítés: b – maximális elágazási faktor a kereső fában; az l mélységben lévő csúcsok (limit); d – a legkisebb költségű megoldás mélysége
- Szélességi: Ha b véges
- Egyenletes költségű: Ha az élköltségek pozitívak és nagyobbak ε-nál, és b véges
- Mélység korlátozott: Ha l >= d
- Iteratívan mélyülő mélységi: mindig
Mely fakeresési módszerek optimálisak?
Szélességi
Egyenletes költségű
Iteratívan mélyülő mélységi
Adja meg a nem informált keresési módszereket a tárkomplexitásuk szerint növekvő sorrendben!
iteratívan mélyülő mélységi: bd
mélységi korlátozott: bl
mélységi: bm
egyenletes költségű: b^(C/e)
szélességi: b^(d+1)
Adja meg a nem informált keresési módszereket az időkomplexitásuk szerint növekvő sorrendben!
mélységi korlátozott: b^l
iteratívan mélyülő mélységi: b^d
egyenletes költségű: b^(C*/e)
szélességi: b^(d+1)
mélységi: b^m
A valós életben a szélességi keresés vagy az iterált mélységi keresés ad gyorsabban eredményt?
Mivel az iteratívan mélyülő mélységi keresés lineáris memóriát használ, gyakran elég neki valamely cache is. Azaz hiába hasonló a bonyolultság, a kisebb memóriahasználat miatt gyorsabban lefut a program.
Melyek optimális gráfkeresési módszerek?
Egyenletes költségű
Szélességi
Mikor szükséges gráfkeresést használni fakeresés helyett?
Ismétlődő állapotokat tartalmazó problémák esetén a gráfkeresés hatékonyabb. A gráfkeresés az összes duplikált állapotot kiküszöböli.
