Quiz 3

Question 1

[S] Az alábbi módszerek közül melyiknél változhat futás közben a globális munkaterület mérete?

• Tabu keresésnél.
• Hegymászó módszernél.
• Véletlen újra indított hegymászó módszernél.
• Szimulált hűtésnél.

Answer 1

• Tabu keresésnél.

Question 2

[M] Melyik állítás NEM igaz a lokális keresésekre az alábbiak közül?

• Az aktuális csúcs környezetéből választja az új aktuális csúcsot.
• Ezek mohó stratégiájú algoritmusok.
• Memóriája az aktuális csúcs környezetének tárolására korlátozódik.
• Csak egy lokálisan legjobb megoldást képes megtalálni.

Answer 2

• Ezek mohó stratégiájú algoritmusok.
• Csak egy lokálisan legjobb megoldást képes megtalálni.

Question 3

[M] Tekinthető-e a hegymászó módszer a tabu keresés speciális változatának?

• Igen, amennyiben a hegymászó módszer tulajdonképpen egy egyelemű tabu halmazt használ, amely az előző aktuális csúcsot tárolja csak.
• Nem, amennyiben a hegymászó módszer nem tárolja el az eddig megtalált legjobb kiértékelő függvényértékű csúcsot.
• Nem, mert a tabu keresés véletlen módon választ új csúcsot.
• Nem, mert a tabu keresés felismeri a köröket, a hegymászó algoritmus nem.

Answer 3

• Igen, amennyiben a hegymászó módszer tulajdonképpen egy egyelemű tabu halmazt használ, amely az előző aktuális csúcsot tárolja csak.
• Nem, amennyiben a hegymászó módszer nem tárolja el az eddig megtalált legjobb kiértékelő függvényértékű csúcsot.

Question 4

[S] Hány helyen használ a szimulált hűtés algoritmusa véletlenített módszert?

• Nulla. Ez ugyan egy nem-determinisztikus módszer, de nem használ véletlenítést.
• Kettő. A következő csúcs kiválasztásához, illetve annak elfogadásához.
• Három. A következő aktuális csúcs kiválasztásához, annak elfogadásához, és a hűtési ütemterv változtatásához.
• Egy. A következő aktuális csúcs kiválasztásához.

Answer 4

• Kettő. A következő csúcs kiválasztásához, illetve annak elfogadásához.

Question 5

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

• A heurisztika garantálja, hogy az algoritmus hatékonysága jobb lesz.
• A heurisztika garantálja, hogy az algoritmus az optimális megoldást találja meg.
• A heurisztika egyszerre csökkentheti az algoritmus memória igényét és a futási idejét.
• A heurisztikát a feladatot megoldó algoritmusba közvetlenül építjük be.

Answer 5

• A heurisztika egyszerre csökkentheti az algoritmus memória igényét és a futási idejét.
• A heurisztikát a feladatot megoldó algoritmusba közvetlenül építjük be.

Question 6

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

• Kicsi a memória igénye.
• Zsákutcába érve a keresés megáll.
• A tabu halmaz méretét csak kísérletezéssel lehet beállítani.
• Képes felismerni, és elkerülni a kisebb köröket.

Answer 6

• Zsákutcába érve a keresés megáll.
• A tabu halmaz méretét csak kísérletezéssel lehet beállítani.

Question 7

[M] Mely állítások NEM igazak a lokális keresésre az alábbiak közül?

• Erősen összefüggő gráfokban nem akadnak el.
• Körmentes gráfokban nem akad el.
• Kicsi memóriát használnak.
• Talál megoldást, ha van megoldás.

Answer 7

• Körmentes gráfokban nem akad el.
• Talál megoldást, ha van megoldás.

Question 8

[M] Melyek az alábbiak közül a hegymászó módszer hátrányai?

• Nem garantál optimális megoldást.
• Zsákutcába érve a keresés megáll.
• Körök mentén végtelen működésbe kezdhet.
• Kicsi a memória igénye.

Answer 8

• Nem garantál optimális megoldást.
• Zsákutcába érve a keresés megáll.
• Körök mentén végtelen működésbe kezdhet.

Question 9

[M] Hogyan hat a heurisztika információ tartalma egy kereső rendszer futási idejére?

• Nagyobb információ tartalom mellett a lépések száma csökkenhet.
• Minél nagyobb az információ tartalma, annál jobb lesz a hatékonysága.
• Minél kisebb az információ tartalma, annál gyorsabban tud új lépést választani.
• Nagyobb információ tartalom mellett egy lépés futási ideje nő.

Answer 9

• Nagyobb információ tartalom mellett a lépések száma csökkenhet.
• Minél kisebb az információ tartalma, annál gyorsabban tud új lépést választani.
• Nagyobb információ tartalom mellett egy lépés futási ideje nő.

Question 10

[M] Mely algoritmusok születtek a hegymászó módszer zsákutcában való beragadásának elkerülésére?

• Véletlen újraindított keresés (random restart search)
• Tabu keresés
• Szimulált hűtés algoritmusa
• Lokális nyaláb keresés (local beam search)

Answer 10

• Véletlen újraindított keresés (random restart search)
• Szimulált hűtés algoritmusa
• Lokális nyaláb keresés (local beam search)

Question 11

[S] Mi a lokális keresések általános vezérlési stratégiája?

• Az aktuális csúcs szomszédjai közül válasszuk a legjobb csúcsot!
• Az aktuális csúcs(ok) környezetéből válasszunk egy (vagy több) viszonylag jó csúcsot!
• Az aktuális csúcs környezetéből válasszuk a legjobb csúcsot!
• Az aktuális csúcs(ok) környezetéből válasszuk a legjobb csúcsot (csúcsokat)!

Answer 11

• Az aktuális csúcs(ok) környezetéből válasszunk egy (vagy több) viszonylag jó csúcsot!

Question 12

[S] A tabu keresésnél használt kiértékelő függvény, amellyel össze tudjuk hasonlítani az aktuális csúcs gyerekeit, heurisztikus stratégiának számít?

• Igen, ez a függvény a konkrét feladatból származik.
• Nem, mert ezt csak az olyan feladatoknál használhatjuk, amelyek állapottér modell-lel rendelkeznek. Ez tehát egy modell-függő stratégia.
• Nem, mert ilyen függvényt minden tabu keresés használ.
• A heurisztikának nincs köze a vezérlési stratégiához.

Answer 12

• Igen, ez a függvény a konkrét feladatból származik.