Quiz 5 Flashcards
1
Q
[S] Mit tartalmaz a gráfkeresés globális munkaterülete?
- A startcsúcsból kiinduló eddig felfedezett összes utat a nyílt csúcsokkal együtt.
- A reprezentációs gráfot, de külön megcímkézve benne a már bejárt csúcsokat.
- A reprezentációs gráf egy tetszőleges részgráfját.
- Csak a nyílt csúcsok halmazát.
A
- A startcsúcsból kiinduló eddig felfedezett összes utat a nyílt csúcsokkal együtt.
2
Q
[S] Melyek a gráfkeresés keresési szabályai?
- A nyílt csúcsok kiterjesztései.
- Egy újabb él hozzávétele a kereső gráf egyik csúcsához.
- A továbblépés (újabb él felfedezése) és a visszalépés.
- A továbblépés (egy csúcsból kivezető összes él felfedezése) és a visszalépés.
A
- A nyílt csúcsok kiterjesztései.
3
Q
[S] Mi a gráfkeresés általános vezérlési stratégiája?
- Minden lépésben a legígéretesebb nyílt csúcsot választja kiterjesztésre.
- A legutoljára felfedezett nyílt csúcs kiterjesztése.
- A startcsúcsból legkisebb költségű úton elérhető nyílt csúcs kiterjesztése.
- A startcsúcsból legkisebb költségű már felfedezett úton elérhető nyílt csúcs kiterjesztése.
A
- Minden lépésben a legígéretesebb nyílt csúcsot választja kiterjesztésre.
4
Q
[S] Mely csúcsokat nevezzük a gráfkereséseknél nyílt csúcsoknak?
- A keresőgráf azon csúcsait, amelyek gyermekeit még nem, vagy nem eléggé jól ismerjük, ennél fogva kiterjesztésre várnak.
- A keresőgráf azon csúcsait, amelyekből kivezető éleket még nem fedeztük fel.
- A keresőgráf azon csúcsait, amelyeket még nem terjesztettünk ki.
- A reprezentációs gráf azon csúcsait, amelyeket még nem terjesztettünk ki.
A
- A keresőgráf azon csúcsait, amelyek gyermekeit még nem, vagy nem eléggé jól ismerjük, ennél fogva kiterjesztésre várnak.
5
Q
[S] Mit mutat a gráfkereséseknél a szülőre visszamutató pointerfüggvény (𝜋)?
- A keresőgráfbeli csúcsok egyik szülőjét.
- A reprezentációs gráfbeli csúcsok legjobb szülőjét.
- A keresőgráfbeli csúcsok legjobb szülőjét.
- A reprezentációs gráfbeli csúcsok egyik szülőjét.
A
- A keresőgráfbeli csúcsok egyik szülőjét.
6
Q
[S] Mit mutat a gráfkereséseknél a költségfüggvény (g)?
- A startcsúcsból a keresőgráfbeli csúcsokhoz, a keresőgráfban vezető egyik út költségét.
- A startcsúcsból a keresőgráfbeli csúcsokhoz vezető egyik út költségét.
- A startcsúcsból a keresőgráfbeli csúcsokhoz, a keresőgráfban vezető legolcsóbb út költségét.
- A startcsúcsból a keresőgráfbeli csúcsokhoz a szülőre visszamutató pointerfüggvény által kijelölt út költségét.
A
- A startcsúcsból a keresőgráfbeli csúcsokhoz, a keresőgráfban vezető egyik út költségét.
7
Q
[S] Mikor nevezünk egy kiértékelő függvényt csökkenőnek?
- Ha egy csúcs függvényértéke soha nem nő, viszont mindig csökken valahányszor olcsóbb odavezető utat találunk hozzá.
- Ha egy csúcs értéke csak akkor változik, de akkor csökken, ha egy olcsóbb odavezető utat találunk hozzá.
- Ha egy startcsúcsból kiinduló már felfedezett út mentén a csúcsok függvényértékei monoton csökkennek.
- Ha az algoritmus által kiterjesztett csúcsok függvényértékei monoton csökkennek.
A
- Ha egy csúcs függvényértéke soha nem nő, viszont mindig csökken valahányszor olcsóbb odavezető utat találunk hozzá.
8
Q
[M] Hogyan lehet a keresőgráf korrektségét fenn tartani?
- Minden kiterjesztés után bejárjuk a kiterjesztéssel elért gyerekcsúcsok leszármazottait (ha vannak), és kijavítjuk azok korrektségét.
- Olyan kiértékelő függvényt használunk, amely kizárja, hogy egy már korábban kiterjesztett csúcshoz minden addiginál olcsóbb odavezető utat találjunk a startcsúcsból.
- Visszahelyezzük az OPEN halmazba azt a zárt csúcsot, amelyhez minden addiginél olcsóbb odavezető utat találtunk a startcsúcsból.
- Amikor egy minden addiginél olcsóbb odavezető utat találunk egy csúcshoz, akkor módosítjuk a szülőre visszamutató pointerfüggvény értékét és a költségfüggvény értékét.
A
- Minden kiterjesztés után bejárjuk a kiterjesztéssel elért gyerekcsúcsok leszármazottait (ha vannak), és kijavítjuk azok korrektségét.
- Olyan kiértékelő függvényt használunk, amely kizárja, hogy egy már korábban kiterjesztett csúcshoz minden addiginál olcsóbb odavezető utat találjunk a startcsúcsból.
9
Q
[M] Mikor mondjuk a keresőgráf egyik csúcsára, hogy korrekt?
- Ha a szülőre visszamutató pointerek a keresőgráfra nézve optimális utat jelölnek ki hozzá a startcsúcsból, és ennek az útnak a költségét mutatja a költségfüggvény.
- Ha optimális és konzisztens.
- Ha a gráfkeresés már kiterjesztette a gyerekeit is.
- Ha a költségfüggvény értéke a visszamutató pointerfüggvény által kijelölt szülő csúcsánál mért költségfüggvény értékének, és a szülőtől hozzávezető él költségének összege.
A
- Ha a szülőre visszamutató pointerek a keresőgráfra nézve optimális utat jelölnek ki hozzá a startcsúcsból, és ennek az útnak a költségét mutatja a költségfüggvény.
- Ha optimális és konzisztens.
10
Q
[M] Mely állítások igazak az alábbiak közül a gráfkeresés általános algoritmusára?
- Véges 𝛿-gráfban mindig terminál.
- Egy csúcsot legfeljebb véges sokszor terjeszt ki még végtelen nagy 𝛿-gráfok esetén is.
- Véges 𝛿-gráfban talál megoldást, ha van.
- Véges 𝛿-gráfban optimális megoldást talál, ha van megoldás.
A
- Véges 𝛿-gráfban mindig terminál.
- Egy csúcsot legfeljebb véges sokszor terjeszt ki még végtelen nagy 𝛿-gráfok esetén is.
- Véges 𝛿-gráfban talál megoldást, ha van.
11
Q
[M] Mely állítások NEM igazak az alábbiak közül a gráfkeresés általános algoritmusára?
- Körmentes 𝛿-gráfban talál megoldást, ha van.
- 𝛿-gráfban mindig terminál.
- Csökkenő kiértékelő függvényt használva soha nem terjeszt ki inkorrekt csúcsot.
- Véges 𝛿-gráfban talál megoldást, ha van.
A
- Körmentes 𝛿-gráfban talál megoldást, ha van.
- 𝛿-gráfban mindig terminál.
12
Q
[P] Mely fogalmak kapcsolhatók egymáshoz a gráfkereséseknél?
globális munkaterület szülőcsúcs keresési szabály korrektség pointer függvény keresőgráf csökkenő kiértékelő függvény kiterjesztés
A
globális munkaterület keresőgráf keresési szabály kiterjesztés pointer függvény szülőcsúcs csökkenő kiértékelő függvény korrektség
