Lokalis kereses

1.
Ebben a prezentacioban a lokalis keresesrol lesz szo.
Az eddig ismertetett keresesi algoritmusok a keresesi teret szisztematikusan tartak fel.
Ezt ugy ertek el, hogy egy vagy tobb utat memorizaltak, es ugyanugy memorizaltak hogy eddig melyik utvonalakat vizsgaltak mar ki. Amikor megtalaltak a celt, a celig vezeto ut egyben a problema megoldasa is.

2.
Szamos feladatban a celhoz vezeto ut erdektelen. Peldaul a 8 kiralyno eseteben nem fontos hogy milyen sorrendben kerultek a kiralynok a tablara, csak a vegso elrendezes a fontos.
A lokalis keresoalgoritmusok (angolul "local search"-nek nevezzuk oket), jellemzoen csak az aktualis allapotot tartjak nyilvan, es csak az adott allapot szomszedaira lepnek. A kereses soran megtett utvonalat nem taroljak. Az ilyen feladatoknal a megoldas nem egy utvonal hanem egy allapot.

3.
A lokalis keresoalgoritmusok nem szisztematikusak, de ket nagyon fontos elonnyel rendelkeznek:
 - mivel csak az adott allapotot taroljak, elenyeszo a memoriaigenyuk, altalaban konstans mennyisegu memoriara van szukseguk,
 - nagy vagy vegtelen keresesi terben elfogadhato eredmenyt adnak (ellentetben a szisztematikus keresesi algoritmusokkal).

4.
A lokalis kereses ismertetesehez eloszor meg kell ismerkednunk az allapotterfelszinnel.
Ennek a felszinnek el lehet kuloniteni nehany jellemzo pontjat. A legmagasabb pont a globalis makszimum, altalaban arra torekszunk hogy ezt megtalaljuk. A globalis makszimumnal nincs magasabb pont a gorben. 
Ezzel szemben a lokalis makszimum olyan pont amelyik a kozvetlen szomszedainal magasabb, de nem eri el a globalis makszimum magassagat. Az algoritmus sokszor eppen ezt a pontot talalja meg a globali s makszimum helyett, erre mondjuk, hogy az algoritmus beragadt egy lokalis makszimumba. Az allapotterfelszinnek van meg ket vizszintes resze is. Az egyiket vallnak nevezzuk, ra az jellemzo hogy egyik iranyba a fuggveny felfele ivel, masik iranyba pedig lefele. Az allapotter masik vizszintes reszletet fennsiknak nevezzuk, itt a szelso pontokon kivul a celfuggveny mind a ket iranyba lefele ivel.

5.
A hegymaszo kereses (angolul hill climbing) egy olyan algoritmus amelyik mindig a javulo ertekek fele halad. Ha egy fuggvenynek a makszimumat keressuk akkor ez felfele irany jelent, ha pedig egy fuggvenynek a minimumat keressuk akkor lefele iranyt jelent.
Az algoritmus akkor all le ha feler a csucsra, illetve ha a legkozelebbi kornyezeteben nincs magasabb pont. A hegymaszo kereses nem tartja nyilvan az utvonalat amelyen az adott pillanatig vegighaladt. Az algoritmus csupan egy lepest nez elore, nem tervez. 
A modszer demonstralasara ket tesztfuggvenyt fogunk hasznalni.Az elso egy szinuszfuggveny pozitiv felperiodusa, es mivel csak egy makszimuma van, a hegymaszo algoritmus ezt mindig meg fogja talalni. A masik fuggveny ennel osszetettebb, ez egy ekszponencialis gorbe amelyhez szinuszos komponenset adtunk hozza. Ennek a fuggvenynek tobb lokalis makszimuma van.
A modszer ugy mukodik, hogy veletlenszeruen kiszurunk egy pontot a fuggveny domenjebol, esleellenorizzuk, hogy jobbra vagy balra kell haladni ahhoz hogy javitsuk a fuggveny erteket. Miutan ezt meghataroztuk, az adott iranyban addig haladunk amig fel nem erunk a csucsra. Ha csak egy makszimum van mint a bal abran, akkor a szelsoerteket biztosan megtalaljuk, ha viszont tobb makszimum van, akkor ebben nem lehetunk biztosak. Ezt a gondot ujrainditassal orvosolhatjuk. Minel nagyobb az ujrainditasok szama, annal nagyobb a valoszinuseg hogy nem csak a lokalis, hanem a globalis makszimumot is megtalaljuk. A kovetkezo video a hegymaszo keresest mutatja be a ket vizsgalt peldafuggvenyen.