5. Gráfkeresé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.

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.