ENUMERATIVE (AI.1.2)

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 / Mixed Reality, Automation, Electronics, Computer Science and Information Technology, Mobile Technologies, Problem Solving, Readings, Social Media, Simulation, Artificial Vision, Work and Soft Skills

by Tateo Giovanni Battista

_________________________________

LEARNING

ARTIFICIAL VISION

Optimization by means of Enumerative Techniques.

L'ottimizzazione per mezzo delle Tecniche Enumerative.

Hashtag keywords: #enumerative #artificialIntelligence #optimization #backtracking #bfs #dfs #dynamicProgramming #divideEtImpera #TILLL #TateoBlog 

Summary. The Enumerative Techniques, also called exhaustive, are the techniques that allow to find the exact solution of the problem. We deepen the study by stating the characteristics of the main enumerative techniques, starting from the exhaustive research, continuing with the techniques inspired by "divide et impera" and "Backtracking", with the "greedy" technique, of BFS and DFS research, and of Programming Dynamics.. 

Le Tecniche Enumerative, dette anche esaustive, sono le tecniche che permettono di trovare la soluzione esatta del problema. Approfondiamo lo studio enunciando le caratteristiche delle principali tecniche enumerative, a partire dalla ricerca esaustiva, continuando con le tecniche ispirate al "divide et impera" ed al "Backtracking", con la tecnica "golosa", della ricerca BFS e DFS, e della Programmazione Dinamica.

~ o ~

You are here (>>>) within the TILLL project

Ti trovi qui (>>>) all'interno del progetto TILLL

HOME

|

+->>> TILLL 

      |

      +-> LEARNING

      |   +->>> AI. ARTIFICIAL INTELLIGENCE

      |         +->>> 1. COMPLEX PROBLEMS

      |               +->>> 1. COMPLEX SYSTEMS

      |               +->>> 2. ENUMERRATIVE

      |               +->>> 3. HEURISTICS

      |

      +->>> SHARING

      |     +->>> BLOG

      |

      +->>> NETWORKING

      |

      +->>> ABOUT ME

~ o ~

§1. Enumerative techniques (or exhaustive research).

Tecniche enumerative (o ricerca esaustiva).

  The Enumerative Techniques, also called exhaustive, are the techniques that allow to find the exact solution of the problem. An elementary example of an enumerative algorithm is the sequential search for an element in a vector. In this elementary case, the search space has linear dimensions with respect to the size of the input data, therefore an acceptable efficiency. However, there are often algorithms for which the size of the search space is large (exponential example) compared to the size of the input data. While as regards the search, the search space is visited up to the searched element and everything is visited only in the worst case, (and searched in the nth position or unsuccessful search) in the case of an optimization problem the space of search must almost always be (see case in which the minimum is searched for in a set M of non-negative integers, in this case the optimal solution is 0 and the visit stops as soon as this value is met) necessarily visited in full. As you can understand, this process is very expensive from the point of view of the calculation. The worst case asymptotic complexity of an enumerative algorithm is obviously related to the size of the search space, which must be entirely visited. We therefore deduce that, although the enumerative techniques allow to determine the solution of a problem in a finite way, often due to the computational complexity they are not effective, in the sense that they do not allow to arrive at the result in an acceptable time.

  Le Tecniche Enumerative, dette anche esaustive, sono le tecniche che permettono di trovare la soluzione esatta del problema. Un esempio elementare di algoritmo enumerativo è la ricerca sequenziale di un elemento in un vettore. In questo caso elementare, lo spazio di ricerca ha dimensioni lineari rispetto alla dimensione dei dati di ingresso quindi un’efficienza accettabile. Esistono però spesso algoritmi per i quali la dimensione dello spazio di ricerca è elevata (esempio esponenziale) rispetto alla dimensione dei dati di ingresso. Mentre per quanto riguarda la ricerca, lo spazio di ricerca viene visitato fino all’elemento cercato e viene visitato tutto solo nel caso peggiore, (e cercato nella n-esima posizione o ricerca con insuccesso) nel caso di un problema di ottimizzazione lo spazio di ricerca deve quasi sempre essere (vedi caso in cui si ricerchi il minimo in un insieme M di interi non negativi, in questo caso la soluzione ottimale è 0 e la visita s’interrompe appena incontrato questo valore) obbligatoriamente visitato per intero. Come si può comprendere questo processo è molto oneroso dal punto di vista del calcolo. La complessità asintotica nel caso peggiore di un algoritmo enumerativo è ovviamente legata alla dimensione dello spazio di ricerca, che deve interamente essere visitato. Deduciamo quindi che, sebbene le tecniche enumerative permettano di determinare in modo finito la soluzione di un problema, spesso a causa della complessità computazionale non sono efficaci, nel senso che non permettono di pervenire al risultato in tempi accettabili.

~ o ~

§2. Divide et impera

  Given that for complex problems, the pure enumerative technique, that is the exhaustive search, is not practicable, let's consider a category of alternative techniques that refer to the well-known principle "Divide et Impera". This principle consists in the recursive decomposition of the complex problem into a certain number of simpler sub-problems until these become simple to solve. Furthermore, the decomposition allows to parallelize the computation, increasing its efficiency on distributed or multi-processor systems. At the end of the solution of all the elementary sub-problems, by recombining their solutions we obtain the solution of the starting problem.

  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.

  We cite below, as examples of techniques inspired by the "Divide et impera" principle, the Backtracking technique, the Golosa technique (Implicit Enumeration), and that of Dynamic Programming.

  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.

~ o ~

§3. 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).

~ o ~

§4. La tecnica golosa (enumerazione implicita).

Le tecniche euristiche e quelle basate sul rilassamento possono contribuire per semplificare il processo enumerativo, in quanto, individuando le aree dello spazio delle soluzioni che non contengono sicuramente la soluzione ottima, permettono all'algoritmo enumerativo di escludere queste aree (dette visitate implicitamente) dalla ricerca sistematica. Con questo artificio gli algoritmi di Enumerazione Implicita riescono spesso a risolvere in tempi accettabili istanze di dimensioni rilevanti. Si osservi che gli algoritmi di Enumerazione Implicita si ispirano perfettamente al principio “divide et impera”, che affronta la soluzione di un problema complesso suddividendolo in un certo numero di sotto-problemi più semplici.
  In particolare, la tecnica Golosa viene spesso utilizzata per la progettazione di algoritmi per la risoluzione di problemi di ottimizzazione in cui, dato un certo numero di oggetti come input, bisogna scegliere un sottoinsieme di essi che ottimizzi una funzione obiettivo rispettando un certo numero di vincoli. La tecnica golosa effettua la scelta di un elemento alla volta sulla base di qualche criterio di scelta dell’elemento che sembra il più conveniente. Analogamente alla tecnica di Backtracking, la tecnica Golosa esegue il processo di costruzione in stadi. Diversamente dalla tecnica di Backtracking, però, la tecnica Golosa si basa sui seguenti principi:

• Ad ogni stadio i, per la componente i-esima viene scelto il valore che, tra quelli ammissibili, risulta il migliore rispetto ad un determinato criterio; ovviamente, per problemi di ottimizzazione, tale scelta è dipendente dalla funzione obiettivo del problema; la scelta avviene sulla scorta delle informazione disponibili a quello stadio.
• Una volta fatta la scelta per la i-esima componente, si passa a considerare le altre componenti senza più tornare sulla decisione presa

In un algoritmo goloso è quindi del tutto assente l’idea di eseguire tentativi, ossia di eseguire scelte che potrebbero successivamente essere revocate sulla base di una verifica a posteriori delle loro conseguenze. Da qui la conseguenza che non tutti gli algoritmi sono corretti, cioè individuano la risposta del problema per ogni istanza di esso. Effettuare ad ogni stadio la scelta migliore sulla base delle informazioni disponibili a quello stadio non garantisce che alla fine del procedimento la soluzione trovata sia ottima. Può infatti accadere che la scelta ad uno stadio escluda, in stadi successivi, la possibilità di effettuare scelte che sarebbero cruciali per ottenere l’ottimo complessivo. Uno degli aspetti critici dell’uso della tecnica golosa è appunto dimostrare quanto sia ottima la soluzione. La tecnica golosa è utilizzabile anche quando, pur non riuscendo a determinare l’ottimo di un problema, il suo calcolo è estremamente oneroso per cui la soluzione fornita dalla tecnica golosa, che ha tempi di esecuzione polinomiali, può costruire una buona approssimazione dell’ottimo; in questo caso è importante stabilire di quanto la soluzione golosa può discostarsi da quella ottima.

~ o ~

§5. La programmazione dinamica e la ricerca in ampiezza (BFS).

  La Programmazione Dinamica è una tecnica di realizzazione di algoritmi che risolvono un problema utilizzando le soluzioni di sotto-problemi. La differenza con la tecnica divide et impera è che divide et impera intende preliminarmente individuare solo quei sotto-problemi che sono rilevanti per la risoluzione del problema originario (metodo top-down) mentre la programmazione dinamica parte direttamente da tutti i sotto-problemi più piccoli per poi arrivare alla soluzione del problema originario (metodo bottom-up).
Questa tecnica si utilizza quando i sotto-problemi di un dato problema tendono a ripetersi. L'idea di base è quella di calcolare la soluzione a distinti sotto-problemi una volta soltanto, e memorizza tale soluzione in una tabella, in modo tale che esse possa essere usata nel seguito, se occorre.
Nel caso di un problema in cui solo un numero limitato di sotto-problemi è rilevante per determinare la soluzione finale, la tecnica divide et impera risulta più conveniente in quanto l’extra-lavoro per individuare i sotto-problemi è ripagato dal minor numero di sotto-problemi da risolvere. D’altra parte, se tutti o quasi tutti i sotto-problemi devono essere comunque risolti e, addirittura, accade che la soluzione di uno stesso sotto-problema debba essere usata più volte, allora la programmazione dinamica risulta essere la tecnica più conveniente poiché essa parte direttamente dalla soluzione di tutti i problemi di dimensione atomica per ricomporre via via le soluzioni di tutti i sotto-problemi di dimensione maggiori, risolvendo ogni sotto-problema solo una volta e conservando la sua soluzione in una tabella. Tipici problemi che possono essere risolti con questa tecnica sono il calcolo dei numeri di Fibonacci, il calcolo di binomiali, il problema della distanza minima tra tutti i nodi di un grafo.
L’algoritmo per la tecnica della Programmazione Dinamica si comporta come se si effettuasse una visita in profondità dell’albero. Nella teoria dei grafi, la Ricerca in Ampiezza (in inglese Breadth-First Search, BFS) è un algoritmo di ricerca per grafi che partendo da un vertice (o nodo) detto sorgente permette di cercare il cammino fino ad un altro nodo scelto e connesso al nodo sorgente. BFS è un metodo di ricerca non informato, ed ha il suo obiettivo quello di esaminare tutti i nodi del grafo sistematicamente. In altre parole, se il nodo cercato non viene trovato, la ricerca procede in maniera esaustiva su tutti i nodi del grafo.

~ o ~

§6. Resources and Insights.

Fonti ed approfondimenti

  In seguito ho riportato alcuni riferimenti alle fonti che ho consultato durante la redazione di questo articolo e che ti suggerisco di utilizzare per approfondire gli argomenti che ho trattato al suo interno.
(1) Algoritmi enumerativi, Università di Pisa
(2) Elementi di programmazione matematica, F. Maffioli, Casa Editrice Ambrosiana, 2000
(3) Modelli e Algoritmi della Ricerca Operativa, A. Sassano, Franco Angeli, 1999.
(4) Integer Programming, L. Wolsey, Wiley-Interscience, 1998
(5) Programming with Constraints: An Introduction, K Marriot, P.J. Stuckey, MIT Press,1998
(6) Tecniche di programmazione, Digilander-Libero
(7) Ricerca in Ampiezza - Breadth-First Search (BFS), Wikipedia
(8) Ricerca in Profondità - Depth-First Search (DFS), Wikipedia
(9) Approccio "Divide et impera" in Informatica, Wikipedia.
(10) Qual è il problema? Metodi, strategie risolutive, algoritmi, Marco Liverani.

~ o ~

§7. More generally.

Più in generale.

  In this article, we looked at artificial intelligence enumeration techniques. But if you want to examine how Artificial Intelligence can be used in general to help humans solve complex problems, then I invite you to continue consulting the Artificial Intelligence thematic area of the Learning section of TILLL by reading the following article which describes how man in the course of history has always had to solve problems, and how such problems, as man has evolved, have gradually become more and more complicated. Complexity has now reached such high levels that help from modern technologies is essential: electronics, information technology and artificial intelligence
  In questo articolo abbiamo esaminato le tecniche enumerative di intelligenza artificiale. Ma se vuoi esaminare come l'Intelligenza Artificiale può essere utilizzata in generale per aiutare l'uomo nella risoluzione dei problemi complessi, allora ti invito a proseguire la consultazione dell'area tematica Intelligenza Artificiale della sezione Learning di TILLL con la lettura dell’articolo seguente che descrive come l’uomo nel corso della storia ha sempre dovuto risolvere problemi, e come tali problemi, man mano che l'uomo si è evoluto, sono diventati via via sempre più complicati. La complessità oggi ha raggiunto livelli così elevati da rendere indispensabile l'aiuto da parte delle moderne tecnologie: elettroniche, informatiche e dell’intelligenza artificiale

The resolution of complex problems.

La risoluzione dei problemi complessi.

(AI.1)

~ o ~

§8 Stay up to date

Rimani aggiornato

If you are interested in the topics covered in the current article and want to be informed about my most recent updates dealing with them, then I invite you to register:

on the Facebook page

"Artificial Intelligence by Tateo's Interdisciplinary Lifelong Learning" (>)

and at the Pinterest dashboard

"Artificial Intelligence by Tateo's Interdisciplinary Lifelong Learning" (>)

which I dedicated specifically for sharing the most recent changes made to the corresponding thematic area of TILLL~Learning (>).

[IT] Se sei interessato agli argomenti trattati nell'articolo corrente e vuoi essere informato sui miei aggiornamenti più recenti che trattano di essi, allora ti invito a registrarti:

alla pagina Facebook

"Artificial Intelligence by Tateo's Interdisciplinary Lifelong Learning" (>)

ed alla bacheca Pinterest

"Artificial Intelligence by Tateo's Interdisciplinary Lifelong Learning" (>)

che ho dedicato appositamente per la condivisione delle modifiche più recenti apportate all'area tematica corrispondente di TILLL~Learning (>).

~ o ~

§9. Let's keep in touch

Teniamoci in contatto

I hope you enjoyed this article, belonging to the Learning (>) section of the Tateo's Interdisciplinary Lifelong Learning (TILLL) project (>), and that the notes and observations I gathered within it meets your interests. 

  If you want stay tuned with the TILLL project evolution, then I invite you to follow the next upgrades that are published on the TILLL's Blog and on the social media pages dedicated to the TILLL community.

  [IT] Spero che questo articolo, appartenente alla sezione Learning (>) del progetto Tateo's Interdisciplinary Lifelong Learning (TILLL) (>), ti sia piaciuto e che le note e le osservazioni che ho raccolto al suo interno soddisfino i tuoi interessi. 

  Se vuoi rimanere aggiornato sull'evoluzione del progetto TILLL, allora ti invito a seguire i prossimi aggiornamenti che vengono pubblicati sul Blog di TILLL e sulle pagine social dedicate alla community TILLL

  (>) Tateo-Blog, official blog of TILL project

  (>) LinkedIn page dedicated to TILL project

  (>) Facebook page dedicated to TILL project

  (>) Twitter account dedicated to TILL project

  (>) Pinterest account dedicated to TILL project

  (>) Instagram account dedicated to TILL project

~ o ~

§10. Something about me, the founder and author of Tateo~Blog Project.

Qualcosa su di me, il fondatore e sull'autore del progetto Tateo~Blog.

First of all, thank you for visiting one of the pages of my blog. My name is Giovanni Battista Tateo (shortly Bat) and I am the founder and author of a project of Interdisciplinary Lifelong Learning of which the Tateo~Blog (:::) blog is the means of sharing. I was initially an Information Technology expert, and later I became an electronic engineer, specializing in industrial Automation. I'm passionate about Artificial intelligence, Virtual Reality, Simulation, and I'm an expert in Artificial Vision applied to industrial Automation. Currently, and starting four years ago, I am employed as a Proposal Engineer at Mer Mec S.p.A. (:::) company. Previously, starting in 2004, I was employed, always at the same company, as a Designer of Artificial Vision Systems and Image Processing Algorithms, applied in particular to Railway Diagnostics. I am a supporter and promoter of Lifelong Learning, Social Networking and Knowledge Sharing by means of the web. If you want more details about me, visit the About Me (:::) page.

Innanzitutto ti ringrazio per aver visitato una delle pagine del mio blog. Mi chiamo Giovanni Battista Tateo (brevemente Bat) e sono il fondatore e l'autore di un progetto Lifelong Learning Interdisciplinare di cui il blog Tateo~Blog (:::) ne è il mezzo di condivisione. Sono stato in principio un esperto di Informatica, e in seguito sono diventato un Ingegnere Elettronico, specializzato in Automazione Industriale. Sono un appassionato di Intelligenza Artificiale, Realtà Virtuale, Simulazione, e sono un esperto di Visione Artificiale applicata all'Automazione Industriale. Attualmente, ed a partire dall'anno 2016, sono impiegato come Proposal Engineer presso la società Mer Mec S.p.A. (:::). Precedentemente, a partire dal 2004, sono stato impiegato, sempre presso la stessa società, come Progettista di Sistemi di Visione Artificiale e di Algoritmi di Elaborazione delle Immagini, applicati in particolare alla Diagnostica Ferroviaria. Sono un sostenitore e promotore dell'apprendimento permanente, dei social network e della condivisione delle conoscenze tramite il web. Se vuoi ulteriori dettagli su di me, visita la pagine About Me (:::).

  References to contact me. Following you can find my personal references that you can use if you want to contact me directly, and the links to my social accounts that you can use to follow me or to keep in touch with me by means of social media networks.

  {Riferimenti per contattarmi. In seguito puoi trovare i miei riferimenti personali che puoi utilizzare se vuoi contattarmi personalmente, ed i collegamenti ai miei account social che puoi utilizzare per seguirmi e rimanere in contatto con me tramite le reti di social media}

Eng. Tateo Giovanni Battista

    - e-mail: tateogb@libero.it (send e-mail)

    - phone / WhatsApp : (+39) 388 8419726

    - Skype (link)

    - LinkedIn account (link)

    - Facebook account (link)

    - Twitter account (link)

    - Instagram account (link)

    - Pinterest account (link)

-----------------------------------------

TILLL~Learning © January 2, 2022