Problémamegoldó ágensek, keresőalgoritmusok

Question 1

Mi a különbség az online és az offline keresések között?

Answer 1

Az offline megismeri a megoldás előtt a teljes problémát, majd a kész megoldást átvezeti az adott környezetre. pl. csukott szemmel rubik kocka kirakása
Az online problémamegoldás során a teljes tudás hiányában cselekszünk, menetközben új információkat szerzünk.

Question 2

Milyen komponensei vannak egy jól definiált problémának keresési feladatok esetén?

Answer 2

Kezdeti állapot
S(x) rákövetkező függvény
Célteszt
Útköltség

Question 3

Keresési feladat esetén hogyan adjuk meg a cselekvéseket?

Answer 3

Egy művelet/cselekvés során az egyik állapotból átkerülünk a másikba.
Megadása történhet: S(x) rákövetkező függvénnyel, amely egy állapothoz megadja, hogy milyen művelettel melyik állapotba lehet átjutni

Question 4

Mi a kapcsolat az állapottér és keresési fa között?

Answer 4

A keresési fa szisztematikusan felfedezi az állapotteret a kezdőállapotból indulva.

Question 5

Mit kell tárolni a keresési fa egy csúcsában?

Answer 5

A gyökérbe kerül a kezdőállapot, a további állapotok pedig a többi csúcsba kerülnek.
Ezek között keresünk célállapotokat.

Question 6

Mi a különbség egy állapot és egy keresési fa csúcsa között?

Answer 6

Az állapot a fizikai konfiguráció (reprezentációja) az állapotnak nincs szülője, gyereke, mélysége, útköltsége. A csomópont egy adatnyilvántartásra használt adatszerkezet, amit egy keresési fa leírására használunk. Egy állapot a világ egy konfigurációja. Így a csomópontok a SZÜLŐ- CSOMÓPONT mutatók által definiált meghatározott úton találhatók, míg az állapotok nem. Továbbá könnyen előfordulhat, hogy két különböző csomópont egyazon állapotot tartalmaz, ha ezt az állapotot két különböző cselekvéssorozattal generálták le.

Question 7

Adja meg az általános fakeresési algoritmust!

Answer 7

function Tree-Search(problem, strategy):megoldás vagy “sikertelen”
kereső fa inicializálása
loop do
if nincs kiterjeszthető csúcs

• return sikertelen

válassz a stratégia alapján egy levél csúcsot
if a csúcs célállapot

• then return kapcsolódó megoldás

else terjeszd ki a csúcsot és gyerekcsúcsokat add a keresőfához
end

Question 8

Adja meg az általános gráfkeresési algoritmust.

Answer 8

function Graph-Search(problem, fringe): megoldás vagy „sikertelen”
closed = ∅
fringe = Insert(Make-Node(Initial-State[problem]), fringe)
loop do
if fringe is empty then return „sikertelen”
node = Remove-Front(fringe)
if Goal-Test(problem, State[node]) then return node
if State[node] is not in closed then
closed += State[node]
fringe = InsertAll(Expand(node, problem), fringe)
end