Informalt keresesi modszerek

1.
Ebben az eloadasban az informalt keresesi modszerekkel fogunk megismerkedni.

2.
Az eddig ismertetett informalatlan keresesi algoritmusoknal a modszerek csak a csomopontok kifejtesi sorrendjeben kulonboztek. Ezeknek az algoritmusoknak nem voltak semmilyen informacioi arrol hogy merre keressek a megoldast, ezert gyenge volt a hatekonysaguk.
Ezzel szemben az informalt keresesi modszereknek mar van valamilyen elkepzese arrol hogy merre keressek a megoldast. Ezeket az algoritmusokat egy  heurisztikus kiertekelo fuggveny vezeti a cel fele. Ezt a fuggvenyt h betuvel jeloljuk, es az egyes csomopontok kivanatossagat, illetve minoseget jelenti a keresesi feladat ertelmeben.
Az informalt keresesi algoritmusokat ket alapveto tipusba lehet sorolni: legjobbat eloszor modszerek, es iterativ javitas. A legjobbat eloszor modszereket tovabb lehet osztani moho legjobbat eloszor keresesre es A* keresesre.
Az informalt keresesi modszereket azert hasznaljuk hogy:
- javitsuk a vak keresesi algoritmusok hatekonysagat
- csokkentsuk a feladat szamitasigenyet
- a keresest sikeresen el tudjuk vegezni korlatozott eroforrasok mellett
- figyelembe vegyuk a feladathoz kapcsolodo informaciokat
 
A heurisztika nyelvi ertelemben olyan tanacsot, szuggesztiot jelent amelyik gyakran hatekony, de nem biztos hogy minden esetben ervenyes.
Muszaki ertelemben a heurisztika egy kiertekelo fuggvenyre vonatkozik amely minden allapothoz egy szamot rendel.
A keresesnel a heurisztikus fuggveny a meg nem kifejtett csomopontokat ertekeli ki, es arra ad valaszt hogy mennyire vannak messze a celtol?
A heurisztikus fuggveny celja a feladatmegoldasra szukseges szamitasigeny csokkentese, a leheto legjobb megoldas megtalalasa amennyiben korlatozva vannak az eroforrasok, es a kompromisszum a szamitasigeny es a megoldas minosege kozott.

3.
Legjobbat eloszor kereses
Ebben az esetben egy f(n) kiertekelo fuggveny donti el, hogy melyik csomopont kerul kifejtesre.
Hagyomanyosan a legkisebb erteku csomopontot valasztjuk kifejtesre, mert a kiertekelo fuggveny a celtol valo tavolsagot  meri. Ez a modszer nem a legjobb, hanem a legjobbnak tuno csomopontot valasztja.
A legjobbat eloszor tipusu algoritmusoknak a kulcseleme egy h(n) heurisztikus kiertekelo fuggveny. A h(n) az n csomoponttol a celig vezeto ut becsult koltseget jeloli.
Ha az n allapot celallapot, akkor a h(n) heurisztikus kiertekelo fuggveny erteke 0.

4.
A legjobbat eloszor tipusu modszereknel, a perem csomopontjait sorbarakjuk, es mindig a legkivanatosabb csomopontot fejtjuk ki.
Az informalt kereses legismertebb kepviseloi moho legjobbat eloszor kereses es az A* kereses.

5.
Moho legjobbat eloszor kereses
Vizsgaljuk eloszor a moho legjobbat eloszor keresest. Ez az algoritmus eloszor azt a csomopontot fejti ki amelyiknek az allapotat a legkozelebbinek iteli meg a celallapothoz. A csomopontokat az algoritmus az f(n)=h(n) heurisztikus fuggvennyel ertekeli ki, tehat nem torodik azzal hogy eddig mekkora utat tettunk meg, a lenyeg minden lepessel minel kozelebb kerulni a celallapothoz.
Ha ez az algoritmus megradag egy utat, akkor mindig rajta marad.