• Algoritam za penjanje na brdo algoritam je lokalnog pretraživanja koji se neprestano kreće u smjeru povećanja nadmorske visine/vrijednosti kako bi se pronašao vrh planine ili najbolje rješenje problema. Završava kada dosegne vršnu vrijednost gdje nijedan susjed nema višu vrijednost.
• Hill climbing algoritam je tehnika koja se koristi za optimizaciju matematičkih problema. Jedan od naširoko raspravljanih primjera algoritma za penjanje na brdo je Problem trgovačkog putnika u kojem trebamo minimizirati udaljenost koju je putovao trgovački putnik.
• Naziva se i pohlepnim lokalnim pretraživanjem jer gleda samo u dobrog neposrednog susjeda, a ne dalje.
• Čvor algoritma za penjanje na brdo ima dvije komponente, a to su stanje i vrijednost.
• Hill Climbing se uglavnom koristi kada je dostupna dobra heuristika.
• U ovom algoritmu ne trebamo održavati i rukovati stablom pretraživanja ili grafikonom jer on čuva samo jedno trenutno stanje.

Značajke brdskog penjanja:

Slijede neke glavne značajke algoritma za penjanje na brdo:

Generiraj i testiraj varijantu:Hill Climbing je varijanta Generate and Test metode. Metoda Generiraj i testiraj proizvodi povratne informacije koje pomažu odlučiti u kojem se smjeru kretati u prostoru pretraživanja.Pohlepan pristup:Hill-climbing algoritam pretraživanja kreće se u smjeru koji optimizira trošak.Bez vraćanja unazad:Ne vraća se natrag u prostor pretraživanja jer ne pamti prethodna stanja.

Dijagram prostora stanja za penjanje na brdo:

Krajolik prostora stanja je grafički prikaz algoritma za penjanje na brdo koji prikazuje grafikon između različitih stanja algoritma i objektivne funkcije/troška.

Na Y-osi smo uzeli funkciju koja može biti ciljna funkcija ili troškovna funkcija, a prostor stanja na x-osi. Ako je tada funkcija na Y-osi trošak, cilj pretraživanja je pronaći globalni minimum i lokalni minimum. Ako je funkcija Y-osi objektivna funkcija, tada je cilj pretrage pronaći globalni maksimum i lokalni maksimum.

Različite regije u krajoliku državnog prostora:

Lokalni maksimum: Lokalni maksimum je stanje koje je bolje od susjednih stanja, ali postoji i drugo stanje koje je više od njega.

java pretvara char u niz

Globalni maksimum: Globalni maksimum je najbolje moguće stanje krajolika državnog prostora. Ima najveću vrijednost objektivne funkcije.

Trenutna država: To je stanje u pejzažnom dijagramu u kojem je agent trenutno prisutan.

Ravni lokalni maksimum: To je ravan prostor u krajoliku gdje sve susjedne države sadašnjih država imaju istu vrijednost.

Rame: To je visoravan s uzbrdicom.

Vrste algoritama za penjanje uzbrdo:

• Jednostavno penjanje na brdo:
• Najstrmiji uspon na brdo:
• Stohastičko penjanje na brdo:

1. Jednostavno penjanje na brdo:

Jednostavno penjanje uz brdo najjednostavniji je način implementacije algoritma za penjanje uz brdo. Procjenjuje samo stanje susjednog čvora odjednom i odabire prvi koji optimizira trenutni trošak i postavlja ga kao trenutno stanje . Provjerava samo jedno stanje nasljednika, a ako pronađe bolje od trenutnog stanja, premjestiti se ili biti u istom stanju. Ovaj algoritam ima sljedeće značajke:

• Oduzima manje vremena
• Manje optimalno rješenje i rješenje nije zajamčeno

Algoritam za jednostavno penjanje uz brdo:

Korak 1:Procijenite početno stanje, ako je ciljno stanje, vratite uspjeh i Stop.Korak 2:Petlja Dok se ne pronađe rješenje ili ne preostane novi operator za primjenu.Korak 3:Odaberite i primijenite operator na trenutno stanje.Korak 4:Provjerite novo stanje:
1. Ako je ciljno stanje, vratite uspjeh i odustanite.
2. Inače, ako je bolje od trenutnog stanja, dodijelite novo stanje kao trenutno stanje.
3. Inače, ako ne i bolje od trenutnog stanja, vratite se na korak 2.
Korak 5:Izlaz.

2. Najstrmiji uspon na brdo:

Algoritam za najstrmiji uspon je varijacija jednostavnog algoritma za penjanje na brdo. Ovaj algoritam ispituje sve susjedne čvorove trenutnog stanja i odabire jedan susjedni čvor koji je najbliži ciljnom stanju. Ovaj algoritam troši više vremena jer traži više susjeda

Algoritam za najstrmiji uspon na brdo:

Korak 1:Procijenite početno stanje, ako je ciljno stanje, vratite uspjeh i zaustavite, inače postavite trenutno stanje kao početno stanje.Korak 2:Vrti se u petlju dok se ne pronađe rješenje ili se trenutno stanje ne promijeni.
1. Neka SUCC bude takva država da će svaki nasljednik sadašnje države biti bolji od nje.
2. Za svaki operator koji se odnosi na trenutno stanje:
   1. Primijenite novi operator i generirajte novo stanje.
   2. Procijenite novo stanje.
   3. Ako je ciljno stanje, vratite ga i zatvorite, inače ga usporedite sa SUCC-om.
   4. Ako je bolje od SUCC, tada postavite novo stanje kao SUCC.
   5. Ako je SUCC bolji od trenutnog stanja, postavite trenutno stanje na SUCC.
Korak 5:Izlaz.

3. Stohastičko penjanje na brdo:

Stohastičko penjanje na brdo ne ispituje sve svoje susjede prije kretanja. Umjesto toga, ovaj algoritam pretraživanja nasumično odabire jedan susjedni čvor i odlučuje hoće li ga odabrati kao trenutno stanje ili ispitati drugo stanje.

Problemi u algoritmu za penjanje uzbrdo:

1. Lokalni maksimum: Lokalni maksimum je vršno stanje u krajoliku koje je bolje od svakog od njegovih susjednih stanja, ali postoji i drugo stanje koje je više od lokalnog maksimuma.

Riješenje: Backtracking tehnika može biti rješenje lokalnog maksimuma u krajoliku državnog prostora. Napravite popis obećavajućih staza tako da algoritam može vratiti unatrag prostor pretraživanja i istražiti i druge staze.

2. Plato: Plato je ravno područje prostora pretraživanja u kojem sva susjedna stanja trenutnog stanja sadrže istu vrijednost, jer ovaj algoritam ne pronalazi najbolji smjer za kretanje. Pretraživanje na brdima moglo bi se izgubiti u području visoravni.

Riješenje: Rješenje za plato je poduzeti velike ili vrlo male korake dok tražite, kako biste riješili problem. Nasumično odaberite stanje koje je daleko od trenutnog stanja tako da je moguće da bi algoritam mogao pronaći područje bez platoa.

3. Grebeni: Greben je poseban oblik lokalnog maksimuma. Ima područje koje je više od okolnih područja, ali samo po sebi ima padinu i ne može se dosegnuti jednim potezom.

Riješenje: Uz korištenje dvosmjernog pretraživanja ili kretanjem u različitim smjerovima, možemo poboljšati ovaj problem.

Simulirano žarenje:

Algoritam uspona koji se nikad ne pomakne prema nižoj vrijednosti zajamčeno je nepotpun jer može zapeti na lokalnom maksimumu. A ako algoritam primijeni slučajni hod, pomicanjem nasljednika, tada može biti dovršen, ali ne i učinkovit. Simulirano žarenje je algoritam koji daje učinkovitost i cjelovitost.

U mehaničkom smislu Žarenje je proces otvrdnjavanja metala ili stakla na visoku temperaturu, a zatim postupnog hlađenja, što omogućuje metalu da postigne niskoenergetsko kristalno stanje. Isti se postupak koristi u simuliranom žarenju u kojem algoritam odabire nasumični potez umjesto odabira najboljeg poteza. Ako nasumični potez poboljšava stanje, onda slijedi isti put. U suprotnom, algoritam slijedi put koji ima vjerojatnost manju od 1 ili se kreće nizbrdo i odabire drugi put.