Si prega di spiegare la differenza tra gli algoritmi "hill climbing" e "greedy".Qual è la differenza tra gli algoritmi "hill climbing" e "greedy"?
Sembra che entrambi siano simili, e ho il dubbio che "l'arrampicata su una collina" sia un algoritmo; sembra essere un'ottimizzazione. È corretto?
Gli algoritmi di scalata e avidi sono entrambi metodi euristici che possono essere utilizzati per problemi di ottimizzazione. In un problema di ottimizzazione , generalmente cerchiamo una combinazione o un ordine ottimale di elementi problematici. Una determinata combinazione o ordinamento è una soluzione. In entrambi i casi, una soluzione può essere valutata per confrontarla con altre soluzioni.
In un'arrampicata euristica, si inizia con una soluzione iniziale. Genera una o più soluzioni adiacenti. Scegli il meglio e continua fino a quando non ci sono soluzioni migliori vicine. Ciò genererà generalmente una soluzione. Nell'arrampicata, dobbiamo sapere come valutare una soluzione e come generare un "vicino".
In un avido euristico, abbiamo bisogno di sapere qualcosa di speciale sul problema in questione. Un algoritmo avido utilizza le informazioni per produrre un'unica soluzione.
Un buon esempio di un problema di ottimizzazione è uno zaino 0-1. In questo problema, c'è uno zaino con un certo limite di peso e un mucchio di oggetti da mettere nello zaino. Ogni oggetto ha un peso e un valore. L'obiettivo è massimizzare il valore degli oggetti nello zaino mantenendo il peso sotto il limite.
Un algoritmo avido sceglierebbe oggetti di maggiore densità e li inserirà finché lo zaino non sarà pieno. Ad esempio, rispetto a un mattone, un diamante ha un valore elevato e un peso ridotto, quindi metteremo il diamante in primo piano.
Ecco un esempio di dove un algoritmo greedy fallirebbe: Diciamo che avete uno zaino con capacità di 100. Sono disponibili le seguenti voci:
l'algoritmo greedy metterebbe nel diamante e poi essere fatto, dando un valore di 1000. Ma la soluzione ottimale sarebbe quella di includere le 5 monete d'oro, dando valore 1050.
L'algoritmo di scalata genererebbe una soluzione iniziale, scegliendo solo alcuni elementi casuali (assicurarsi che siano sotto il limite di peso). Quindi valuta la soluzione, cioè determina il valore. Genera una soluzione vicina.Ad esempio, prova a scambiare un oggetto con un altro (assicurati di essere ancora al di sotto del limite di peso). Se questo ha un valore più alto, usa questa selezione e ricomincia.
L'arrampicata in salita non è un algoritmo avido.
Sì, hai ragione. L'alpinismo è una tecnica di ottimizzazione matematica generale (vedi: http://en.wikipedia.org/wiki/Hill_climbing). Un algoritmo ingordo è un algoritmo che sceglie semplicemente la scelta migliore che vede al momento e lo prende.
Un esempio di questo è apportare modifiche riducendo al minimo il numero di monete (almeno con USD). Prendi la maggior parte della moneta più alta, quindi la maggior parte della successiva più alta, fino a raggiungere la quantità necessaria.
In questo modo, l'arrampicata su collina è un algoritmo ingordo.
La tua conclusione sembra fuorviante. L'algoritmo greedy specifico che hai descritto costruisce avidamente la soluzione, mentre l'euristica dell'arrampicata raggiunge avidamente un optima locale. L'unica differenza è che il passo goloso nel primo riguarda la costruzione di una soluzione, mentre il passo goloso nell'arrampicata consiste nella selezione di un vicino (ricerca locale avida). Hill climbing è un'euristica golosa. Se si desidera distinguere un algoritmo da un euristico, suggerirei di leggere la risposta di Mikola, che è più precisa. –