Példa a hegymászó algoritmusra a Java-ban

1. Áttekintés

Ebben az oktatóanyagban bemutatjuk a Hegymászás algoritmust és annak megvalósítását. Megvizsgáljuk előnyeit és hiányosságait is. Mielőtt közvetlenül belevágnánk, beszéljük meg röviden a generálás és tesztelés algoritmusok megközelítését.

2. Generál és teszt algoritmus

Ez egy nagyon egyszerű technika, amely lehetővé teszi számunkra a megoldások keresésének algoritmusát:

  1. Definiálja az aktuális állapotot kezdeti állapotként
  2. Alkalmazzon minden lehetséges műveletet az aktuális állapoton, és hozzon létre egy lehetséges megoldást
  3. Hasonlítsa össze az újonnan létrehozott megoldást a cél állapotával
  4. Ha a cél megvalósul, vagy nem lehet új állapotokat létrehozni, lépjen ki. Ellenkező esetben térjen vissza a 2. lépésre

Nagyon jól működik egyszerű problémák esetén. Mivel kimerítő keresésről van szó, nem kivitelezhető annak mérlegelése, miközben nagy problémás terekkel foglalkozunk. British Museum algoritmusként is ismert (véletlenszerű felfedezéssel próbál műtárgyat találni a British Museumban).

Ez a hegymászó támadás fő gondolata a biometrikus adatok világában is. Ez a megközelítés felhasználható szintetikus biometrikus adatok előállítására.

3. Bevezetés az egyszerű hegymászó algoritmusba

Hegymászás technikában, egy domb tövéből indulva, felfelé haladunk, amíg el nem érjük a domb tetejét. Más szavakkal, kezdeti állapotból indulunk ki, és folyamatosan javítjuk a megoldást, amíg az optimális.

Ez a generálás és teszt algoritmus variációja, amely elvet minden olyan állapotot, amely nem tűnik ígéretesnek, vagy valószínűleg nem vezet a célállapotba. Az ilyen döntések meghozatalához heurisztikát (értékelési funkciót) használ, amely jelzi, hogy az aktuális állapot mennyire áll közel a célállapothoz.

Egyszerű szavakkal: Hegymászás = generálás és teszt + heurisztika

Nézzük meg a Simple Hill mászási algoritmust:

  1. Definiálja az aktuális állapotot kezdeti állapotként
  2. Hurokozzon addig, amíg a célállapotot el nem éri, vagy a jelenlegi állapotra már nem lehet több operátort alkalmazni:
    1. Művelet alkalmazása az aktuális állapotra és új állapotot kapjon
    2. Hasonlítsa össze az új állam a céllal
    3. Kilépés ha a célállapot megvalósul
    4. Értékelje az új állapotot heurisztikus funkcióval és hasonlítsa össze a jelenlegi állapottal
    5. Ha az újabb állam közelebb van a célhoz a jelenlegi állapothoz képest, frissítse az aktuális állapotot

Mint láthatjuk, iteratív fejlesztésekkel éri el a célállapotot. A Hegymászás algoritmusban a cél megtalálása egyenértékű a domb tetejének elérésével.

4. Példa

A hegymászási algoritmus tájékozott keresésként kategorizálható. Tehát bármilyen csomópont alapú keresést vagy problémát, például az n-királynők problémáját, megvalósíthatunk a használatával. A koncepció egyszerű megértéséhez egy nagyon egyszerű példát veszünk fel.

Nézzük meg az alábbi képet:

A hegymászási problémák megoldása során a legfontosabb szempont a megfelelő heurisztikus funkció kiválasztása.

Definiáljuk az ilyen függvényt h:

h (x) = +1 a tartószerkezet összes blokkjára, ha a blokk helyesen van elhelyezve, különben -1 a tartószerkezet összes blokkjára.

Itt minden blokkot helyesen hívunk, ha annak a támogatási struktúrája megegyezik a célállapotéval. A korábban tárgyalt hegymászási eljárásnak megfelelően nézzük meg az összes iterációt és heurisztikájukat a célállomás elérése érdekében:

5. Végrehajtás

Most ugyanezt a példát valósítsuk meg a Hegymászás algoritmus segítségével.

Először is szükségünk van a Állapot osztály, amely az egyes állapotokban a blokkok pozícióit képviselő halmok listáját tárolja. Emellett az adott állam heurisztikáját is tárolja:

public class Állami {privát lista állapot; magán int heurisztika; // másoló szerkesztő, beállítók és szerelők}

Szükségünk van egy olyan módszerre is, amely kiszámítja az állam heurisztikus értékét.

nyilvános int getHeuristicsValue (Lista currentState, Stack goalStateStack) {Egész heuristicValue; heuristicValue = currentState.stream () .mapToInt (verem -> {return getHeuristicsValueForStack (verem, currentState, goalStateStack);}). összeg (); return heuristicValue; } public int getHeuristicsValueForStack (Veremköteg, Lista currentState, Stack goalStateStack) {int stackHeuristics = 0; logikai isPositioneCorrect = true; int célStartIndex = 0; a (String currentBlock: verem) {if (isPositioneCorrect && currentBlock.equals (goalStateStack.get (goalStartIndex))) {stackHeuristics + = goalStartIndex; } else {stackHeuristics - = goalStartIndex; isPositioneCorrect = hamis; } goalStartIndex ++; } return stackHeurisztika; } 

Ezenkívül meg kell határoznunk olyan operátoros módszereket, amelyek új állapotot kapnak. Példaként két módszert fogunk meghatározni:

  1. Tegyen fel egy blokkot egy veremből, és tolja rá egy új veremre
  2. Tegyen ki egy blokkot egy veremből, és tolja be a többi verem egyikébe
magánállami pushElementToNewStack (List currentStackList, String block, int currentStateHeuristics, Stack goalStateStack) {Állapot newState = null; Verem newStack = új Verem (); newStack.push (blokk); currentStackList.add (newStack); int newStateHeuristics = getHeuristicsValue (currentStackList, goalStateStack); if (newStateHeuristics> currentStateHeuristics) {newState = new State (currentStackList, newStateHeuristics); } else {currentStackList.remove (newStack); } return newState; }
magánállami pushElementToExistingStacks (Stack currentStack, List currentStackList, String block, int currentStateHeuristics, Stack goalStateStack) {return currentStackList.stream () .filter (stack -> stack! = currentStack) .map (stack -> {return pushElementToStack (stack, block, currentStackList, currentStateHeuristics, goalStateStack); }) .filter (Objects :: nonNull) .findFirst () .orElse (null); } private state pushElementToStack (Veremköteg, Karakterlánc, Lista currentStackList, int currentStateHeuristics, Stack goalStateStack) {stack.push (blokk); int newStateHeuristics = getHeuristicsValue (currentStackList, goalStateStack); if (newStateHeuristics> currentStateHeuristics) {return new State (currentStackList, newStateHeuristics); } stack.pop (); return null; }

Most, hogy megvannak a segítő módszereink, írjunk egy módszert a hegymászási technika megvalósítására.

Itt, folyamatosan új állapotokat számolunk, amelyek közelebb vannak a célokhoz, mint elődeik. Addig tartjuk őket az utunkban, amíg el nem érjük a célt.

Ha nem találunk új állapotokat, az algoritmus hibaüzenettel zárul le:

public list getRouteWithHillClimbing (Verem initStateStack, Verem goalStateStack) dobja a Kivételt {// az initState példányát az initStateStack segítségével // ... List resultPath = new ArrayList (); resultPath.add (új állapot (initState)); Állapot currentState = initState; logikai noStateFound = hamis; while (! currentState.getState (). get (0) .equals (goalStateStack) || noStateFound) {noStateFound = true; State nextState = findNextState (currentState, goalStateStack); if (nextState! = null) {noStateFound = hamis; currentState = nextState; resultPath.add (új állapot (nextState)); }} return resultPath; }

Ezen felül nekünk is szükségünk van findNextState módszer, amely az összes lehetséges műveletet a jelenlegi állapotban alkalmazza a következő állapot megszerzéséhez:

public State findNextState (State currentState, Stack goalStateStack) {Lista listOfStacks = currentState.getState (); int currentStateHeuristics = currentState.getHeuristics (); return listOfStacks.stream () .map (stack -> {return ApplyOperationsOnState (listOfStacks, stack, currentStateHeuristics, goalStateStack);}) .filter (Objects :: nonNull) .findFirst () .orElse (null); } public state applicationOperationsOnState (Lista listOfStacks, Stack stack, int currentStateHeuristics, Stack goalStateStack) {State tempState; Lista tempStackList = new ArrayList (listOfStacks); Karakterlánc = verem.pop (); if (stack.size () == 0) tempStackList.remove (stack); tempState = pushElementToNewStack (tempStackList, blokk, currentStateHeuristics, goalStateStack); if (tempState == null) {tempState = pushElementToExistingStacks (verem, tempStackList, blokk, currentStateHeuristics, goalStateStack); verem.push (blokk); } return tempState; }

6. A meredekebb emelkedő dombmászó algoritmus

A meredekebb-emelkedő hegymászó algoritmus (gradiens keresés) a hegymászó algoritmus egyik változata. Könnyű módosításokkal megvalósíthatjuk egyszerű algoritmusunkban. Ebben az algoritmusban mi vegye figyelembe az összes lehetséges állapotot a jelenlegi állapotból, majd válassza ki a legjobbat utódként, ellentétben az egyszerű dombmászási technikával.

Más szavakkal, a hegymászási technika esetében bármelyik olyan államot választottuk utódnak, amely közelebb állt a célhoz, mint a jelenlegi állapot, míg a Steepest-Ascent Hill Climbing algoritmusban a legjobb utódot választjuk az összes lehetséges utód közül, majd frissítjük a jelenlegi állapot.

7. Hátrányok

A hegymászás rövidlátó technika, mivel csak az azonnali lehetőségeket értékeli. Tehát kevés olyan helyzetbe kerülhet, amelyekből nem tud további állapotokat kiválasztani. Nézzük meg ezeket az állapotokat és néhány megoldást ezekre:

  1. Helyi maximum: Ez egy olyan állapot, amely jobb, mint az összes szomszéd, de létezik egy jobb állam, amely messze van a jelenlegi állapottól; ha a helyi maximum a megoldás látótávolságán belül van, akkor az „előhegyek” néven ismert
  2. Fennsík: Ebben az állapotban minden szomszédos államnak ugyanazok a heurisztikus értékei, ezért nem világos, hogy helyi összehasonlítással válasszuk a következő állapotot
  3. Gerinc: Ez egy olyan terület, amely magasabb, mint a környező államok, de egyetlen mozdulattal nem érhető el; például négy lehetséges irányunk van a felfedezésre (É, K, NY, É), É-i irányban pedig létezik egy terület

Kevés megoldás van ezeknek a helyzeteknek a leküzdésére:

  1. Tudunk visszalép az egyik előző állapotba, és fedezze fel a többi irányt
  2. Kevés állapotot hagyhatunk ki, és a ugrás új irányokban
  3. Tudunk fedezze fel több irányt hogy kitaláljuk a helyes utat

8. Következtetés

Annak ellenére, hogy a hegymászási technika sokkal jobb, mint a kimerítő keresés, még mindig nem optimális a nagy problémás helyeken.

A globális információkat mindig heurisztikus funkciókba kódolhatjuk, hogy okosabb döntéseket hozzunk, de akkor a számítási bonyolultság sokkal nagyobb lesz, mint korábban volt.

A hegymászás algoritmusa nagyon hasznos lehet, ha más technikákkal állunk klubba. Mint mindig, az összes példa teljes kódja megtalálható a GitHub oldalon.