• Algoritmul de alpinism este un algoritm de căutare locală care se mișcă continuu în direcția creșterii cotei/valorii pentru a găsi vârful muntelui sau cea mai bună soluție la problemă. Se termină când atinge o valoare de vârf unde niciun vecin nu are o valoare mai mare.
• Algoritmul de alpinism este o tehnică utilizată pentru optimizarea problemelor matematice. Unul dintre exemplele larg discutate de algoritm de escaladare a dealurilor este Problema Traveling-salesman în care trebuie să minimizăm distanța parcursă de vânzător.
• Se mai numește și căutare locală lacomă, deoarece se uită doar la starea vecinului său imediat bun și nu mai departe.
• Un nod de algoritm de alpinism are două componente care sunt starea și valoarea.
• Alpinismul este folosit mai ales atunci când este disponibilă o euristică bună.
• În acest algoritm, nu trebuie să menținem și să gestionăm arborele sau graficul de căutare, deoarece păstrează doar o singură stare curentă.

Caracteristici ale alpinismului:

Următoarele sunt câteva caracteristici principale ale algoritmului Hill Climbing:

Generați și testați varianta:Hill Climbing este varianta metodei Generate and Test. Metoda Generare și Testare produce feedback care vă ajută să decideți în ce direcție să vă mișcați în spațiul de căutare.Abordare lacomă:Căutarea algoritmului de alpinism se deplasează în direcția care optimizează costul.Fără întoarcere:Nu dă înapoi spațiul de căutare, deoarece nu își amintește stările anterioare.

Diagrama de stat-spațiu pentru alpinism:

Peisajul de stat-spațiu este o reprezentare grafică a algoritmului de alpinism care arată un grafic între diferite stări ale algoritmului și funcția obiectiv/cost.

python sort tuple

Pe axa Y am luat funcția care poate fi o funcție obiectiv sau funcție de cost și spațiul de stare pe axa x. Dacă funcția de pe axa Y este costul, atunci scopul căutării este de a găsi minimul global și minimul local. Dacă funcția axei Y este funcția obiectivă, atunci scopul căutării este de a găsi maximul global și maximul local.

Diferite regiuni din peisajul spațiului de stat:

Maxim local: Maximul local este un stat care este mai bun decât statele vecine, dar există și un alt stat care este mai înalt decât acesta.

Maxim global: Maximul global este cea mai bună stare posibilă a peisajului spațial de stat. Are cea mai mare valoare a funcției obiective.

Starea curenta: Este o stare dintr-o diagramă peisaj în care un agent este prezent în prezent.

Maxim local plat: Este un spațiu plat în peisaj în care toate stările vecine ale stărilor actuale au aceeași valoare.

Umăr: Este o regiune de platou care are o margine în sus.

Tipuri de algoritm de alpinism:

• Alpinism simplu:
• Cea mai abruptă urcare de deal:
• Alpinism stocastic:

1. Alpinism simplu:

Alpinismul simplu este cel mai simplu mod de a implementa un algoritm de alpinism. Evaluează doar starea nodului vecin la un moment dat și îl selectează pe primul care optimizează costul curent și îl setează ca stare curentă . Verifică doar starea succesorală și dacă găsește o stare mai bună decât starea curentă, atunci mutați altfel să fie în aceeași stare. Acest algoritm are următoarele caracteristici:

• Mai puțin consumator de timp
• Soluție mai puțin optimă și soluția nu este garantată

Algoritm pentru alpinism simplu:

Pasul 1:Evaluați starea inițială, dacă este starea obiectivului, reveniți cu succes și opriți.Pasul 2:Buclă Până când se găsește o soluție sau nu mai rămâne niciun operator nou de aplicat.Pasul 3:Selectați și aplicați un operator la starea curentă.Pasul 4:Verificați starea nouă:
1. Dacă este starea obiectivului, atunci reveniți cu succes și renunțați.
2. Altfel, dacă este mai bună decât starea curentă, atunci atribuiți o nouă stare ca stare curentă.
3. Altfel, dacă nu este mai bună decât starea curentă, atunci reveniți la pasul 2.
Pasul 5:Ieșire.

2. Cea mai abruptă urcare pe deal:

Algoritmul cel mai abrupt de urcare este o variantă a algoritmului simplu de alpinism. Acest algoritm examinează toate nodurile vecine ale stării curente și selectează un nod vecin care este cel mai apropiat de starea obiectiv. Acest algoritm consumă mai mult timp pe măsură ce caută mai mulți vecini

Algoritm pentru alpinism pe deal cu cea mai abruptă urcare:

Pasul 1:Evaluați starea inițială, dacă este starea obiectivului, întoarceți succesul și opriți, altfel faceți starea curentă ca stare inițială.Pasul 2:Buclă până când se găsește o soluție sau starea curentă nu se schimbă.
1. Să fie SUCC un stat astfel încât orice succesor al statului actual să fie mai bun decât acesta.
2. Pentru fiecare operator care se aplică stării curente:
   1. Aplicați noul operator și generați o nouă stare.
   2. Evaluează noua stare.
   3. Dacă este starea obiectivului, returnați-l și renunțați, altfel comparați-l cu SUCC.
   4. Dacă este mai bine decât SUCC, atunci setați noua stare ca SUCC.
   5. Dacă SUCC este mai bun decât starea curentă, atunci setați starea curentă la SUCC.
Pasul 5:Ieșire.

3. Alpinism stocastic:

Alpinismul stocastic nu examinează vecinii înainte de a se muta. Mai degrabă, acest algoritm de căutare selectează la întâmplare un nod vecin și decide dacă îl alege ca stare curentă sau examinează o altă stare.

Probleme în algoritmul de alpinism:

1. Maxim local: Un maxim local este o stare de vârf în peisaj care este mai bună decât fiecare dintre statele vecine, dar există și un alt stat care este mai mare decât maximul local.

îmbunătățit pentru buclă java

Soluţie: Tehnica backtracking poate fi o soluție a maximului local în peisajul spațiului de stat. Creați o listă a căii promițătoare, astfel încât algoritmul să poată face înapoi spațiul de căutare și să exploreze și alte căi.

linux care

2. Podișul: Un platou este zona plată a spațiului de căutare în care toate stările vecine ale stării curente conțin aceeași valoare, din cauza acestui algoritm nu găsește cea mai bună direcție de deplasare. O căutare de alpinism ar putea fi pierdută în zona platoului.

Soluţie: Soluția pentru platou este să faci pași mari sau foarte mici în timpul căutării, pentru a rezolva problema. Selectați aleatoriu o stare care este departe de starea curentă, astfel încât este posibil ca algoritmul să găsească o regiune non-plateau.

3. Crestele: O creastă este o formă specială a maximului local. Are o zonă mai înaltă decât zonele înconjurătoare, dar ea însăși are o pantă și nu poate fi atins într-o singură mișcare.

Soluţie: Cu ajutorul căutării bidirecționale sau prin deplasarea în direcții diferite, putem îmbunătăți această problemă.

Recoacere simulată:

Un algoritm de alpinism care nu face niciodată o mișcare către o valoare mai mică garantată a fi incomplet deoarece se poate bloca la un maxim local. Și dacă algoritmul aplică o mers aleatorie, prin mutarea unui succesor, atunci acesta poate fi complet, dar nu eficient. Recoacerea simulată este un algoritm care oferă atât eficiență, cât și completitudine.

În termeni mecanici Recoacerea este un proces de întărire a unui metal sau a sticlei la o temperatură ridicată, apoi de răcire treptat, astfel încât acest lucru permite metalului să atingă o stare cristalină cu energie scăzută. Același proces este utilizat în recoacere simulată în care algoritmul alege o mișcare aleatorie, în loc să aleagă cea mai bună mișcare. Dacă mișcarea aleatoare îmbunătățește starea, atunci urmează aceeași cale. În caz contrar, algoritmul urmează calea care are o probabilitate mai mică de 1 sau se deplasează în jos și alege o altă cale.