6. A* algoritmus

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 (A^c) 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?

• ¹/₂ k²

• 2^k-1

• k

• k log₂ 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.