CODEWITHSUNDEEP
algorithmdepth-first-searchbreadth-first-search
Jim
Jim

Reputation: 239

Algorithm for "balanced" breadth-first search

I'm looking for references for an algorithm that conducts a breadth-first tree search in a balanced manner that is resilient in a situation where

Consider this simple tree (modified from this post):

     A
   /   \
  B     C
 /     /  \
D     E    F
|    /|\    \
G   HIJ...   K

Depth-first visits nodes in this order:

A B D G C E H I J ... F K

Breadth-first visits nodes in this order:

A B C D E F G H I J ... K

The balanced breadth-first algorithm that I have in mind would visit nodes in this order:

A B C D E G F H K I J ...

Note how

G is deeper than F, but it is an only child of B whereas F is a second child of C and must share its search priority with E. Similarly between K and the many children H, I, J, ... of E.

I call this "balanced" because a node with lots of children cannot choke the algorithm. Concretely, if E has šœ” (infinitely) many nodes then a pure breadth-first strategy would never reach K, whereas the "balanced" algorithm would still reach K after H but before the other children of E.

(The reader who does not like šœ” can attain a similar effect with a large but still finite number such as "the greatest number of steps any practical search algorithm will ever make, plus 1".)

I can only imagine that this style of search or something like it must have been the subject of much research and practical application. I would be grateful to be pointed in the right direction. Thank you.

Upvotes: 1

Views: 95

Answers (2)

n. m. could be an AI
n. m. could be an AI

Reputation: 120049

Transform your tree to a different kind of representation. In this new representation, each node has at most two links: one to its leftmost child, and one to its right sibling.

     A
   /   \
  B     C
 /     /  \
D     E    F
|    /|\    \
G   HIJ...   K

Ā  ā‡“

     A
   /  
  B --> C
 /     /  
D     E -> F
|    /      \
G   /        K
   /
  H -> I -> J -> ...

Then treat this representation as a normal binary tree, and traverse it breadth-first. It may have an infinite height, but like with any binary tree, the width at any particular level is finite.

Upvotes: 2

MrSmith42
MrSmith42

Reputation: 10161

depth-first-search, breadth-first-search, A*-search (and others) only differ in how you handle the list of "nodes still to visit".
(I assume you always process the node at the start of the list next)

  • depth-first-search: append new nodes at the front of the list
  • breadth-first-search: add new nodes to the end of the list
  • A*-search: insert new nodes in the list according to costs+heuristic

So you need to formalize how to insert new nodes to the list to fulfill your requirements.

Upvotes: 0

Related Questions