Sommario:
Definizione - Cosa significa Hill Climbing?
L'arrampicata in collina è un metodo euristico di ottimizzazione matematica utilizzato per risolvere problemi complessi dal punto di vista computazionale che presentano soluzioni multiple. È un metodo iterativo appartenente alla famiglia di ricerca locale che inizia con una soluzione casuale e quindi migliora iterativamente quella soluzione un elemento alla volta fino a quando non arriva a una soluzione più o meno ottimizzata.
Techopedia spiega Hill Climbing
L'arrampicata in collina è una tecnica di ottimizzazione che viene utilizzata per trovare una soluzione "locale ottimale" a un problema computazionale. Si inizia con una soluzione che è molto scarsa rispetto alla soluzione ottimale e quindi migliora iterativamente da lì. Lo fa generando soluzioni "vicine" che sono relativamente un passo migliore rispetto alla soluzione attuale, sceglie il meglio e quindi ripete il processo fino a quando non arriva alla soluzione ottimale perché non riesce più a trovare alcun miglioramento.
varianti:
- Semplice: viene scelto il primo nodo o soluzione più vicino da trovare.
- Salita più ripida: vengono prese in considerazione tutte le soluzioni successive disponibili e viene selezionata la soluzione più vicina.
- Stocastico: una soluzione vicina viene selezionata casualmente e viene quindi deciso se passare a quella soluzione in base alla quantità di miglioramento rispetto al nodo corrente.
L'arrampicata in collina viene eseguita in modo iterativo - passa attraverso un'intera procedura e la soluzione finale viene memorizzata. Se una iterazione diversa trova una soluzione finale migliore, la soluzione o lo stato memorizzato viene sostituito. Questo è anche chiamato arrampicata su collina di fucili da caccia, in quanto prova semplicemente diversi percorsi fino a quando non colpisce il migliore, proprio come un fucile è impreciso ma può ancora colpire il bersaglio a causa della vasta diffusione di proiettili. Funziona molto bene in molti casi perché, a quanto pare, è meglio spendere risorse della CPU per esplorare percorsi diversi piuttosto che ottimizzare con attenzione da una condizione iniziale.
