Príklad algoritmu horolezectva v Jave

1. Prehľad

V tomto výučbe si ukážeme algoritmus Hill-Climbing a jeho implementáciu. Pozrime sa tiež na jeho výhody a nedostatky. Pred priamym skočením doňho si krátko povieme o prístupe k algoritmom generovania a testovania.

2. Algoritmus generovania a testovania

Je to veľmi jednoduchá technika, ktorá nám umožňuje algoritmizovať hľadanie riešení:

  1. Definujte súčasný stav ako počiatočný stav
  2. Použite akúkoľvek možnú operáciu na aktuálny stav a vygenerujte možné riešenie
  3. Porovnajte novo vygenerované riešenie so stavom cieľa
  4. Ak je cieľ dosiahnutý alebo nie je možné vytvoriť nové štáty, ukončite prácu. V opačnom prípade sa vráťte ku kroku 2

Funguje veľmi dobre pri jednoduchých problémoch. Pretože ide o vyčerpávajúce hľadanie, nie je možné uvažovať o ňom pri riešení veľkých problémových priestorov. Je tiež známy ako algoritmus Britského múzea (snaží sa nájsť artefakt v Britskom múzeu náhodným skúmaním).

Je to tiež hlavná myšlienka Hill-Climbing Attack vo svete biometrie. Tento prístup možno použiť na generovanie syntetických biometrických údajov.

3. Úvod do jednoduchého algoritmu horolezectva

Pri technike lezenia do vrchu vychádzame zo základne kopca a kráčame nahor, až kým sa nedostaneme na vrchol kopca. Inými slovami, začíname s počiatočným stavom a neustále vylepšujeme riešenie, až kým nebude optimálne.

Je to variácia algoritmu generovania a testovania, ktorý zahodí všetky stavy, ktoré nevyzerajú sľubne alebo sa zdá nepravdepodobné, že by nás priviedli do cieľového stavu. Na prijímanie takýchto rozhodnutí využíva heuristiku (hodnotiaca funkcia), ktorá naznačuje, ako blízko je súčasný stav k cieľovému stavu.

Jednoduchými slovami Horolezectvo = generovanie a testovanie + heuristika

Pozrime sa na algoritmus lezenia Simple Hill:

  1. Definujte súčasný stav ako počiatočný stav
  2. Opakujte, kým sa nedosiahne cieľový stav alebo kým na aktuálny stav nebude možné použiť ďalších operátorov:
    1. Použiť operáciu na aktuálny stav a získať nový štát
    2. Porovnaj nový štát s cieľom
    3. Skončiť ak je dosiahnutý cieľový stav
    4. Vyhodnotiť nový stav s heuristickou funkciou a porovnaj to so sucasnym stavom
    5. Ak je novší štát bližšie k cieľu v porovnaní so súčasným stavom, aktualizovať súčasný stav

Ako vidíme, do cieľového stavu sa dostáva iteračnými vylepšeniami. V algoritme stúpania do kopca je nájdenie cieľa ekvivalentné dosiahnutiu vrcholu kopca.

4. Príklad

Algoritmus stúpania do vrchu možno kategorizovať ako informované vyhľadávanie. Takže môžeme pomocou neho implementovať akékoľvek uzlové vyhľadávanie alebo problémy, ako je problém n-kráľovien. Aby sme tomuto konceptu ľahko porozumeli, vezmeme si veľmi jednoduchý príklad.

Pozrime sa na obrázok nižšie:

Kľúčovým bodom pri riešení každého problému s lezením do kopca je výber vhodnej heuristickej funkcie.

Definujme takúto funkciu h:

h (x) = +1 pre všetky bloky v podpornej štruktúre, ak je blok správne umiestnený inak -1 pre všetky bloky v podpornej štruktúre.

Tu zavoláme akýkoľvek blok správne umiestnený, ak má rovnakú podpornú štruktúru ako cieľový stav. Podľa skôr diskutovaného postupu do kopca sa pozrime na všetky iterácie a ich heuristiky na dosiahnutie cieľového stavu:

5. Implementácia

Teraz poďme implementovať ten istý príklad pomocou algoritmu Hill-Climbing.

V prvom rade potrebujeme a Štát trieda, ktorá uloží zoznam stohov predstavujúcich pozície blokov v každom štáte. Uloží tiež heuristiku pre konkrétny štát:

public class State {private List štát; súkromná int heuristika; // kopírovať konštruktor, nastavovač a prijímač}

Potrebujeme tiež metódu, ktorá spočíta heuristickú hodnotu štátu.

public int getHeuristicsValue (Zoznam currentState, Stack goalStateStack) {Integer heuristicValue; heuristicValue = currentState.stream () .mapToInt (stack -> {return getHeuristicsValueForStack (stack, currentState, goalStateStack);}). sum (); return heuristicValue; } public int getHeuristicsValueForStack (zásobník, zoznam currentState, Stack goalStateStack) {int stackHeuristics = 0; boolean isPositioneCorrect = true; int goalStartIndex = 0; pre (String currentBlock: stack) {if (isPositioneCorrect && currentBlock.equals (goalStateStack.get (goalStartIndex))) {stackHeuristics + = goalStartIndex; } else {stackHeuristics - = goalStartIndex; isPositioneCorrect = false; } goalStartIndex ++; } return stackHeuristics; } 

Ďalej musíme definovať operátorské metódy, ktoré nám dajú nový stav. Pre náš príklad definujeme dve z týchto metód:

  1. Vysuňte blok zo stohu a posuňte ho na nový
  2. Vyberte blok zo stohu a zatlačte ho do jedného z ďalších stohov
private State pushElementToNewStack (Zoznam currentStackList, reťazec block, int currentStateHeuristics, Stack goalStateStack) {State newState = null; Stack newStack = nový Stack (); newStack.push (blok); currentStackList.add (newStack); int newStateHeuristics = getHeuristicsValue (currentStackList, goalStateStack); if (newStateHeuristics> currentStateHeuristics) {newState = new State (currentStackList, newStateHeuristics); } else {currentStackList.remove (newStack); } návrat newState; }
private State pushElementToExistingStacks (Stack currentStack, Zoznam 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 (zásobník, zásobník, blok currentStackList, int currentStateHeuristics, Stack goalStateStack) {stack.push (blok); int newStateHeuristics = getHeuristicsValue (currentStackList, goalStateStack); if (newStateHeuristics> currentStateHeuristics) {return new State (currentStackList, newStateHeuristics); } stack.pop (); návrat null; }

Teraz, keď máme svoje pomocné metódy, napíšeme metódu na implementáciu techniky horolezectva.

Tu, Neustále počítame nové štáty, ktoré sú bližšie k cieľom ako ich predchodcovia. Stále im ich pridávame do cesty, až kým nedosiahneme cieľ.

Ak nenájdeme žiadne nové stavy, algoritmus sa ukončí chybovou správou:

public List getRouteWithHillClimbing (Stack initStateStack, Stack goalStateStack) vyvolá výnimku {// instantiate initState s initStateStack // ... List resultPath = new ArrayList (); resultPath.add (nový štát (initState)); State currentState = initState; boolean noStateFound = false; while (! currentState.getState (). get (0) .equals (goalStateStack) || noStateFound) {noStateFound = true; State nextState = findNextState (currentState, goalStateStack); if (nextState! = null) {noStateFound = false; currentState = nextState; resultPath.add (nový štát (nextState)); }} return resultPath; }

Okrem toho potrebujeme tiež findNextState metóda, ktorá aplikuje všetky možné operácie na súčasný stav na získanie nasledujúceho stavu:

public State findNextState (State currentState, Stack goalStateStack) {Zoznam listOfStacks = currentState.getState (); int currentStateHeuristics = currentState.getHeuristics (); return listOfStacks.stream () .map (stack -> {return applyOperationsOnState (listOfStacks, stack, currentStateHeuristics, goalStateStack);}) .filter (Objects :: nonNull) .findFirst () .orElse (null); } verejný štát applyOperationsOnState (Zoznam listOfStacks, Stack stack, int currentStateHeuristics, Stack goalStateStack) {State tempState; Zoznam tempStackList = nový ArrayList (listOfStacks); Reťazcový blok = stack.pop (); if (stack.size () == 0) tempStackList.remove (zásobník); tempState = pushElementToNewStack (tempStackList, blok, currentStateHeuristics, goalStateStack); if (tempState == null) {tempState = pushElementToExistingStacks (zásobník, tempStackList, blok, currentStateHeuristics, goalStateStack); stack.push (blok); } vratit tempState; }

6. Algoritmus stúpania do kopca najstrmšieho stúpania

Algoritmus Steepest-Ascent Hill-Climbing (hľadanie gradientu) je variantom algoritmu Hill Climbing. Môžeme ho implementovať s miernymi úpravami v našom jednoduchom algoritme. V tomto algoritme sme zvážte všetky možné stavy zo súčasného stavu a potom vyberte si toho najlepšieho ako nástupcu, na rozdiel od jednoduchej techniky horolezectva.

Inými slovami, v prípade techniky horolezectva sme vybrali akýkoľvek štát ako nástupcu, ktorý bol bližšie k cieľu ako súčasný stav, zatiaľ čo v algoritme horolezeckého stúpania Steepest-Ascent zvolíme najlepšieho nástupcu spomedzi všetkých možných nástupcov a potom aktualizujeme súčasný stav.

7. Nevýhody

Hill Climbing je krátkozraká technika, pretože hodnotí iba okamžité možnosti. Môže to teda skončiť v niekoľkých situáciách, z ktorých si nebude môcť vybrať ďalšie stavy. Pozrime sa na tieto štáty a niektoré riešenia pre ne:

  1. Miestne maximum: Je to štát, ktorý je lepší ako všetci susedia, ale existuje lepší štát, ktorý je ďaleko od súčasného stavu; ak sa miestne maximum objaví na dohľad od roztoku, je známe ako „podhorie“
  2. Náhorná plošina: V tomto štáte majú všetky susedné štáty rovnaké heuristické hodnoty, takže je nejasné zvoliť ďalší štát lokálnym porovnaním.
  3. Ridge: Je to oblasť, ktorá je vyššia ako okolité štáty, ale nemožno ju dosiahnuť jediným ťahom; napríklad máme štyri možné smery na preskúmanie (S, V, Z, Z, J) a oblasť existuje v smere SV

Existuje niekoľko riešení, ako tieto situácie prekonať:

  1. Môžeme ústupok do jedného z predchádzajúcich štátov a preskúmať ďalšie smery
  2. Môžeme preskočiť niekoľko štátov a urobiť a skok v nových smeroch
  3. Môžeme preskúmať niekoľko smerov prísť na správnu cestu

8. Záver

Aj keď je technika lezenia do kopca oveľa lepšia ako vyčerpávajúce vyhľadávanie, vo veľkých problémových priestoroch stále nie je optimálna.

Globálne informácie môžeme kedykoľvek zakódovať do heuristických funkcií, aby sme mohli robiť inteligentnejšie rozhodnutia, ale potom bude výpočtová zložitosť oveľa vyššia ako predtým.

Algoritmus stúpania do kopca môže byť veľmi prospešný, ak sa spája s inými technikami. Celý kód pre všetky príklady nájdete ako vždy na serveri GitHub.


$config[zx-auto] not found$config[zx-overlay] not found