• L'algoritmo di salita in collina è un algoritmo di ricerca locale che si muove continuamente nella direzione dell'aumento dell'elevazione/del valore per trovare la vetta della montagna o la migliore soluzione al problema. Termina quando raggiunge un valore di picco dove nessun vicino ha un valore più alto.
• L'algoritmo di hill climbing è una tecnica utilizzata per ottimizzare i problemi matematici. Uno degli esempi ampiamente discussi di algoritmo Hill climbing è il problema del commesso viaggiatore in cui dobbiamo ridurre al minimo la distanza percorsa dal venditore.
• Si chiama anche ricerca locale avida poiché guarda solo allo stato vicino immediato e non oltre.
• Un nodo dell'algoritmo di hill climbing ha due componenti che sono stato e valore.
• L'Hill Climbing viene utilizzato principalmente quando è disponibile una buona euristica.
• In questo algoritmo, non abbiamo bisogno di mantenere e gestire l'albero o il grafico di ricerca poiché mantiene solo un singolo stato corrente.

Caratteristiche dell'arrampicata in collina:

Di seguito sono riportate alcune caratteristiche principali dell'algoritmo Hill Climbing:

Genera e prova la variante:Hill Climbing è la variante del metodo Genera e prova. Il metodo Genera e Testa produce feedback che aiuta a decidere in quale direzione muoversi nello spazio di ricerca.Approccio goloso:La ricerca dell’algoritmo di hillclimbing si muove nella direzione che ottimizza il costo.Nessun ritorno indietro:Non torna indietro nello spazio di ricerca, poiché non ricorda gli stati precedenti.

Diagramma spazio-stato per l'arrampicata in collina:

Il panorama nello spazio degli stati è una rappresentazione grafica dell'algoritmo di salita in collina che mostra un grafico tra i vari stati dell'algoritmo e la funzione obiettivo/costo.

Sull'asse Y abbiamo preso la funzione che può essere una funzione obiettivo o una funzione di costo, e lo spazio degli stati sull'asse x. Se la funzione sull'asse Y è costo, l'obiettivo della ricerca è trovare il minimo globale e il minimo locale. Se la funzione dell'asse Y è la funzione Obiettivo, l'obiettivo della ricerca è trovare il massimo globale e il massimo locale.

Diverse regioni nel panorama dello spazio statale:

Massimo locale: Il massimo locale è uno stato che è migliore degli stati vicini, ma esiste anche un altro stato che è più alto di esso.

Massimo globale: Il massimo globale è il miglior stato possibile del panorama dello spazio statale. Ha il valore più alto della funzione obiettivo.

Stato attuale: È uno stato in un diagramma paesaggistico in cui è attualmente presente un agente.

Massimo locale piatto: È uno spazio piatto nel paesaggio in cui tutti gli stati vicini agli stati attuali hanno lo stesso valore.

Spalla: È una regione dell'altopiano che ha un bordo in salita.

Tipi di algoritmo di arrampicata in collina:

• Arrampicata semplice:
• Salita più ripida:
• Salita stocastica in salita:

1. Arrampicata semplice in collina:

Il semplice hill climbing è il modo più semplice per implementare un algoritmo di hill climbing. Valuta solo lo stato del nodo vicino alla volta e seleziona il primo che ottimizza il costo corrente e lo imposta come stato corrente . Controlla solo che si tratti di uno stato successivo e, se trova uno stato migliore dello stato corrente, sposta il resto nello stesso stato. Questo algoritmo ha le seguenti caratteristiche:

• Meno tempo richiesto
• Soluzione meno ottimale e la soluzione non è garantita

Algoritmo per la scalata semplice in collina:

Passo 1:Valuta lo stato iniziale, se è lo stato obiettivo, restituisci successo e Stop.Passo 2:Ciclo finché non viene trovata una soluzione o non rimane alcun nuovo operatore da applicare.Passaggio 3:Seleziona e applica un operatore allo stato corrente.Passaggio 4:Controlla il nuovo stato:
1. Se è lo stato obiettivo, restituisci il successo e esci.
2. Altrimenti, se è migliore dello stato corrente, assegna il nuovo stato come stato corrente.
3. Altrimenti, se non migliore, dello stato attuale, torna al passaggio 2.
Passaggio 5:Uscita.

2. Salita in salita più ripida:

L'algoritmo della salita più ripida è una variante del semplice algoritmo di salita in collina. Questo algoritmo esamina tutti i nodi vicini dello stato corrente e seleziona un nodo vicino più vicino allo stato obiettivo. Questo algoritmo consuma più tempo durante la ricerca di più vicini

Algoritmo per la salita in salita più ripida:

Passo 1:Valuta lo stato iniziale, se è lo stato obiettivo, restituisci successo e interrompi, altrimenti rendi lo stato corrente come stato iniziale.Passo 2:Ripeti finché non viene trovata una soluzione o lo stato corrente non cambia.
1. Lasciamo che il SUCC sia uno stato tale che qualsiasi successore dello stato attuale sarà migliore di esso.
2. Per ogni operatore che si applica allo stato corrente:
   1. Applica il nuovo operatore e genera un nuovo stato.
   2. Valutare il nuovo stato.
   3. Se è lo stato obiettivo, restituiscilo ed esci, altrimenti confrontalo con SUCC.
   4. Se è migliore di SUCC, imposta il nuovo stato come SUCC.
   5. Se il SUCC è migliore dello stato corrente, imposta lo stato corrente su SUCC.
Passaggio 5:Uscita.

3. Salita stocastica:

L'arrampicata stocastica non esamina tutti i suoi vicini prima di muoversi. Piuttosto, questo algoritmo di ricerca seleziona un nodo vicino in modo casuale e decide se sceglierlo come stato corrente o esaminare un altro stato.

Problemi nell'algoritmo di arrampicata in collina:

1. Massimo locale: Un massimo locale è uno stato di picco nel paesaggio che è migliore di ciascuno degli stati confinanti, ma è presente anche un altro stato che è superiore al massimo locale.

Soluzione: La tecnica del backtracking può essere una soluzione del massimo locale nel panorama dello spazio statale. Crea un elenco del percorso promettente in modo che l'algoritmo possa tornare indietro nello spazio di ricerca ed esplorare anche altri percorsi.

2. Altopiano: Un plateau è l'area piatta dello spazio di ricerca in cui tutti gli stati vicini allo stato corrente contengono lo stesso valore, poiché questo algoritmo non trova alcuna direzione migliore in cui muoversi. Una ricerca in salita potrebbe andare perduta nell'area dell'altopiano.

Soluzione: La soluzione per l’altopiano è fare passi grandi o piccolissimi durante la ricerca, per risolvere il problema. Seleziona casualmente uno stato lontano dallo stato corrente in modo che sia possibile che l'algoritmo possa trovare una regione non plateau.

3. Creste: Una cresta è una forma speciale del massimo locale. Ha un'area più alta rispetto alle aree circostanti, ma a sua volta ha una pendenza e non può essere raggiunta con un solo movimento.

Soluzione: Con l'uso della ricerca bidirezionale, ovvero muovendosi in direzioni diverse, possiamo migliorare questo problema.

Ricottura simulata:

Un algoritmo di scalata che non si muove mai verso un valore inferiore è sicuramente incompleto perché può rimanere bloccato su un massimo locale. E se l’algoritmo applica una passeggiata casuale, spostando un successore, allora potrebbe essere completo ma non efficiente. Ricottura simulata è un algoritmo che garantisce sia efficienza che completezza.

In termini meccanici Ricottura è un processo di indurimento di un metallo o di vetro ad alta temperatura e poi di raffreddamento graduale, quindi ciò consente al metallo di raggiungere uno stato cristallino a bassa energia. Lo stesso processo viene utilizzato nella ricottura simulata in cui l'algoritmo sceglie una mossa casuale, invece di scegliere la mossa migliore. Se la mossa casuale migliora lo stato, segue lo stesso percorso. Altrimenti l'algoritmo segue il percorso che ha una probabilità inferiore a 1 oppure si muove in discesa e sceglie un altro percorso.