I am reading Artificial Intelligence: Making Machines "Think" by Neill Graham. He gives an overview of graph search using either the breadth-first (BF) or depth-first (DF) search algorithms, and describes the role of of a queue in BF search vs a stack in DF search. It got me thinking hypothetically about an intermediate approach in which the usage of a data structure is, in a probabilistic fashion, treated as either a queue or a stack in a graph search. I'm imagining it would be like a bandit problem where switching between BF and DF would be a stochastic function of how much BF vs DF has been done.

What I've described is not fully specified as there may be different algorithms that implement this strategy. Even so, do such algorithms exist? Please give an example.

  • $\begingroup$ It seems like what you are describing is similar to A* search on unweighted graphs. It would decide to increase the "breadth" or the "depth" heuristically, which in some sense is probabilistic dependent on input. Also, while not probabilistic, there is a search algorithm called iterative deepening depth first search which tries to take advantage of both algorithms (space complexity of DFS and guarantees from BFS). $\endgroup$ – ryan Apr 22 '19 at 17:42
  • $\begingroup$ If you are looking for a search, I wouldn't think the stochastic function would be based on how much BF and DF have been, but rather on a heuristic to the node you're searching for. Unless you're not necessarily looking for shortest path, but rather just finding the node, in which case this might be more plausible. Could you elaborate more on what you're looking for (in terms of shortest path vs general search)? Also I'd suggest checking through these search algorithms. $\endgroup$ – ryan Apr 22 '19 at 17:46
  • $\begingroup$ See also Combining Breadth-First and Depth-First Strategies in Searching for Treewidth. While skimming, I don't think this is probabilistic, but shows a combination of BFS and DFS that can be applied to graph search. $\endgroup$ – ryan Apr 22 '19 at 18:12
  • $\begingroup$ How about Monte Carlo tree search? $\endgroup$ – John L. Apr 22 '19 at 18:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.