Brute-force search strategies


Brute-force search strategies

They're the easiest to use because they don't require domain-specific expertise, and they function well with a limited number of states.

Requirements −

  • Description of the state
  • a collection of acceptable operators
  • The starting point
  • Description of the desired condition

Breadth-First Search

It starts at the root node, then continues to the next level neighbours after exploring the adjacent nodes. It creates one tree at a time until it finds the solution. The FIFO queue data structure can be used to implement it.

The number of nodes at level d = bd if branching factor (average number of child nodes for a given node) = b and depth = d.

In the worst-case scenario, the total number of nodes produced is b + b2 + b3 +... + bd.

The number of nodes determines its complexity, and it can check for duplicate nodes.

Depth-First Search

It's written in recursion and uses a LIFO stack data structure. The same collection of nodes is created with the Breadth-First approach but in a different sequence.

The space required to store nodes on a single path is linear since they are stored from root to leaf node in each iteration. The storage space is bm with a branching factor of b and a depth of m.

Bidirectional Search

It looks for a joint state by searching forward from the beginning state and backward from the goal state until they meet.

Concatenate the path from the beginning state with the inverse path from the destination state. Only half of the whole path is searched in each search.

Uniform Cost Search

Sorting makes the journey to a node more expensive, and it continuously extends the node with the lowest cost. If each transition has the exact cost, it's the same as a Breadth-First search.

Iterative Deepening Depth-First Search

It runs a depth-first search to level 1, then restarts, performing a full depth-first search to level 2, and so on until the answer is discovered.

It does not build a node until all of the lower nodes have been created, and it merely stores a node stack. The method is finished when it reaches depth d and finds a solution. Bd is the number of nodes produced at depth d, while bd-1 is the number of nodes created at depth d-1.