🧠 Lo spazio degli stati e la ricerca delle soluzioni

 TILLL / 🏠 HOME / ...

... ✍️ TateoBlog / 10/09/26 👈 sei qui.

... 🎓 Learning / 🧠 AI / problemi complessi / enumerative 👈 sei qui

#AI #enumerative #euristiche #robotica #DFS #BFS #machineLearning #deepLearning #LLM #TateoBlog #TILLL

Una delle idee fondamentali dell'Intelligenza Artificiale classica consiste nel rappresentare un problema come una ricerca all'interno di uno spazio degli stati. Uno stato rappresenta una possibile configurazione del problema, mentre le azioni consentono di passare da uno stato ad un altro. L'obiettivo del problema è rappresentato da uno o più stati finali desiderati.

Molti problemi pratici possono essere modellati in questo modo: la pianificazione di percorsi tra città, la risoluzione di puzzle, il gioco degli scacchi, la navigazione robotica, la schedulazione industriale e l'allocazione delle risorse. Una volta rappresentato il problema mediante un grafo o un albero di ricerca, la soluzione può essere ottenuta esplorando sistematicamente le alternative disponibili.

L'approccio basato sullo spazio degli stati ha avuto un ruolo fondamentale nello sviluppo dell'Intelligenza Artificiale simbolica durante i primi decenni della disciplina. Algoritmi come la Ricerca in Profondità (DFS) e la Ricerca in Ampiezza (BFS) nacquero originariamente come tecniche generali per la risoluzione dei problemi mediante l'esplorazione sistematica delle alternative.

La principale difficoltà consiste nel fatto che il numero degli stati cresce spesso in modo esponenziale rispetto alla dimensione del problema, dando origine al fenomeno noto come esplosione combinatoria. Per questo motivo le tecniche enumerative vengono frequentemente affiancate da approcci euristici in grado di guidare la ricerca verso le regioni più promettenti dello spazio delle soluzioni.

Nota storica. La ricerca nello spazio degli stati rappresenta uno dei fondamenti della cosiddetta Intelligenza Artificiale simbolica. Prima dell'avvento del Machine Learning e delle Reti Neurali Profonde (Deep Learning), molti ricercatori ritenevano che il comportamento intelligente potesse essere ottenuto modellando un problema come uno spazio di possibili stati e ricercando sistematicamente il percorso che conduce all'obiettivo. Tecniche come DFS, BFS, Branch-and-Bound e successivamente A* costituiscono ancora oggi il nucleo di molti sistemi di pianificazione e ottimizzazione.

Sebbene oggi l'Intelligenza Artificiale venga spesso associata al Machine Learning, al Deep Learning e ai Large Language Model, molti sistemi intelligenti contemporanei continuano a utilizzare algoritmi di ricerca nello spazio degli stati. La pianificazione di percorsi in robotica, l'ottimizzazione dei tragitti nei navigatori, i motori per giochi strategici e i sistemi di pianificazione automatica utilizzano ancora tecniche evolute derivate da DFS, BFS, Branch-and-Bound e A*.

Per questo motivo gli algoritmi di ricerca non devono essere considerati tecnologie superate, bensì uno dei mattoni fondamentali dell'Intelligenza Artificiale. Sebbene oggi l'attenzione sia spesso rivolta al Machine Learning, al Deep Learning e ai Large Language Model, la ricerca nello spazio degli stati continua ad essere ampiamente utilizzata nella robotica, nei sistemi di navigazione, nella pianificazione automatica, nei videogiochi e nei sistemi di supporto alle decisioni. Le moderne applicazioni di Intelligenza Artificiale combinano spesso tecniche di apprendimento con algoritmi di ricerca, dando origine a sistemi ibridi capaci sia di apprendere dai dati sia di ragionare sulle alternative disponibili.

🔗 Riferimenti per approfondire:

1. 📖 Enciclopedia di Elettronica & Informatica (EI) - 9. Aggiornamenti I, Gruppo Editoriale Jackson (📚lt.5.3-§3.8); Informatica e Società (IS) / Intelligenza Artificiale / Analisi delle alternative; pag. 10 

2. TILLL / 🏠 HOME / 🎓 Learning / 📚 Lettura (LT) / 🧬Saggi / Scienza /⚙️Tecnologia (LT.5.3); Titolo: Le mie letture dedicate alla tecnologia; Link: https://tateoblog.blogspot.com/p/tecnologia-lt53.html; Paragrafo: §3.8. Enciclopedia di Elettronica & Informatica (EI) - 9. Aggiornamenti I, Gruppo Editoriale Jackson

3. TILLL / 🏠 HOME / 🎓 Learning / 🧠 Intelligenza Artificiale (AI) / 🧠 Problemi complessi (AI.1) / 🧠 Enumerative (AI.1.2); Title: L'ottimizzazione per mezzo delle Tecniche Enumerative; 🔗: https://tateoblog.blogspot.com/p/ai12-la-ottimizzazione-attraverso-le.html.

4. TILLL / 🏠 HOME / 🎓 Learning / 🧠 Intelligenza Artificiale (AI); Titolo: Come delegare alle macchine compiti che gli umani riescono a svolgere grazie alla loro intelligenza; Link: https://tateoblog.blogspot.com/p/artificial-intelligence.html. Paragrafi: §6. Apprendimento Automatico (Machine Learning); §8. Deep Learning (DP), §8.7.1. Large Language Model (LLM).

5. TILLL / 🏠 HOME / 🎓 Learning / 🧠 Intelligenza Artificiale (AI) / 🧠 Problemi complessi (AI.1) / 🧠 Enumerative (AI.1.2) / 🧠Tecniche euristiche (AI.1.3); Titolo: L'approccio Euristico e le tecniche meta-Euristiche per la risoluzione dei problemi complessi; 🔗: https://tateoblog.blogspot.com/p/lapproccio-euristico-e-le-tecniche.html

6. TILLL / 🏠 HOME / 🎓 Learning / 🔧⚙️ Automazione (AU) / 🤖🦾 Robotica (AU.9); Titolo: La robotica; 🔗: https://tateoblog.blogspot.com/p/ua.html.

~~~~~~~~~~=======( v. 2 10 / 9 / 2026 )=====~~~~~~~~~~

© 2026 Tateo’s Interdisciplinary Lifelong Learning Lab (TILLL)

The backtracking technique and the search in depth (BFS).

La tecnica backtracking e la ricerca in profondità (BFS).

  The enumerative technique of Backtracking extends the exhaustive search (it can be considered as a refinement of the enumerative technique) in the resolution of search problems through the introduction of some checks to verify as soon as possible whether a solution under construction satisfies or not the conditions of eligibility in order to reduce the research space. Specifically, the technique consists in considering the research space as constituted by different components and at each stage a component is chosen. 

  La tecnica enumerativa di Backtracking estende la ricerca esaustiva (la si può considerare come un raffinamento della tecnica enumerativa) nella risoluzione di problemi di ricerca attraverso l’introduzione di alcuni controlli per verificare il più presto possibile se una soluzione in via di costruzione soddisfi o no le condizioni di ammissibilità in modo da ridurre lo spazio di ricerca. Nello specifico la tecnica consiste nel considerare lo spazio di ricerca come costituito da diverse componenti e ad ogni stadio viene scelta una componente. 

  It is then verified that at each stage i the admissibility conditions are not violated, if this happens then we come to the conclusion that the "partial solution" thus generated cannot lead to any solution, because any of its completion violates the constraints of the problem, ( here the restriction of the search space). Then the next element is chosen, if there is no element that allows not to violate the constraints, it returns to the previous stage i-1 (Backtracking) at this point the procedure is repeated at stage i-1 as in stage i. The algorithm ends when the solution has been reached (when the n-th stage is terminated without the constraints being violated) or when backtracking to the initial element (at the root) and all the components at the initial stage. 

  Si verifica poi che ad ogni stadio i non vengano violate le condizioni di ammissibilità, se ciò succede allora si giunge alla conclusione che la “soluzione parziale” così generata non può condurre a nessuna soluzione, perché qualsiasi suo completamento viola i vincoli del problema,(qui la restrizione dello spazio di ricerca). Quindi si sceglie l’elemento successivo, se non vi è nessun elemento che permetta di non violare i vincoli si ritorna allo stadio precedente i-1 (Backtracking) a questo punto si ripete la procedura allo stadio i-1 come allo stadio i. L’algoritmo termina quando si è arrivati alla soluzione (quando si termina l’n-esimo stadio senza che si siano violati i vincoli) oppure quando si fa Backtracking fino all’elemento iniziale (alla radice) e siano state scelte tutte le componenti allo stadio iniziale.

  The algorithm can be schematized with a search tree where the root is the first element chosen, the child nodes of the root are the elements that can be chosen at the second stage and so on up to the leaves that represent the search space. So if at a certain stage we choose an element for which the partial solution violates the admissibility constraints of the problem, then we can ignore the whole subtree rooted in the node representing the same element, thus reducing the search space.

  L’algoritmo può essere schematizzato con un albero di ricerca dove la radice è il primo elemento scelto, i nodi figli della radice sono gli elementi che si possono scegliere al secondo stadio e così via fino ad arrivare alle foglie che rappresentano lo spazio di ricerca. Quindi se ad un determinato stadio scegliamo un elemento per cui la soluzione parziale viola i vincoli di ammissibilità del problema, allora possiamo ignorare tutto il sotto-albero che ha come radice il nodo raffigurante lo stesso elemento, riducendo così lo spazio di ricerca.

  The algorithm for the Backtracking technique behaves as if a thorough examination of the tree was carried out. In graph theory, Depth-First Search (DFS) is a search algorithm on trees and graphs. The name derives from the fact that in a tree, even before having visited the nodes of the first generations, the algorithm can find itself visiting vertices far from the root, thus going "in depth". Not by chance, if run on a graph, the algorithm identifies a tree that is a sub-graph of it (that is, that contains all the vertices and all and only the arcs that have been followed). We can see the algorithm as a wide visit in which instead of a queue we use a stack (i.e. instead of adding the new items at the bottom we add them to the top).

  L’algoritmo per la tecnica Backtracking si comporta come se si effettuasse una visita in profondità dell’albero. Nella teoria dei grafi, la Ricerca in Profondità, in inglese Depth-First Search (DFS), è un algoritmo di ricerca su alberi e grafi. Il nome deriva dal fatto che in un albero, ancora prima di avere visitato i nodi delle prime generazioni, l'algoritmo può ritrovarsi a visitare vertici lontani dalla radice, andando così "in profondità". Non a caso, se fatto girare su un grafo, l'algoritmo individua un albero che ne è un sotto-grafo (ovvero che ne contiene tutti i vertici e tutti e soli gli archi che sono stati seguiti). Possiamo vedere l'algoritmo come una visita in ampiezza in cui invece che una coda utilizziamo una pila (ovvero invece di aggiungere gli elementi nuovi in fondo li aggiungiamo in cima).

Hashtag keywords: #enumerative #artificialIntelligence #backtracking #bfs #divideEtImpera #TILLL #TateoBlog

Extract from: Optimization by means of Enumerative Techniques, TILLL-Learning.

Link: https://tateoblog.blogspot.com/p/ai12-la-ottimizzazione-attraverso-le.html

_______________________________________

Tateo’s Interdisciplinary Lifelong Learning Project
T I L L L
LEARNING - SHARING - NETWORKING
Learning, knowledge sharing and communities engagement about:
Artificial Intelligence; Augmented, Virtual and Mixed Reality; Automation; Electronics; Computer Science and Information Technology; Mobile Technologies; Problem Solving; Readings; Social Media; Modeling and Simulation; Artificial Vision; Hard and Soft Work Skills.
by Tateo Giovanni Battista
_______________________________________

TILLL~Blog © January 9, 2022

Il principio "Divide et impera" nella risoluzione dei problemi complessi

Tateo-Blog > Learning > Intelligenza Artificiale > Problem Solving > Enumerative >

#intelligenzaartificiale, #ottimizzazione, #enumerative, #artificialintelligence, #optimization, #backtracking, #bfs, #dfs, #programmazionedinamica, #divideetimpera

13-06-2019. Premesso che per problemi complessi, la tecnica enumerativa pura, ossia la ricerca esaustiva, non è praticabile, consideriamo una categorie di tecniche alternative che si rifanno al ben noto principio "Divide et Impera". Questo principio consiste nella scomposizione ricorsiva del problema complesso in un certo numero di sotto-problemi più semplici fino a quando questi non diventino di semplice risoluzione. La scomposizione, inoltre, permette di parallelizzare la computazione aumentandone l'efficienza su sistemi distribuiti o multi-processore. Al termine della risoluzione di tutti i sotto-problemi elementari, ricombinando le loro soluzioni si ottiene la soluzione del problema di partenza.

Citiamo di seguito, come esempi di tecniche ispirate al principio "Divide et impera", la tecnica Backtracking, la tecnica Golosa (Enumerazione Implicita), e quella di Programmazione Dinamica.

Per approfondire gli altri aspetti di questa particolare metodologia di problem solving, ti invito a proseguire la consultazione di Tateo Blog con la lettura dell’articolo

AI.1.2. LA OTTIMIZZAZIONE ATTRAVERSO LE TECNICHE ENUMERATIVE 

che è contenuto nella sezione Learning di

Learning & Web Posting interdisciplinare sui seguenti argomenti:

| INTELLIGENZA ARTIFICIALE | REALTA' AUMENTATA / VIRTUALE | AUTOMAZIONE | ELETTRONICA | LETTERATURA | INFORMATICA | DISPOSITIVI MOBILI | PROBLEM MANAGEMENT | SOCIAL MEDIA | SIMULAZIONE | VISIONE ARTIFICIALE | COMPETENZE |

COLLABORA CON ME. Se il mio post, e l'articolo a cui esso fa riferimento, hanno incontrato il tuo interesse e se vuoi contribuire a migliorarne il contenuto, allora ti invito a lasciare un segno del tuo gradimento, un commento, una critica, un suggerimento oppure una riflessione nello spazio preposto in coda al post. Sarò felice di leggere il tuo messaggio e di confrontarmi con te.

TENIAMOCI IN CONTATTO. Se preferisci puoi seguirmi attraverso una delle seguenti piattaforme social:

LinkedIn | Facebook | Twitter : @tateogb | Instagram | AboutMe |

Oppure puoi contattarmi direttamente attraverso uno dei seguenti riferimenti:

tateogb@libero.it­ (e-mail) | 388–8419726 (mobile o WhatsApp) |­ giovannibattistatateo (Skype) |

(c) 2019-24