Vincoli e pruning delle soluzioni

Vincoli e pruning delle soluzioni

Nell’esplorazione dello spazio delle possibili soluzioni di un problema spesso è necessario porre dei vincoli alle soluzioni cercate, per necessità o spesso per richieste relative al problema trattato; tali vincoli vengono applicati alla soluzione completa sui casi terminali delle ricorsioni, essi vengono denominati condizioni di accettazione.
E’ però possibile evitare alcuni rami ricorsivi cercando di eliminare quelle strade di ricorsione che allo stato di ricorsione in cui se ne effettua il controllo, viene già ritenuta non idonea a divenire al caso terminale, come possibile soluzione validata; vengono dunque effettuati dei controlli intermedi ad ogni passo di ricorsione per verificare la bontà della soluzione parziale, tale meccanismo viene definito pruning e permette di ridurre il numero di ricorsioni effettuate dall’algoritmo.
Un esempio di utilizzo del pruning è ad esempio il classico problema dello zaino; se si possiede uno zaino di capienza x e si vuole trovare il massimo numero di oggetti trasportabili nello zaino, se la soluzione parziale di oggetti trasportati supera la capienza massima dello zaino, quel ramo di ricorsione viene abbandonata perché non può più portare ad una soluzione valida, viene quindi risparmiato il tempo di esecuzione dell’algoritmo sui successivi passi di ricorsione di quella soluzione parziale, molte volte con un buon risparmio di tempo.