Quiz 4

Question 1

[P] Mely fogalmak kapcsolhatók egymáshoz a visszalépéses keresés esetén?

globális munkaterület / sorrendi szabály
keresési szabály / mélységi korlát figyelés
másodlagos vezérlési stratégia / irányított út
második változat / visszalépés

Answer 1

globális munkaterület / irányított út
keresési szabály / visszalépés
másodlagos vezérlési stratégia / sorrendi szabály
második változat / mélységi korlát figyelés

Question 2

[S] Mit tartalmaz a visszalépéses keresések globális munkaterülete?

• Az eddig bejárt startcsúcsból kiinduló utakat azok csúcsaiból kivezető még nem vizsgált élekkel együtt.
• A reprezentációs gráfot és külön annak a startcsúcsból kiinduló egyik útját.
• Ez eddig bejárt részgráfot és külön annak a startcsúcsból kiinduló egyik útját annak csúcsaiból kivezető még nem vizsgált élekkel együtt.
• A startcsúcsból kiinduló egyik utat és annak csúcsaiból kivezető még nem vizsgált éleket.

Answer 2

• A startcsúcsból kiinduló egyik utat és annak csúcsaiból kivezető még nem vizsgált éleket.

Question 3

[S] Melyek a visszalépéses keresés keresési szabályai?

• A nyilvántartott úthoz egy újabb kivezető él hozzávétele, illetve az utolsó él elvétele.
• A nyilvántartott út kiterjesztése, illetve a visszalépés.
• A nyilvántartott út utolsó csúcsának kiterjesztése, illetve az utolsó él elvétele.
• A nyilvántartott út végcsúcsából kivezető egyik él hozzávétele az úthoz, illetve az út utolsó élének elvétele.

Answer 3

• A nyilvántartott út végcsúcsából kivezető egyik él hozzávétele az úthoz, illetve az út utolsó élének elvétele.

Question 4

[S] Mi a visszalépéses keresés általános vezérlési stratégiája?

• Zsákutcába jutva mindig a visszalépés szabályát kell választani.
• A továbblépést meghatározó sorrendi és a vágó szabályok.
• A visszalépés szabályát csak a legvégső esetben válasszuk.
• A visszalépés szabálya mindig elsőbbséget élvez a többi keresési szabállyal
  szemben.

Answer 4

• A visszalépés szabályát csak a legvégső esetben válasszuk.

Question 5

[S] Melyik állítás NEM igaz a visszalépéses keresés második változatára az alábbiak közül?

• A körfigyelés elhagyása végtelen fák esetén mindenképpen gyorsítja a megoldás megtalálását.
• A körfigyelés elhagyása kicsi mélységi korlát mellett gyorsíthatja a futási időt.
• A körfigyelés elhagyása növeli a memória igényét.
• A körfigyelés elhagyása mindenképpen gyorsítja a megoldás megtalálását.

Answer 5

• A körfigyelés elhagyása mindenképpen gyorsítja a megoldás megtalálását.

Question 6

[M] Melyek az alábbiak közül a visszalépéses keresés hátrányai?

• Ugyanazt a részgráfot többször is bejárja.
• Nehéz az implementációja.
• Nagy a memória igénye.
• Kezdetben hozott rossz döntést csak sok visszalépés árán korrigálja.

Answer 6

• Ugyanazt a részgráfot többször is bejárja.
• Kezdetben hozott rossz döntést csak sok visszalépés árán korrigálja.

Question 7

[S] Képzelje maga elé a 4-királynő probléma 2. állapottér modelljének állapotfáját. (Minden csúcsból négy él vezet ki.) Hány startcsúcsból kivezető utat vizsgál meg ebben a visszalépéses keresés második változata, ha a mélységi korlát 2?

• 8
• 16
• 20
• 21

Answer 7

• 21

Question 8

[M] Mely állítások igazak a visszalépéses keresés második változatára az alábbiak közül?

• Minden 𝛿-gráfban terminál.
• Minden 𝛿-gráfban talál megoldást, ha van.
• Minden 𝛿-gráfban talál megoldást, ha annak hossza rövidebb, mint a mélységi korlát.
• Minden 𝛿-gráfban megmutatja, hogy van-e megoldás.

Answer 8

• Minden 𝛿-gráfban terminál.
• Minden 𝛿-gráfban talál megoldást, ha annak hossza rövidebb, mint a mélységi korlát.

Question 9

[M] Mely állítások NEM igazak a visszalépéses keresés második változatára az alábbiak közül?

• A mélységi korlát figyelés önmagában is elég ahhoz, hogy garantáltan termináljon.
• A körfigyelés önmagában is elég ahhoz, hogy garantáltan termináljon.
• Képes megtalálni a legrövidebb megoldást, ha van.
• Ha van megoldás a mélységi korláton belül, akkor talál megoldást.

Answer 9

• A körfigyelés önmagában is elég ahhoz, hogy garantáltan termináljon.
• Képes megtalálni a legrövidebb megoldást, ha van.

Question 10

[M] Melyek az alábbiak közül a visszalépéses keresés előnyei?

• Ha van (mélységi korálton belül) megoldása, akkor talál egyet.
• Mindig terminál.
• Véges 𝛿-gráfban optimális megoldást talál.
• Kicsi a memória igénye.

Answer 10

• Ha van (mélységi korálton belül) megoldása, akkor talál egyet.
• Mindig terminál.
• Kicsi a memória igénye.

Question 11

[M] Mely állítások NEM igazak az alábbiak közül?

• A sorrendi és a vágó szabály egyaránt épülhet heurisztikára.
• A sorrendi szabály egy heurisztikus vezérlési stratégia.
• A mélységi korlát felfogható egy speciális vágó szabálynak.
• Vágó szabály nem alkalmazható sorrendi szabályokkal együtt.

Answer 11

• A sorrendi szabály egy heurisztikus vezérlési stratégia.
• Vágó szabály nem alkalmazható sorrendi szabályokkal együtt.

Question 12

[S] Képzelje maga elé a Hanoi tornyai probléma állapotgráfját három korong
esetén. A startcsúcsból kivezető utak közül hányat vizsgál meg a visszalépéses
keresés második változata, ha a mélységi korlát 3?

• 9
• 8
• 14
• 15

Answer 12

• 15