TechCodeview

• Hill climbing algorithm är en lokal sökalgoritm som kontinuerligt rör sig i riktning mot ökande höjd/värde för att hitta toppen av berget eller bästa lösningen på problemet. Den avslutas när den når ett toppvärde där ingen granne har ett högre värde.
• Hill climbing algoritm är en teknik som används för att optimera de matematiska problemen. Ett av de brett diskuterade exemplen på bergsklättringsalgoritmer är Traveling-salesman Problem där vi måste minimera avståndet som säljaren tillryggalägger.
• Det kallas också girigt lokalt sök eftersom det bara ser till sin goda omedelbara grannstat och inte längre än så.
• En nod för backklättringsalgoritm har två komponenter som är tillstånd och värde.
• Hill Climbing används mest när en bra heuristik finns tillgänglig.
• I den här algoritmen behöver vi inte underhålla och hantera sökträdet eller grafen eftersom den bara behåller ett enda aktuellt tillstånd.

Funktioner för bergsklättring:

Följande är några huvuddrag i Hill Climbing Algorithm:

Generera och testa variant:Hill Climbing är varianten av Generate and Test-metoden. Generera och testa metoden ger feedback som hjälper till att bestämma vilken riktning som ska röra sig i sökutrymmet.girigt tillvägagångssätt:Klätringsalgoritmsökning rör sig i den riktning som optimerar kostnaden.Ingen bakåtspårning:Den backar inte sökutrymmet, eftersom den inte kommer ihåg de tidigare tillstånden.

State-space-diagram för bergsklättring:

Landskapet tillstånd och rymd är en grafisk representation av bergsklättringsalgoritmen som visar en graf mellan olika tillstånd av algoritm och målfunktion/kostnad.

hashing i datastruktur

På Y-axeln har vi tagit funktionen som kan vara en objektiv funktion eller kostnadsfunktion, och tillståndsrum på x-axeln. Om funktionen på Y-axeln är kostnad då är målet med sökningen att hitta det globala minimum och lokalt minimum. Om Y-axelns funktion är Objektiv funktion, då är målet med sökningen att hitta det globala maximum och lokala maximum.

Olika regioner i det statliga rymdlandskapet:

Lokalt maximum: Lokalt maximum är en stat som är bättre än sina grannstater, men det finns också en annan stat som är högre än den.

Globalt maximum: Global maximum är det bästa möjliga tillståndet i statens rymdlandskap. Den har det högsta värdet av objektiv funktion.

Nuvarande tillstånd: Det är ett tillstånd i ett landskapsdiagram där en agent för närvarande är närvarande.

latex bord

Platt lokalt maximum: Det är ett platt utrymme i landskapet där alla grannstater till nuvarande stater har samma värde.

Axel: Det är en platåregion som har en uppförsbacke.

Typer av bergsklättringsalgoritm:

• Enkel bergsklättring:
• Brantaste-bestigning bergsklättring:
• Stokastisk backklättring:

1. Enkel bergsklättring:

Enkel bergsklättring är det enklaste sättet att implementera en klättringsalgoritm. Den utvärderar bara grannodstillståndet åt gången och väljer den första som optimerar nuvarande kostnad och ställer in den som ett aktuellt tillstånd . Det kontrollerar bara att det är ett efterföljande tillstånd, och om det upptäcks bättre än det nuvarande tillståndet, flytta annars i samma tillstånd. Denna algoritm har följande funktioner:

• Mindre tidskrävande
• Mindre optimal lösning och lösningen är inte garanterad

Algoritm för enkel bergsklättring:

Steg 1:Utvärdera det initiala tillståndet, om det är måltillstånd så returnera framgång och Stopp.Steg 2:Slinga Tills en lösning hittas eller det inte finns någon ny operatör kvar att ansöka om.Steg 3:Välj och tillämpa en operatör på det aktuella läget.Steg 4:Kontrollera nytt tillstånd:
1. Om det är måltillstånd, returnera framgång och sluta.
2. Annars om det är bättre än det nuvarande tillståndet, tilldela nytt tillstånd som ett aktuellt tillstånd.
3. Annars om inte bättre än det nuvarande tillståndet, återgå sedan till steg 2.
Steg 5:Utgång.

2. Brantaste bergsklättring:

Algoritmen för den brantaste uppstigningen är en variant av enkel algoritm för bergsklättring. Denna algoritm undersöker alla angränsande noder i det aktuella tillståndet och väljer en grannod som är närmast måltillståndet. Denna algoritm förbrukar mer tid eftersom den söker efter flera grannar

Algoritm för bergsklättring med brantaste stigning:

Steg 1:Utvärdera det initiala tillståndet, om det är måltillstånd, återställ sedan framgång och sluta, annars gör det nuvarande tillståndet som initialt tillstånd.Steg 2:Slinga tills en lösning hittas eller det aktuella tillståndet inte ändras.
1. Låt SUCC vara en stat så att varje efterträdare till den nuvarande staten kommer att vara bättre än den.
2. För varje operatör som gäller det aktuella tillståndet:
   1. Använd den nya operatorn och generera ett nytt tillstånd.
   2. Utvärdera det nya tillståndet.
   3. Om det är måltillstånd, returnera det och avsluta, annars jämför det med SUCC.
   4. Om det är bättre än SUCC, ställ sedan in nytt tillstånd som SUCC.
   5. Om SUCC är bättre än det nuvarande tillståndet, ställ sedan in aktuellt tillstånd till SUCC.
Steg 5:Utgång.

3. Stokastisk bergsklättring:

Stokastisk bergsklättring undersöker inte för alla sina grannar innan de flyttar. Snarare väljer denna sökalgoritm en grannod slumpmässigt och bestämmer om den ska väljas som ett aktuellt tillstånd eller undersöka ett annat tillstånd.

karta vs set

Problem med Hill Climbing Algorithm:

1. Lokalt maximum: Ett lokalt maximum är ett topptillstånd i landskapet som är bättre än var och en av dess grannstater, men det finns också en annan stat som är högre än det lokala maximum.

Lösning: Backtracking-teknik kan vara en lösning av det lokala maximum i statligt rymdlandskap. Skapa en lista över den lovande sökvägen så att algoritmen kan spåra sökutrymmet och utforska andra vägar också.

2. Platå: En platå är det platta området i sökutrymmet där alla granntillstånd i det aktuella tillståndet innehåller samma värde, eftersom denna algoritm inte hittar någon bästa riktning att röra sig. En sökning i bergsklättring kan gå förlorad i platåområdet.

Lösning: Lösningen för platån är att ta stora steg eller mycket små steg under sökandet, för att lösa problemet. Välj slumpmässigt ett tillstånd som är långt borta från det aktuella tillståndet så att det är möjligt att algoritmen kan hitta icke-platåregion.

hur man sorterar en arraylist i java

3. Åsar: En ås är en speciell form av det lokala maximumet. Den har ett område som är högre än dess omgivande områden, men har själv en sluttning och kan inte nås i ett enda drag.

Lösning: Med hjälp av dubbelriktad sökning, eller genom att röra oss i olika riktningar, kan vi förbättra detta problem.

Simulerad glödgning:

En bergsklättringsalgoritm som aldrig gör ett steg mot ett lägre värde är garanterat ofullständig eftersom den kan fastna på ett lokalt maximum. Och om algoritmen tillämpar en slumpmässig promenad, genom att flytta en efterträdare, kan den slutföra men inte effektiv. Simulerad glödgning är en algoritm som ger både effektivitet och fullständighet.

På mekanisk term Glödgning är en process för att härda en metall eller ett glas till en hög temperatur och sedan kylas ned gradvis, så att metallen kan nå ett lågenergikristallint tillstånd. Samma process används i simulerad glödgning där algoritmen väljer ett slumpmässigt drag istället för att välja det bästa draget. Om det slumpmässiga draget förbättrar tillståndet, följer det samma väg. Annars följer algoritmen vägen som har en sannolikhet på mindre än 1 eller så rör den sig nedför och väljer en annan väg.