Worksheets6. A* algoritmus
Total questions: 15
Worksheet time: 8mins
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.
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.
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.
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.
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.
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.
Mennyi a B algoritmus kiterjesztéseinek száma legrosszabb esetben, ha a kiterjesztett csúcsok száma k?
1/2 k2
2k-1
k
k log2 k
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 nagyobb, 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.
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ö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.
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.
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.
Az alábbiak közül melyek a megengedhető gráfkereső algoritmusok?
A algoritmus
B algoritmus
Egyenletes gráfkeresés
A** algoritmus
Mely fogalmak kapcsolhatók egymáshoz a gráfkereséseknél? - mélységi gráfkeresés
nem-informált gráfkeresés
optimális megoldás
Martelli
zárt csúcsok száma
Mely fogalmak kapcsolhatók egymáshoz a gráfkereséseknél? - A* algoritmus
nem-informált gráfkeresés
optimális megoldás
Martelli
zárt csúcsok száma
Mely fogalmak kapcsolhatók egymáshoz a gráfkereséseknél? - B algoritmus
nem-informált gráfkeresés
optimális megoldás
Martelli
zárt csúcsok száma
Mely fogalmak kapcsolhatók egymáshoz a gráfkereséseknél? - memória igény
nem-informált gráfkeresés
optimális megoldás
Martelli
zárt csúcsok száma
