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