Uninformed Search

Uninformed search, also known as blind search, is a search technique used in artificial intelligence and computer science to explore a problem space without having any prior knowledge about the structure or characteristics of the space. Uninformed search algorithms make decisions solely based on the available information and do not incorporate domain-specific knowledge or heuristics.

Here are some commonly used uninformed search algorithms:

1. Breadth-First Search (BFS): BFS explores a problem space by systematically expanding all the neighboring nodes of the current node before moving to the next level of nodes. It guarantees the shortest path to the goal if the path cost is uniform, but it may consume a lot of memory and time for large or infinite state spaces.
2. Depth-First Search (DFS): DFS explores a problem space by traversing as far as possible along each branch before backtracking. It explores the depth of a branch first before moving to other branches. DFS may not guarantee the shortest path to the goal, but it is memory-efficient as it only needs to store the path from the root to the current node.
3. Iterative Deepening Depth-First Search (IDDFS): IDDFS is a combination of BFS and DFS. It repeatedly performs DFS with increasing depth limits until a goal node is found. IDDFS combines the memory efficiency of DFS with the completeness and optimality of BFS.
4. Uniform Cost Search (UCS): UCS explores a problem space by considering the cost associated with each path. It expands the nodes with the lowest path cost first. UCS guarantees the optimal solution in terms of path cost, but it can be computationally expensive if the cost varies widely.
5. Depth-Limited Search (DLS): DLS is similar to DFS but with a predefined depth limit. It restricts the depth of exploration, allowing the search to terminate within a specific depth. DLS can be useful when the depth of the solution is known or limited.

Uninformed search algorithms are suitable when there is limited or no prior knowledge about the problem space. They are applicable in situations where the problem structure is unknown, or the search space is small enough to explore exhaustively. However, uninformed search algorithms may suffer from inefficiency, especially in large or complex problem spaces, as they do not exploit any domain-specific information or heuristics to guide the search process.

Uninformed Search Algorithms

Uninformed search is a class of general-purpose search algorithms which operates in brute force-way. Uninformed search algorithms do not have additional information about state or search space other than how to traverse the tree, so it is also called blind search.

Following are the various types of uninformed search algorithms:

1. Breadth-first Search
2. Depth-first Search
3. Depth-limited Search
4. Iterative deepening depth-first search
5. Uniform cost search
6. Bidirectional Search

1. Breadth-first Search:

• Breadth-first search is the most common search strategy for traversing a tree or graph. This algorithm searches breadthwise in a tree or graph, so it is called breadth-first search.
• BFS algorithm starts searching from the root node of the tree and expands all successor node at the current level before moving to nodes of next level.
• The breadth-first search algorithm is an example of a general-graph search algorithm.
• Breadth-first search implemented using FIFO queue data structure.

Advantages:

• BFS will provide a solution if any solution exists.
• If there are more than one solutions for a given problem, then BFS will provide the minimal solution which requires the least number of steps.

Disadvantages:

• It requires lots of memory since each level of the tree must be saved into memory to expand the next level.
• BFS needs lots of time if the solution is far away from the root node.