3.Nem informált keresések

Question 1

Mit jelent? (nem informált)

Answer 1

Csak a probléma definiálásakor megadott információkat használja fel.
-szélességi
-egyenletes költségű
-mélységi
-mélységkorlátozott
-iteratívan mélyülő mélységi keresés

Question 2

Mi a perem?

Answer 2

Egy sor adatszerkezet (Queue, FIFO) az új rákövetkezők a sor végére kerülnek a sor első eleme kerül kiterjesztésre

Szélességi keresés használja

Question 3

Lényeges különbségek a nem informált keresési módszerek között?

Answer 3

1. Keresési sorrendBFS: először a legközelebbi állapotokat vizsgálja → garantáltan megtalálja a legrövidebb utat (ha minden él azonos költségű).DFS: mélyen lemegy egy ágon → gyors lehet, de elakadhat egy végtelen útvonalon.Uniform-Cost: mindig a legkisebb költségű útvonalat vizsgálja tovább.
2. OptimalitásUniform-Cost → mindig megtalálja a legolcsóbb utat.BFS → csak akkor optimális, ha minden lépés költsége egyforma.DFS, DLS → nem garantáltan optimális.
3. MemóriahasználatDFS, DLS → kevés memóriát használ, mivel csak egy útvonalat tárol.BFS, UCS → sok memória kell, mert rengeteg állapotot tart a memóriában egyszerre.
4. Iteratív mélyítés (IDS):Kombinálja a BFS teljességét és az alacsony memóriahasználatot, mint DFS.Minden iterációban növeli a mélységkorlátot.

Question 4

Melyek a teljes fakeresési módszerek?

Answer 4

Szélességi
Egyenletes költségű
Mélység korlátozott
Iteratívan mélyülő mélységi

Question 5

Optimális fakeresési módszerek

Answer 5

-Egyenletes költségű
Mindig a legkisebb utvonal költségű csomópontot bővíti
-A*
Kombinálja az eddigi útvonal költségét és a becsült hátralévő költséget

Question 6

Nem informált keresések tárkomplexitásuk szerint.

Answer 6

1.Mélységi: bm
2.Mélységkorlátos: bl
3.Iteratív mélyítéses keresés: b*d
4.UCS: b^c
5.Szélességi: b^d

Question 7

Nem informált keresések időkomplexitás szerint

Answer 7

1.Mélységi: b^m
2.Mélység korlátos: b^I
3.Iteratív mélyítéses: b^d
4.Szélességi: b^(d+1)
4.Költség alapú: b^c

Question 8

Valós éeletben szélességi vagy iterált mélységi keresés gyorsabb

Answer 8

Iteratív mélységi keresés mivel lineáris memóriát használ akár a cacheben is elfér így rendszerint sokkal gyorsabban végez mit a többi

Question 9

Optimális gráfkeresési módszerek

Answer 9

-UCS
-A*
-

Question 10

Mikor szükséges gráfkeresést használni fakeresés helyett?

Answer 10

Amikor egy probléma állapottere tartalmaz ciklusokat vagy ismétlődő állapotokat.