Python - Classi di algoritmi
Gli algoritmi sono passaggi non ambigui che dovrebbero darci un output ben definito elaborando zero o più input. Questo porta a molti approcci nella progettazione e nella scrittura degli algoritmi. È stato osservato che la maggior parte degli algoritmi può essere classificata nelle seguenti categorie.
Algoritmi avidi
Gli algoritmi avidi cercano di trovare una soluzione ottimale localizzata, che alla fine può portare a soluzioni ottimizzate a livello globale. Tuttavia, gli algoritmi generalmente avidi non forniscono soluzioni ottimizzate a livello globale.
Gli algoritmi così avidi cercano una soluzione facile in quel momento senza considerare come influisce sui passaggi futuri. È simile a come gli esseri umani risolvono i problemi senza passare attraverso i dettagli completi degli input forniti.
La maggior parte degli algoritmi di rete utilizza l'approccio avido. Ecco un elenco di alcuni di loro:
- Problema del commesso viaggiatore
- Algoritmo Minimal Spanning Tree di Prim
- Algoritmo Minimal Spanning Tree di Kruskal
- Algoritmo Minimal Spanning Tree di Dijkstra
Dividere e conquistare
Questa classe di algoritmi comporta la divisione del problema dato in sotto-problemi più piccoli e quindi la risoluzione di ciascuno dei sotto-problemi in modo indipendente. Quando il problema non può essere ulteriormente suddiviso, iniziamo a fondere la soluzione a ciascuno dei sotto-problemi per arrivare alla soluzione per il problema più grande.
Gli esempi importanti di algoritmi divide et impera sono:
- Unisci ordinamento
- Ordinamento rapido
- Algoritmo Minimal Spanning Tree di Kruskal
- Ricerca binaria
Programmazione dinamica
La programmazione dinamica implica la divisione del problema più grande in problemi più piccoli ma, a differenza del divide et impera, non implica la risoluzione di ogni sottoproblema in modo indipendente. Piuttosto, i risultati di problemi secondari più piccoli vengono ricordati e utilizzati per problemi secondari simili o sovrapposti. Per lo più, questi algoritmi vengono utilizzati per l'ottimizzazione. Prima di risolvere il sotto-problema in mano, l'algoritmo dinamico cercherà di esaminare i risultati dei sotto-problemi risolti in precedenza.
gli algoritmi dinamici sono motivati per un'ottimizzazione complessiva del problema e non per l'ottimizzazione locale.
Gli esempi importanti di algoritmi di programmazione dinamica sono:
- Serie di numeri di Fibonacci
- Problema dello zaino
- Torre di Hanoi