China
Africa
Explore chapters and articles related to this topic
Problem Solving by Intelligent Search
Published in Konar Amit, Artificial Intelligence and Soft Computing, 2018
The iterative deepening search algorithm, discussed earlier, searches the goal node in a depth first manner at limited depth. In each pass the depth is increased by one level to test the presence of the goal node in that level. The A* algorithm, on the other hand, in each pass, selects the least cost (f) node for expansion. The iterative deepening A* (or IDA*) algorithm presented below attempts to combine the partial features of iterative deepening and A* algorithms together. Here, the heuristic measure is used to check the depth cut-off, rather than the order of the selection of nodes for expansion. The algorithm is formally presented below.
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.