3. Lokális keresések

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

• Véletlen újra indított hegymászó módszernél

• Hegymászó módszernél

• Szimulált hűtésnél

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.

• Csak egy lokálisan legjobb megoldást képes megtalálni.

• Memóriája az aktuális csúcs környezetének tárolására korlátozódik.

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

• 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.

• 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, mert a tabu keresés felismeri a köröket, a hegymászó algoritmus nem.

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.

• Egy. A következő aktuális csúcs kiválasztásához.

• 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.

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

• A heurisztika egyszerre csökkentheti az algoritmus memória igényét és a futási idejét.

• A heurisztika garantálja, hogy az algoritmus az optimális megoldást találja meg.

• A heurisztika garantálja, hogy az algoritmus hatékonysága jobb lesz.

• A heurisztikát a feladatot megoldó algoritmusba közvetlenül építjük be.

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

• 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.

• Kicsi a memória igénye.

• Zsákutcába érve a keresés megáll.

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

• Körmentes gráfokban nem akad el.

• Kicsi memóriát használnak.

• Talál megoldást, ha van megoldás.

• Erősen összefüggő gráfokban nem akadnak el.

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

• 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.

• Nem garantál optimális megoldást.

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

• Minél nagyobb az információ tartalma, annál jobb lesz a hatékonysága.

• 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ő.

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

• Szimulált hűtés algoritmusa

• Tabu keresés

• Lokális nyaláb keresés (local beam search)

• Véletlen újraindított keresés (random restart search)