• Algoritmus horolezectva je lokálny vyhľadávací algoritmus, ktorý sa neustále pohybuje v smere zväčšujúcej sa nadmorskej výšky/hodnoty, aby našiel vrchol hory alebo najlepšie riešenie problému. Skončí, keď dosiahne špičkovú hodnotu, kde žiadny sused nemá vyššiu hodnotu.
• Algoritmus horolezectva je technika, ktorá sa používa na optimalizáciu matematických problémov. Jedným zo široko diskutovaných príkladov algoritmu lezenia do kopca je problém Traveling-Salesman, v ktorom musíme minimalizovať vzdialenosť, ktorú prejde obchodník.
• Nazýva sa to aj chamtivé miestne vyhľadávanie, pretože sa zameriava len na svoj dobrý bezprostredný susedný štát a nie za ním.
• Uzol algoritmu lezenia do kopca má dve zložky, ktorými sú stav a hodnota.
• Hill Climbing sa väčšinou používa, keď je k dispozícii dobrá heuristika.
• V tomto algoritme nepotrebujeme udržiavať a spracovávať vyhľadávací strom alebo graf, pretože zachováva iba jeden aktuálny stav.

Vlastnosti horolezectva:

Nasleduje niekoľko hlavných funkcií algoritmu horolezectva:

Vygenerovať a otestovať variant:Hill Climbing je variantom metódy Generate and Test. Metóda Generate and Test vytvára spätnú väzbu, ktorá pomáha rozhodnúť, ktorým smerom sa pohybovať vo vyhľadávacom priestore.Chamtivý prístup:Hľadanie algoritmu horolezectva sa pohybuje smerom, ktorý optimalizuje náklady.Žiadne spätné sledovanie:Nevracia sa späť do vyhľadávacieho priestoru, keďže si nepamätá predchádzajúce stavy.

Diagram stavového priestoru pre horolezectvo:

Krajina stavového priestoru je grafickým znázornením algoritmu horolezectva, ktorý zobrazuje graf medzi rôznymi stavmi algoritmu a cieľovou funkciou/nákladmi.

rozdiel medzi firmou a spoločnosťou

Na osi Y sme vzali funkciu, ktorá môže byť objektívna funkcia alebo nákladová funkcia, a stavový priestor na osi x. Ak je funkcia na osi Y nákladná, cieľom vyhľadávania je nájsť globálne minimum a lokálne minimum. Ak je funkcia osi Y objektívna funkcia, potom cieľom hľadania je nájsť globálne maximum a lokálne maximum.

Rôzne regióny v krajine štátneho priestoru:

Miestne maximum: Lokálne maximum je stav, ktorý je lepší ako susedné štáty, ale existuje aj iný štát, ktorý je od neho vyšší.

Globálne maximum: Globálne maximum je najlepší možný stav krajiny štátneho priestoru. Má najvyššiu hodnotu objektívnej funkcie.

Aktuálny stav: Je to stav v krajinnom diagrame, kde sa agent momentálne nachádza.

Ploché miestne maximum: Ide o rovinatý priestor v krajine, kde všetky susedné štáty súčasných štátov majú rovnakú hodnotu.

Rameno: Je to oblasť náhornej plošiny, ktorá má okraj do kopca.

Typy algoritmu lezenia do vrchu:

• Jednoduché lezenie do kopca:
• Najstrmšie stúpanie do kopca:
• Stochastické lezenie do kopca:

1. Jednoduché lezenie do vrchu:

Jednoduché lezenie do kopca je najjednoduchší spôsob implementácie algoritmu lezenia do kopca. Naraz vyhodnotí iba stav susedného uzla a vyberie prvý, ktorý optimalizuje súčasné náklady a nastaví ho ako aktuálny stav . Skontroluje iba, že ide o jeden následnícky stav, a ak zistí, že je lepší ako súčasný stav, presunie sa inak v rovnakom stave. Tento algoritmus má nasledujúce vlastnosti:

• Menej časovo náročné
• Menej optimálne riešenie a riešenie nie je zaručené

Algoritmus pre jednoduché lezenie do vrchu:

Krok 1:Vyhodnoťte počiatočný stav, ak je to cieľový stav, vráťte úspech a zastavte.Krok 2:Slučka, kým sa nenájde riešenie alebo nezostane žiadny nový operátor, ktorý by mohol použiť.Krok 3:Vyberte a použite operátor na aktuálny stav.Krok 4:Skontrolujte nový stav:
1. Ak je to cieľový stav, potom vráťte úspech a ukončite.
2. V opačnom prípade, ak je lepší ako súčasný stav, priraďte nový stav ako aktuálny.
3. V opačnom prípade, ak nie lepšie ako súčasný stav, vráťte sa na krok 2.
Krok 5:VÝCHOD.

2. Stúpanie do kopca s najstrmším výstupom:

Algoritmus najstrmšieho stúpania je variáciou jednoduchého algoritmu lezenia do kopca. Tento algoritmus skúma všetky susedné uzly aktuálneho stavu a vyberie jeden susedný uzol, ktorý je najbližšie k cieľovému stavu. Tento algoritmus spotrebuje viac času pri hľadaní viacerých susedov

Algoritmus pre stúpanie do kopca s najstrmším výstupom:

Krok 1:Vyhodnoťte počiatočný stav, ak je to cieľový stav, vráťte úspech a zastavte, inak nastavte aktuálny stav ako počiatočný stav.Krok 2:Opakujte, kým sa nenájde riešenie alebo sa aktuálny stav nezmení.
1. SUCC nech je stav taký, že každý nástupca súčasného stavu bude lepší ako on.
2. Pre každý operátor, ktorý sa vzťahuje na aktuálny stav:
   1. Použite nový operátor a vygenerujte nový stav.
   2. Vyhodnoťte nový stav.
   3. Ak je to cieľový stav, vráťte ho a ukončite, inak ho porovnajte s SUCC.
   4. Ak je lepší ako SUCC, potom nastavte nový stav ako SUCC.
   5. Ak je SUCC lepší ako aktuálny stav, nastavte aktuálny stav na SUCC.
Krok 5:VÝCHOD.

3. Stochastické lezenie do kopca:

Stochastické lezenie do kopca neskúma všetkých svojich susedov pred presunom. Tento vyhľadávací algoritmus skôr náhodne vyberie jeden susedný uzol a rozhodne sa, či ho vybrať ako aktuálny stav alebo preskúmať iný stav.

Problémy v algoritme horolezectva:

1. Miestne maximum: Lokálne maximum je vrcholový stav v krajine, ktorý je lepší ako každý z jeho susedných štátov, ale je prítomný aj iný stav, ktorý je vyšší ako lokálne maximum.

v regexe java

Riešenie: Technika backtrackingu môže byť riešením lokálneho maxima v krajine stavového priestoru. Vytvorte zoznam sľubnej cesty, aby algoritmus mohol spätne sledovať priestor vyhľadávania a preskúmať aj iné cesty.

reťazec do dátumu

2. Plošina: Plošina je plochá oblasť vyhľadávacieho priestoru, v ktorej všetky susedné stavy aktuálneho stavu obsahujú rovnakú hodnotu, pretože tento algoritmus nenájde najlepší smer pohybu. V oblasti náhornej plošiny sa môže stratiť hľadanie horolezectva.

Riešenie: Riešením pre plató je robiť veľké alebo veľmi malé kroky pri hľadaní, aby ste problém vyriešili. Náhodne vyberte stav, ktorý je ďaleko od súčasného stavu, takže je možné, že algoritmus nájde oblasť bez plató.

3. Hrebene: Hrebeň je špeciálna forma miestneho maxima. Má plochu, ktorá je vyššia ako jej okolie, ale sama o sebe má sklon a nedá sa dosiahnuť jediným pohybom.

Riešenie: Pomocou obojsmerného vyhľadávania alebo pohybom v rôznych smeroch môžeme tento problém zlepšiť.

Simulované žíhanie:

Algoritmus horolezectva, ktorý sa nikdy nepohne smerom k nižšej hodnote, je zaručený ako neúplný, pretože sa môže zaseknúť na lokálnom maxime. A ak algoritmus použije náhodnú prechádzku, posunutím následníka, potom môže byť dokončený, ale nie efektívny. Simulované žíhanie je algoritmus, ktorý prináša účinnosť aj úplnosť.

V mechanickom zmysle Žíhanie je proces kalenia kovu alebo skla na vysokú teplotu a následného postupného ochladzovania, čo umožňuje kovu dosiahnuť kryštalický stav s nízkou energiou. Rovnaký proces sa používa pri simulovanom žíhaní, pri ktorom algoritmus vyberie náhodný pohyb namiesto výberu najlepšieho pohybu. Ak náhodný pohyb zlepší stav, potom nasleduje rovnakú cestu. V opačnom prípade algoritmus sleduje cestu, ktorá má pravdepodobnosť menšiu ako 1, alebo sa pohybuje z kopca a volí inú cestu.