TILLL > 🏠 Home > ✍️ TateoBlog > 🧠 Branch-and-Bound 👈 Sei qui
#AI #ArtificialIntelligence #enumerative #TateoBlog #TILLL
La tecnica Branch-and-Bound (letteralmente "ramifica e delimita") rappresenta una delle più importanti evoluzioni delle tecniche enumerative classiche. L'idea consiste nel suddividere progressivamente il problema in sotto-problemi sempre più piccoli (branching), associando però ad ogni sotto-problema una stima del miglior risultato che esso potrebbe produrre (bound).
Quando questa stima dimostra che un determinato sotto-problema non potrà mai condurre ad una soluzione migliore di quelle già individuate, l'intero sotto-albero ad esso associato viene eliminato senza essere ulteriormente esplorato. In questo modo una parte potenzialmente molto ampia dello spazio delle soluzioni viene esclusa dalla ricerca.
A differenza della ricerca esaustiva, che visita sistematicamente tutte le possibili alternative, il Branch-and-Bound cerca di concentrare gli sforzi computazionali esclusivamente sulle regioni dello spazio delle soluzioni che appaiono più promettenti.
Questa tecnica viene largamente utilizzata nei problemi di ottimizzazione combinatoria, quali il problema del commesso viaggiatore (Travelling Salesman Problem), l'assegnazione delle risorse, la pianificazione delle attività e numerosi problemi della Ricerca Operativa.
Il Branch-and-Bound occupa una posizione storicamente importante nell'Intelligenza Artificiale poiché introduce il concetto di ricerca guidata da informazioni aggiuntive sul problema. Molti algoritmi moderni, tra cui il celebre algoritmo A*, possono essere interpretati come un'evoluzione di questo approccio, nella quale alla valutazione del costo già sostenuto si affianca una stima euristica del costo necessario per raggiungere l'obiettivo.
- [1] 📖 Analisi delle alternative; Enciclopedia di Elettronica & Informatica (EI) - 9. Aggiornamenti I, Gruppo Editoriale Jackson (📚LT.5.3-§3.8); Informatica e Società (IS) / Intelligenza Artificiale; pag. 10
- [2] 🧭Enciclopedia di Elettronica & Informatica (EI) - 9. Aggiornamenti I, Gruppo Editoriale Jackson; 🔗:https://tateoblog.blogspot.com/p/tecnologia-lt53.html (LT.5.3-§3.8).
- [3] 🧭L'ottimizzazione per mezzo delle Tecniche Enumerative; 🔗:https://tateoblog.blogspot.com/p/ai12-la-ottimizzazione-attraverso-le.html (AI.1.2-§7).
- [4] 🧭 Come delegare alle macchine compiti che gli umani riescono a svolgere grazie alla loro intelligenza; 🔗https://tateoblog.blogspot.com/p/artificial-intelligence.html; (AI.)
_______________________________________________________
Questo contenuto fa parte del progetto Tateo's Interdisciplinary Lifelong Learning Lab (TILLL), dedicato all'apprendimento continuo, all'interdisciplinarità e alla condivisione della conoscenza.
Nessun commento:
Posta un commento