Worksheets5. Gráfkeresés
Total questions: 15
Worksheet time: 9mins
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.
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.
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.
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.
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.
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 vissza mutató pointerfüggvény által kijelölt út költségét.
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.
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.
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 vissza mutató 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.
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.
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.
Mely fogalmak kapcsolhatók egymáshoz a gráfkereséseknél? - globális munkaterület
keresőgráf
kiterjesztés
szülőcsúcs
korrektség
Mely fogalmak kapcsolhatók egymáshoz a gráfkereséseknél? - keresési szabály
keresőgráf
kiterjesztés
szülőcsúcs
korrektség
Mely fogalmak kapcsolhatók egymáshoz a gráfkereséseknél? - pointerfüggvény
keresőgráf
kiterjesztés
szülőcsúcs
korrektség
Mely fogalmak kapcsolhatók egymáshoz a gráfkereséseknél? - csökkenő kiértékelő függvény
keresőgráf
kiterjesztés
szülőcsúcs
korrektség
