Un-Informed Search

Un-Informed Search

• This section covers several search strategies that come under the heading of uninformed search (also called blind search).
• The term means that the strategies have no additional information about states beyond that provided in the problem definition.
• All they can do is generate successors and distinguish a goal state from a non-goal state.
• All search strategies are distinguished by the order in which nodes are expanded.
• Strategies that know whether one non-goal state is “more promising” than another are called informed search or heuristic search strategies.

Un-Informed Search

Types of Un-Informed Search:

• Breadth-first search (BFS)
• Uniform-cost search (UCS)
• Depth-first search (DFS)
• Depth-limited search (DLS)
• Iterative deepening depth-first search
• Bidirectional search

I. Breadth-first search

• Breadth-first search is a simple strategy in which the root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on.
• In general, all the nodes are expanded at a given depth in the search tree before any nodes at the next level are expanded.
• Breadth-first search is an instance of the general graph-search algorithm in which the shallowest unexpanded node is chosen for expansion.
• BFS implemented using FIFO queue data structure.
• New nodes go to the back of the queue, and old nodes, which are shallower than the new nodes, get expanded first.
• The algorithm, following the general template for graph search, discards any new path to a state already in the frontier or explored set; it is easy to see that any such path must be at least as deep as the one already found.
• Thus, breadth-first search always has the shallowest path to every node on the frontier.
• Breadth-first search always expands the shallowest unexpanded node. To achieve this, we will take the help of a First-in First-out (FIFO) queue for the frontier. The newly generated nodes always go to the back of the queue, while the older nodes get expanded first

​

I. Breadth-first search

I. Breadth-first search

• complete—if the shallowest goal node is at some finite depth d, breadth-first search will eventually find it after generating all shallower nodes (provided the branching factor b is finite).
• Note that as soon as a goal node is generated, we know it is the shallowest goal node because all shallower nodes must have been generated already and failed the goal test.
• The shallowest goal node is not necessarily the optimal one; technically, breadth-first search is optimal if the path cost is a nondecreasing function of the depth of the node.
• The most common such scenario is that all actions have the same cost.
• Imagine searching a uniform tree where every state has b successors.
• The root of the search tree generates b nodes at the first level
• Each of which generates b more nodes, for a total of b2 at the second level.
• Each of which generates b more nodes, yielding b3 nodes at the third level, and so on.
• Now suppose that solution is at depth d. in worst case, it is the last node generated at that level. Then the total number of nodes generated is

​

​

Algorithm

1. Enter starting node on queue.
2. If -> queue is empty, then return failure and stop
3. If -> first element on queue is goal node, then return success and stop
4. Else -> Remove and expand first element from queue and place children at end of queue
5. Go to step(2).

​

​

​

Applications of Breadth-first search

Crawlers in Search Engines:

• Breadth-First Search is one of the main algorithms used for indexing web pages. The algorithm starts traversing from the source page and follows all the links associated with the page. Here each web page will be considered as a node in a graph.

GPS Navigation systems:

• Breadth-First Search is one of the best algorithms used to find neighboring locations by using the GPS system.

Find the Shortest Path & Minimum Spanning Tree for an unweighted graph:

• When it comes to an unweighted graph, calculating the shortest path is quite simple since the idea behind the shortest path is to choose a path with the least number of edges.

Broadcasting:

• Networking makes use of what we call as packets for communication. These packets follow a traversal method to reach various networking nodes. One of the most commonly used traversal methods is Breadth-First Search.

Peer to Peer Networking:

• Breadth-First Search can be used as a traversal method to find all the neighboring nodes in a Peer to Peer Network. For example, BitTorrent uses Breadth-First Search for peer to peer communication.

​

​

​

​

II. Depth-First Search Algorithm

• Depth-first search always expands the deepest node in the current frontier of the search tree.
• The search proceeds immediately to the deepest level of the search tree, where the nodes have no successors.
• As those nodes are expanded, they are dropped from the frontier, so then the search “backs up” to the next deepest node that still has unexplored successors.
• The depth-first search algorithm is an instance of the graph-search algorithm.
• whereas breadth-first-search uses a FIFO queue, depth-first search uses a LIFO queue.
• A LIFO queue means that the most recently generated node is chosen for expansion.
• This must be the deepest unexpanded node because it is one deeper than its parent—which, in turn, was the deepest unexpanded node when it was selected.
• As an alternative to the GRAPH-SEARCH-style implementation, it is common to implement depth-first search with a recursive function that calls itself on each of its children in turn.

​

​

II. Depth-First Search Algorithm

II. Depth-First Search Algorithm

1. Push the root node on the stack (LIFO QUEUE)
2. While(stack is not empty)

a) pop a node from the stack

1) if -> node is goal return success

2) push all children nodes on to the stack

3) Return failure

II. Depth-First Search Algorithm

Applications of DFS:

• Finding connected components: DFS can be used to identify all the connected components in an undirected graph.
• Cycle detection: DFS can be used to detect cycles in a graph. If a node is visited again during a DFS traversal, it indicates that there is a cycle in the graph.
• Topological sorting: DFS can be used to perform topological sorting on a directed acyclic graph (DAG). In topological sorting, the nodes of a graph are ordered in such a way that for every directed edge from node A to node B, node A comes before node B in the ordering.
• Pathfinding: DFS can be used to find a path between two nodes in a graph.
• Solving puzzles: DFS can be used to solve puzzles such as mazes, where the goal is to find a path from the start to the end.
• Spanning trees: DFS can be used to construct a spanning tree of a graph. A spanning tree is a subgraph of a connected graph that includes all the vertices of the original graph and is also a tree.
• Backtracking: DFS can be used for backtracking in algorithms like the N-Queens problem or Sudoku.

III. Uniform-cost search

• When all step costs are equal, breadth-first search is optimal because it always expands the shallowest unexpanded node.
• By a simple extension, we can find an algorithm that is optimal with any step-cost function.
• Instead of expanding the shallowest node, uniform-cost search expands the node n with the lowest path cost g(n).
• This is done by storing the frontier as a priority queue ordered by g.

III. Uniform-cost search

III. Uniform-cost search

III. Uniform-cost search

IV. Depth-limited search

• The embarrassing failure of depth-first search in infinite state spaces can be alleviated by supplying depth-first search with a predetermined depth limit l. That is, nodes at depth are l treated as if they have no successors. This approach is called depth-limited search.
• The depth limit solves the infinite-path problem. Unfortunately, it also introduces an additional source of incompleteness if we choose l < d, that is, the shallowest goal is beyond the depth limit. (This is likely when d is unknown.)
• Depth-limited search will also be nonoptimal if we choose l > d.
• Its time complexity is O(b ^l) and its space complexity is O(b l).
• Depth-first search can be viewed as a special case of depth-limited search with l=∞.
• it can be implemented as a simple recursive algorithm

IV. Depth-limited search

IV. Depth-limited search

IV. Depth-limited search

depth-limited search can terminate with two kinds of failure:

• the standard failure value indicates no solution;
• the cutoff value indicates no solution within the depth limit.

Depth-limited search

V. Iterative deepening depth-first search

• Iterative deepening search (or iterative deepening depth-first search) is a general strategy, often used in combination with depth-first tree search, that finds the best depth limit.
• It does this by gradually increasing the limit—first 0, then 1, then 2, and so on—until a goal is found. This will occur when the depth limit reaches d, the depth of the shallowest goal node.
• Iterative deepening combines the benefits of depth-first and breadth-first search.
• Like depth-first search, its memory requirements are modest: O(bd) to be precise.
• Like breadth-first search, it is complete when the branching factor is finite and optimal when the path cost is a nondecreasing function of the depth of the node.
• four iterations of ITERATIVE-DEEPENING-SEARCH on a binary search tree, where the solution is found on the fourth iteration.
• general, iterative deepening is the preferred uninformed search method when the search space is large and the depth of the solution is not known.

Depth-limited search

Depth-limited search

VI. Bidirectional search

• The idea behind bidirectional search is to run two simultaneous searches—one forward from the initial state and the other backward from the goal—hoping that the two searches meet in the middle.
• The motivation is that b^d/2 + b^d/2 is much less than bd, or in the figure, the area of the two small circles is less than the area of one big circle centered on the start and reaching to the goal.
• Bidirectional search is implemented by replacing the goal test with a check to see whether the frontiers of the two searches intersect; if they do, a solution has been found.