• Algoritmus lezení do kopce je místní vyhledávací algoritmus, který se neustále pohybuje ve směru rostoucí nadmořské výšky/hodnoty, aby našel vrchol hory nebo nejlepší řešení problému. Ukončí se, když dosáhne špičkové hodnoty, kde žádný soused nemá vyšší hodnotu.
• Algoritmus lezení do kopce je technika, která se používá k optimalizaci matematických problémů. Jedním z široce diskutovaných příkladů algoritmu lezení do kopce je problém Traveling-Salesman, ve kterém potřebujeme minimalizovat vzdálenost, kterou obchodník urazí.
• Nazývá se také chamtivé místní vyhledávání, protože se dívá pouze na svůj dobrý bezprostřední soused a ne za ním.
• Uzel algoritmu lezení do kopce má dvě složky, kterými jsou stav a hodnota.
• Hill Climbing se většinou používá, když je k dispozici dobrá heuristika.
• V tomto algoritmu nepotřebujeme udržovat a zpracovávat vyhledávací strom nebo graf, protože zachovává pouze jeden aktuální stav.

Vlastnosti horolezectví:

Níže jsou uvedeny některé hlavní rysy Hill Climbing Algorithm:

Vygenerovat a otestovat variantu:Hill Climbing je variantou metody Generate and Test. Metoda Generate and Test vytváří zpětnou vazbu, která pomáhá rozhodnout, kterým směrem se ve vyhledávacím prostoru pohybovat.Zištný přístup:Hledání algoritmu horolezectví se pohybuje směrem, který optimalizuje náklady.Žádné zpětné sledování:Nevrací se zpět do vyhledávacího prostoru, protože si nepamatuje předchozí stavy.

Diagram stavového prostoru pro horolezectví:

Krajina stavového prostoru je grafickým znázorněním algoritmu lezení do kopce, který ukazuje graf mezi různými stavy algoritmu a cílovou funkcí/nákladem.

Na ose Y jsme vzali funkci, která může být objektivní funkcí nebo nákladovou funkcí, a stavový prostor na ose x. Pokud je funkce na ose Y nákladná, cílem hledání je najít globální minimum a lokální minimum. Pokud je funkcí osy Y objektivní funkce, pak je cílem hledání najít globální maximum a lokální maximum.

Různé regiony v krajině státního prostoru:

Místní maximum: Lokální maximum je stav, který je lepší než sousední státy, ale existuje i jiný stav, který je vyšší než on.

velikost mého monitoru

Globální maximum: Globální maximum je nejlepší možný stav krajiny stavového prostoru. Má nejvyšší hodnotu účelové funkce.

Aktuální stav: Je to stav v krajinném diagramu, kde je aktuálně přítomen agent.

Ploché místní maximum: Jde o rovinatý prostor v krajině, kde všechny sousední státy současných států mají stejnou hodnotu.

Rameno: Je to oblast náhorní plošiny, která má okraj do kopce.

metody v Javě

Typy algoritmu lezení do vrchu:

• Jednoduché lezení do kopce:
• Nejstrmější stoupání do kopce:
• Stochastické lezení do kopce:

1. Jednoduché lezení do vrchu:

Jednoduché lezení do kopce je nejjednodušší způsob, jak implementovat algoritmus lezení do kopce. Najednou vyhodnotí pouze stav sousedního uzlu a vybere první, který optimalizuje aktuální náklady, a nastaví jej jako aktuální stav . Zkontroluje pouze, že se jedná o jeden následnický stav, a pokud zjistí, že je lepší než současný stav, pak bude přesun ve stejném stavu. Tento algoritmus má následující vlastnosti:

nulová kontrola v Javě

• Méně časově náročné
• Méně optimální řešení a řešení není zaručeno

Algoritmus pro jednoduché lezení do vrchu:

Krok 1:Vyhodnoťte počáteční stav, pokud je to cílový stav, vraťte úspěch a zastavte.Krok 2:Smyčka Dokud nebude nalezeno řešení nebo nezbude žádný nový operátor, který by mohl použít.Krok 3:Vyberte a použijte operátor na aktuální stav.Krok 4:Zkontrolujte nový stav:
1. Pokud je to cílový stav, vraťte úspěch a ukončete.
2. V opačném případě, pokud je lepší než aktuální stav, přiřaďte nový stav jako aktuální.
3. Jinak, pokud ne lepší než aktuální stav, vraťte se ke kroku 2.
Krok 5:Výstup.

2. Nejstrmější stoupání do kopce:

Algoritmus nejstrmějšího stoupání je variací jednoduchého algoritmu pro lezení do kopce. Tento algoritmus prozkoumá všechny sousední uzly aktuálního stavu a vybere jeden sousední uzel, který je nejblíže cílovému stavu. Tento algoritmus spotřebovává více času, protože hledá více sousedů

Algoritmus pro lezení do kopce s nejstrmějším výstupem:

Krok 1:Vyhodnoťte počáteční stav, pokud je to cílový stav, vraťte úspěch a zastavte, jinak nastavte aktuální stav jako výchozí.Krok 2:Opakujte, dokud není nalezeno řešení nebo se aktuální stav nezmění.
1. Ať je SUCC stavem takovým, že jakýkoli nástupce současného stavu bude lepší než on.
2. Pro každý operátor, který platí pro aktuální stav:
   1. Použijte nový operátor a vygenerujte nový stav.
   2. Vyhodnoťte nový stav.
   3. Pokud je to cílový stav, vraťte jej a ukončete, jinak jej porovnejte s SUCC.
   4. Pokud je lepší než SUCC, nastavte nový stav jako SUCC.
   5. Pokud je SUCC lepší než aktuální stav, nastavte aktuální stav na SUCC.
Krok 5:Výstup.

3. Stochastické lezení do kopce:

Stochastické lezení do kopce nezkoumá před přesunem všechny sousedy. Tento vyhledávací algoritmus spíše náhodně vybere jeden sousední uzel a rozhodne, zda jej vybrat jako aktuální stav, nebo prozkoumat jiný stav.

Problémy v algoritmu horolezectví:

1. Místní maximum: Lokální maximum je vrcholový stav v krajině, který je lepší než každý z jeho sousedních států, ale existuje i jiný stav, který je vyšší než lokální maximum.

Řešení: Technika backtracking může být řešením lokálního maxima v krajině stavového prostoru. Vytvořte seznam slibných cest, aby algoritmus mohl zpětně sledovat prostor hledání a prozkoumat i jiné cesty.

2. Plošina: Plošina je plochá oblast vyhledávacího prostoru, ve které všechny sousední stavy aktuálního stavu obsahují stejnou hodnotu, protože tento algoritmus nenajde žádný nejlepší směr pohybu. Hledání horolezectví může být ztraceno v oblasti náhorní plošiny.

Řešení: Řešením pro plošinu je dělat velké nebo velmi malé kroky při hledání, abyste problém vyřešili. Náhodně vyberte stav, který je daleko od aktuálního stavu, takže je možné, že algoritmus najde oblast bez plató.

3. Hřebeny: Hřeben je zvláštní forma místního maxima. Má oblast, která je vyšší než její okolí, ale sama má sklon a nelze ji dosáhnout jediným pohybem.

tabulka popisů v mysql

Řešení: S využitím obousměrného vyhledávání nebo pohybem v různých směrech můžeme tento problém zlepšit.

Simulované žíhání:

Algoritmus pro jízdu do kopce, který nikdy neudělá pohyb směrem k nižší hodnotě, je zaručen jako neúplný, protože se může zaseknout na lokálním maximu. A pokud algoritmus použije náhodnou procházku přesunutím následníka, pak může být dokončen, ale neefektivní. Simulované žíhání je algoritmus, který přináší účinnost i úplnost.

Mechanicky řečeno Žíhání je proces kalení kovu nebo skla na vysokou teplotu a následného postupného ochlazování, takže to umožňuje kovu dosáhnout nízkoenergetického krystalického stavu. Stejný proces se používá při simulovaném žíhání, ve kterém algoritmus vybírá náhodný pohyb namísto výběru nejlepšího pohybu. Pokud náhodný pohyb zlepší stav, pak jde stejnou cestou. Jinak algoritmus sleduje cestu, která má pravděpodobnost menší než 1, nebo se pohybuje z kopce a volí jinou cestu.