China
Africa
Explore chapters and articles related to this topic
Top-Down Artificial Intelligence
Published in Robert H. Chen, Chelsea Chen, Artificial Intelligence, 2022
Despite being called “progressive deepening” the iterative deepening depth-first search (IDDFS) in practice reduces the ultimate tree search depth by earlier iteration of a probably beneficial branch (for example because it is a good move based on some chess heuristic) until a good node is found in that branch.
On searching explanatory argumentation graphs
Published in Journal of Applied Non-Classical Logics, 2020
As local search, various options are possible, see e.g. Gendreau and Potvin (2010) and Fürnkranz et al. (2014). We adopt an iterative deepening depth-first search, yielding thus an ‘iterated local iterative deepening depth-first search’. The iterative deepening depth search iterates a depth-limited depth-first search with increasing depth limits until an interesting graph is found. As alluded to earlier, the main reason for a local deepening depth-first search is that such a search may be less likely to suffer from myopia than basic hill-climbing search approaches.
Variable-depth local search heuristic for assembly line balancing problems
Published in International Journal of Production Research, 2023
Eduardo Álvarez-Miranda, Jordi Pereira, Camila Vargas, Mariona Vilà
The implementation of the local search process is structured as a graph search procedure. Thus, any classic graph search procedure can be used to construct and explore the graph. Two of these procedures were tested in our implementation: a depth-first search and an iterative deepening depth-first search. Both strategies are classical graph exploration strategies (Cormen et al. 2009) with low memory requirements owing to their use of recursive implementations. The two procedures differ in the order in which the solutions are considered. Depth-first search explores the graph by taking edges to the maximum depth before going back and considering alternative decisions, whereas iterative deepening depth-first search first explores all vertices separated by an edge from the root vertex, then applies a depth-first search, constraining the depth of the vertices explored to one edge farther from the root vertex than in the last depth-first step, and repeating the depth-first search step until vertices λ edges away from the root vertex are explored. Therefore, the depth-first search can return an improvement that requires a number of shifts larger than the minimum number necessary to improve the incumbent solution, which would not be possible in an iterative deepening depth-first search. To illustrate the differences between both strategies, we consider the order in which the vertices of the graph depicted in Figure 2 are visited by each strategy considering that we always explore the left-most branch first. The depth-first search strategy would explore vertices b, f, l, g, m and h, reporting h as the new incumbent; while the iterative deepening strategy would visit vertices b, c, d and e during the initial step (with depth limit equal to 1) and then proceed with a second step (with maximum depth set to 2) in which the search visits vertices b, f, g and h, and returns the solution represented by vertex h as the new incumbent.