Quiz 6 Flashcards
1
Q
[S] Lehet-e sorrendi heurisztika egy nem-informált gráfkeresés másodlagos vezérlési stratégiájában?
- Igen.
- Nem.
- Csak akkor, ha már az elsődleges vezérlési stratégia is alkalmaz heurisztikát.
- A másodlagos stratégiába nem lehet heurisztikát beépíteni.
A
- Igen.
2
Q
[S] Mit jelent a gráfkereséseknél a megengedhetőség fogalma?
- Olyan heurisztikus függvényt, amely alulról becsüli egy reprezentációs gráfban a csúcsokból a célba vezető optimális út költségét.
- Olyan gráfkereső algoritmust, amelyik optimális megoldást talál, ha van.
- Olyan algoritmust, amely lépésről lépésre szűkíti a megoldások halmazát, amíg az már csak az optimális megoldásokat tartalmazza.
- Olyan gráfkereséseket, amelyek kiértékelő függvényében megengedett a heurisztika használata.
A
- Olyan heurisztikus függvényt, amely alulról becsüli egy reprezentációs gráfban a csúcsokból a célba vezető optimális út költségét.
3
Q
[S] Melyik állítás NEM igaz az azonosan nulla függvényről?
- Nem válaszható kiértékelő függvénynek.
- Becsli a célba vezető optimális út költségét.
- Megengedhető és monoton megszorításos.
- Nem tartalmaz extra ismeretet, azaz heurisztikát.
A
- Nem válaszható kiértékelő függvénynek.
4
Q
[S] Melyik gráfkereső algoritmust nevezzük A* algoritmusnak?
- Amelyik kiértékelő függvénye g+h alakú, ahol h nem-negatív és megengedhető.
- Amelyik kiértékelő függvénye g+h alakú, ahol h nem-negatív, megengedhető és monoton megszorításos.
- Amelyik garantáltan optimális megoldást talál, ha van.
- Amelyik kiértékelő függvénye g+h alakú, ahol h megengedhető, és garantáltan optimális megoldást talál, ha van.
A
- Amelyik kiértékelő függvénye g+h alakú, ahol h nem-negatív és megengedhető.
5
Q
[S] Mi az alábbiak közül az A algoritmus tulajdonsága?
- 𝛿-gráfban megengedhető heurisztikával optimális megoldást talál, ha van.
- Heurisztikus függvénye megengedhető.
- 𝛿-gráfban egy csúcsot legfeljebb egyszer terjeszt ki.
- 𝛿-gráfban optimális megoldást talál, ha van.
A
- 𝛿-gráfban megengedhető heurisztikával optimális megoldást talál, ha van.
6
Q
[S] Mely állítás NEM igaz a következetes (Ac) algoritmusra?
- A kiterjesztéseinek száma akár a kiterjesztett csúcsok száma mínusz egynek a kettő hatványa is lehet.
- Egy csúcsot legfeljebb egyszer terjeszt ki.
- Amikor egy csúcsot kiterjeszt, már ismeri a start csúcsból odavezető optimális utat.
- Optimális megoldással terminál, ha van megoldás.
A
- A kiterjesztéseinek száma akár a kiterjesztett csúcsok száma mínusz egynek a kettő hatványa is lehet.
7
Q
[S] Mennyi a B algoritmus kiterjesztéseinek száma legrosszabb esetben, ha a
kiterjesztett csúcsok száma k?
- ½ k2
- 2k-1
- k
- k log2 k
A
- ½ k2
8
Q
[S] Mikor mondunk egy A* algoritmust jobban informáltnak egy másiknál?
- Ha a heurisztikus függvényének értéke a nem célcsúcsokban kisebb, mint a másik algoritmus heurisztikus függvényének értéke.
- Ha kevesebb csúcs kiterjesztése mellett terminál.
- Ha a memória igénye nem nagyobb a másikénál.
- Ha a heurisztikus függvényének értéke a nem célcsúcsokban közelebbi becslést ad, mint a másik algoritmus heurisztikus függvényének értéke.
A
- Ha a heurisztikus függvényének értéke a nem célcsúcsokban kisebb, mint a másik algoritmus heurisztikus függvényének értéke.
9
Q
[S] Mikor mondjuk a gráfkereséseknél egy heurisztikus függvényről azt, hogy monoton megszorításos?
- Ha bármelyik él költsége nagyobb-egyenlő, mint az a különbség, amit úgy kapunk, hogy az él kezdőcsúcsának függvényértékéből levonjuk a végcsúcsának függvényértékét.
- Ha a függvényt használó gráfkeresés működési grafikonja monoton növekedő.
- Ha a függvény megengedhető és nem negatív.
- Ha a függvény alulról becsüli minden csúcsban a hátralevő optimális költséget.
A
- Ha bármelyik él költsége nagyobb-egyenlő, mint az a különség, amit úgy kapunk, hogy az él kezdőcsúcsának függvényértékéből levonjuk a végcsúcsának függvényértékét.
10
Q
[M] Melyik állítás igaz az egyenletes gráfkeresésre?
- Optimális megoldást talál, ha van.
- Egy már kiterjesztett csúcshoz soha nem talál minden addiginál olcsóbb utat.
- Kiértékelő függvénye az élek élköltségeit egységnyinek tekinti.
- Dijkstra legrövidebb utak algoritmusának szinonimája.
A
- Optimális megoldást talál, ha van.
- Egy már kiterjesztett csúcshoz soha nem talál minden addiginál olcsóbb utat.
11
Q
[M] Az alábbiak közül melyek a megengedhető gráfkereső algoritmusok?
- A algoritmus
- B algoritmus
- Egyenletes gráfkeresés
- A** algoritmus
A
- A algoritmus
- B algoritmus
- Egyenletes gráfkeresés
- A** algoritmus
12
Q
[P] Mely fogalmak kapcsolhatók egymáshoz a gráfkereséseknél?
mélységi gráfkeresés zárt csúcsok száma A* algoritmus nem-informált gráfkeresés B algoritmus optimális megoldás memória igény Martelli
A
mélységi gráfkeresés nem-informált gráfkeresés A* algoritmus optimális megoldás B algoritmus Martelli memória igény zárt csúcsok száma
