4.Informált keresések Flashcards
(17 cards)
Legjobbat elöszőr keresés család jellemzői?
Mindig azt a csomópontot bővítik tovább, amely a legígéretesebbnek tűnik egy adott értékfüggvény szerint.
Jellemzői:
-Prioritás sort használ, sor első eleme a legígéretesebb csomópont
-Értékfüggvény alapján dönt, ez alapján dönt
-Hearisztika használhat
Mohó legjpbbat előszőr keresés problémái:
-Nem garantált az optimalitás, csak azt nézi ilyen közel van a célhoz nem azt hogy mennyibe kerül oda kerülni
-Könnyen talál drága megoldást
-Heurisztika túlbecsülhet (hibás döntés, rossz irányba indulhat)
-Végtelen ciklusba futhat
nem teljes, nem optimális, nem veszi figyelembe a költséget
A* keresés jellemzői?
-ötlet:
Ne terjesszük azokat az utakot melyek már eleve drágák
-Kiértékelő függvény:
f(n) = g(n) + h(n)
útköltség n-ig + heurisztika
-Elfogadható heurisztikát használ
-Optimális
Tulajdonságai:
-teljes
-idő: exponenciális
-tár: minden csúcsot memóriában tart
-optimalitás: igen
Elfogadható heurisztika mit jelent?
Kiértékelő függvény adja meg hogy a csúcsok mennyire kivánatosak. Leginkább a kivánatos csúcsokat terjesztjük ki.
Mit garantál az elfogadható heurisztika fa keresés esetén?
Jó heurisztika lerövidíti a keresést.
Olyan csúcsokat nem terjesztümnk ki mely nem kívánatos.
Mit garantál az elfogadható heurisztika gráfkeresés esetén?
-Optimális megoldást
-Nem vizsgál feleslegesen drága útvonalakat
-Nem zár ki jó megoldást
Mit jelent a konzisztens heurisztika?
A heurisztika becslése nem nőhet jobban, mint amennyit ténylegesen léptünk
Ez biztosítja, hogy az f(n) = g(n) + h(n) értékek sosem csökkennek egy úton előrehaladva — innen jön a monotonitás név.
Mit garantál a konzisztens heurisztika fakeresés esetén?
-Optimális megoldást A* algoritmus esetén
Mit garantál a konzisztens heurisztika gráfkeresés esetén?
Granantálja hogy az A* gráfkeresés optimális.
Miért fontos, ha egy heurisztika dominál egy másik heurisztikát?
Fontos az A* keresés hatékonysága szempontjából.
-Jobban közelít a valódi költséghez
-Kevesebb csomópont vizsgálata
-Mindig legalább olyan hatékony mint a gyengébb
Relaxált problémák keresésnél
Melyben az operátorokra kevesebb megkötést teszünk mint az eredeti problémára.
Fontos: optimális megoldásának költsége nem nagyobb mint az eredeti 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?
Hasonlóság:
-Cél: megoldást találni
-Állapottérben keresnek
-Heurisztika használata
Különbségek (lokális 1, fa/gráf: 2)
Memória igény:
1. alacsony
2. Magas
Visszalépés:
1.Nem tartja meg a korábbi állapotokat
2.Korábbiak vissza kereshetőek
Megoldás:
1.Gyakran jó de nem feltétlenül optimális
2. Tipikusan optimális megoldást keres
Teljes:
1.Lokális optimum keresése
2.Teljes vagy részleges
Hegymászó algoritmus
function Hill-Climb(problem):
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
Hegymászó algoritmus problémái
Lokális maximum: olyan pont amelynél minden szomszéd rosszabb de nem globális max itt megakad
Sikfensík: olyan terület, ahol több szomszédnak azonos értéke van – az algoritmus nem tudja, merre lépjen, és akár végtelenül keresgélhet.
Ciklusok:
Ha nem tiltjuk, a hegymászó algoritmus visszatérhet korábbi állapotba
Genetikus algoritmus lényege
- KEzdeti populáció létrehozása
2.Fitnesz értékelés: mennyire jó a megoldás
- Kiválasztás: jobb fitnesz értékű egyedeknek nagyobb esélyük van szaporodni
4.Keresztezés: Két szülő kombinálódik
5.Mutáció: a gyermeken véletlenszerű módosítást végzünk
- ismétlés amíg elérünk egy jó megoldást vagy teljesűl egy megállási feltétel (pl.: idő vagy konvergencia)
Szimulált hűtés lényege
A lokális maximumból szabaduljunk azzal hogy rossz lépéseket is megengedünk de eek méretét és gyakoriságát sorra csökkentjük
Minimális konfliktusok algoritmusnak lényege
