Informált keresések Flashcards
Melyek a legjobbat először keresés-család jellemzői?
Kiértékel egy függvényt a csúcsokon, mely a csúcs kivánatosságát becsüli meg, legkívánatosabb csúcsot terjesszük ki. Perem egy sor, mely kívánatosság szerint rendezett.
Kulcseleme a h(n) heurisztikus függvény, ahol n csomóponttól a célig vezető legolcsóbb út becsült útköltsége.
Milyen problémái vannak a mohó legjobbat először keresésnek?
Nem teljes.
A heurisztika nagyon távol lehet a valóságtól, tehát csak arra alapozni igencsak kockázatos.
Időbonyolultság O(bm), de egy jó heurisztika drámaian felgyorsíthatja.
Tárbonyolultság: O(bm), minden csúcsot a memóriában tart.
Melyek az A* keresés jellemzői?
Nem terjeszti ki az eleve drága utakat.
Kiértékelő függvény f(n) = g(n) + h(n) azaz útköltség n-ig + célig tartó becsült költség n-től
Mit jelent az elfogadható heurisztika?
Ahol a becsült útköltség n-től kisebb egyenlő mint a valós útköltség.
A becsült útköltség nemnegatív és célban pedig nulla. Légvonalban mért távolság nem becsüli felül az úton mértet.
Mit garantál az elfogadható heurisztika fakeresés esetén?
FA-KERESÉS-t használó A* algoritmus optimális, ha h(n) elfogadható.
Mit garantál az elfogadható heurisztika gráfkeresés esetén?
A GRÁF-KERESÉS-t használó A* algoritmus által kifejtett csomópontok sorozata tehát f(n)- ben nem csökkenő.
Mit jelent a konzisztens heurisztika?
Egy h(n) heurisztikus függvény konzisztens, ha minden n csomópontra és annak generált minden n’ utódcsomópontjaira az n csomóponttól elért célt becsült költsége nem lehet kisebb mint az n’-be kerülés lépésköltsége. Ez az általános háromszög egyenlőtlenség egy formája, mely azt mondja ki, hogy egy háromszög egy oldala sem lehet hosszabb mint a másik kettő összege.
Mit garantál a konzisztens heurisztika fakeresés esetén?
Optimális megoldást
Mit garantál a konzisztens heurisztika gráfkeresés esetén?
Az állapottérfelszínen a lokális maximumok, hegygerincek, és fennsíkok olyan helyek, ahonnan az algoritmus nehezen vagy egyáltalán nem képes elnavigálni. Ilyen helyeken az algoritmus beragadhat. Az algoritmus minden esetben elér egy pontot, ahonnan már nem tud továbblépni.
Miért fontos, ha egy heurisztika dominál egy másik heurisztikát?
Mivel ekkor kevesebb kiterjesztésre lesz szükség, így sokkal hasznosabb keresésre
Miért lehetnek érdekesek a relaxált problémák keresésnél?
A relaxált probléma operátoraira kevesebb megkötést teszünk, mint az eredeti problémában és kevesebb lépésre lesz szükség.
Relaxált probléma optimális költsége nem nagyobb mint az eredeti probléma megoldásának költsége.
A lokális algoritmusok miben hasonlítanak és miben térnek el a fa- és gráfkeresésektől?
Teljes állapotleírásokkal dolgoznak, de a memóriában csak csekély számú csomópontot tartanak.
- Folyamatos javítás módszere
o csak egy állapotot használunk, azon próbálunk javítani
Adja meg vázlatosan a hegymászó algoritmust!
function Hill-Climbing(problem) : lokális maximum állapot
current: csúcs
neighbor: csúcs
current := Make-Node(Initial-State[problem])
loop do
neighbor := current legnagyobb értékű rákövetkezője
if Value[neighbor] <= Value[current] then return State[current]
current:=neighbor
end
Milyen problémái vannak a hegymászó algoritmusnak?
A valós életben akár több száz dimenziós feladatokról is szó lehet, itt csupán egy dimenzióval dolgozunk, azaz y=f(x). Csak lokális maximum garantálható. Ködben nem tudjuk, hogy van e jobb érték, illetve a lokális maximum és a váll megkülönböztethetetlen ez esetben.
Mi a lényege a genetikus algoritmusnak?
A genetikus algoritmus , GA ( genetic algorithm ) a sztochasztikus nyaláb keresés egy olyan variánsa, ahol a követő állapotokat nem egy állapot módosításával, hanem két szülő állapot összekombinálásával állítjuk elő. A nyaláb kereséshez kell k véletlen módon generált állapot, ez lesz populáció. Minden állapotot 0 és 1-ből álló füzér képvisel. Egy fitness-függvénynek a jobb állapotokra magasabb értékeket kell visszaadnia.
