Uninformed Search in AI

Uninformed Search

• Also known as blind search and naive search.
• It is a class of general-purpose algorithms.
• Operates in a brute force manner.
• Can apply to a variety of search problems.
• Inefficient because it doesn't account for the target problem.

Search and AI

• Search is a key aspect to AI.
• Problem solving in AI is fundamentally a search.
• Search is a key computational mechanism in many AI agents.
• It is a problem-solving technique that enumerates a problem space from an initial position in search of a goal position (or solution).
• The manner in which the problem space is searched is defined by the search algorithm or strategy.
• Search strategies offer different ways to enumerate the search space.
• How well a strategy works depends on the problem at hand.

General State Space Search

• Solution space is thought of in terms of actions we can take and the new state of the environment as we perform those actions.
• As one of multiple possible actions is taken, the environment changes and opens up alternatives for new actions.
• The problem of search finds a sequence of operators that transition from the start to goal state, and that sequence of operators is the solution.

Search in Puzzle Space

• The "Towers of Hanoi" puzzle exemplifies a state space for solving a puzzle.
• Move disks from one peg to another, one at a time, under constraints.
• Each disk has a unique size.
• A larger disk cannot sit on a smaller disk.
• Initially, disks are on one peg in increasing size order.
• The overall goal is to move all disks to the last peg.

Trees, Graphs, and Representation

• A graph is a finite set of nodes (vertices) connected by edges (arcs).
• A loop (cycle) can exist in a graph where an arc (edge) leads back to the original node.
• Graphs can be undirected or directed (digraph), where direction is implicit in the arc.
• Arcs have weights, where a cost can be associated with a path.
• Graphs demonstrate connectivity.
• Graphs are connected because every pair of nodes is connected by a path, and complete if every node connects to every node by an arc.
• A tree is a special connected graph with no cycles.
• Representing a graph is simple, and one of the ways to represent it is with the adjacency matrix.

Common Orders of Search Functions

• O-Notation Order is used
• O(1) Constant, regardless of node count.
• O(n) Linear, consistent with node count.
• O(log n) Logarithmic.
• O(n²) Quadratic.
• O(cn) Geometric.
• O(n!) Combinatorial.
• Big-O notation measures worst-case complexity.
• Algorithms are compared by space (memory required) and time complexity (worst-case time to find a solution).

General Search Paradigms

• Generate and Test: Potential solutions are generated and checked. The process stops when a solution is found, otherwise repeats until a solution is found.
• Random Search: Randomly selects a solution from the current state by selecting a valid operator. It stops when goal state is reached.
• All of these are blind methods of search.

Depth-First Search (DFS)

• Starts at the root node of the graph
• Exhaustively searches each branch to its greatest depth before backtracking to unexplored branches.
• Nodes found but not yet viewed are stored in a LIFO (Last In, First Out) queue, a stack.
• Space complexity is O(bd).
• Time complexity is geometric, at O(bd).

Depth-Limited Search (DLS)

• Modification of depth-first search that minimizes the search algorithm's depth.
• Starts with root and goal nodes, plus a set depth the algorithm will not descend beyond.
• Nodes below the set depth are omitted from the search.
• Halts search indefinitely at a pre-imposed depth to avoid cycles.

Iterative Deepening Search (IDS)

• Derivative of DLS and blends depth-first and breadth-first search features.
• Performs DLS searches with increased depths until goal is found or no nodes can be enumerated.
• Depth begins at one, increasing until goal is found or nodes are fully enumerated.
• Minimizing search depth forces the breadth of the graph to also search.
• Should goal not be found, the permitted search depth increases and the algorithm restarts.
• Not susceptible to cycles and finds the goal nearest to the root node.
• It will always find the best solution, making it complete and optimal, unlike DFS and DLS.

Breadth-First Search (BFS)

• The graph is searched from the root node in order of the distance from the root.
• It is guaranteed to find the best possible (shallowest) solution in a non-weighted graph.
• Checks each node nearest the root before descending to the next level. This is opposed to DFS which digs deep down into the graph, progressing further and further from the root.
• Implementation uses a FIFO (first-in-first-out) queue.
• As new nodes are found, they are checked against the goal is not found, the new nodes are added to the queue.
• The oldest node is dequeued (FIFO order) to continue the search.
• The disadvantage is that each node searched must be stored, so space complexity is O(bd). Depth of the tree does not have to be fully searched as d in this context is the depth of the solution.
• Time complexity is O(bd).

Bidirectional Search

• Derivative of BFS, operating two breadth-first searches simultaneously, one from root, one from the goal node.
• The two searches meet in the middle and a path can be reconstructed from the root to goal.
• Meeting location defines when a common node is found.
• This search requires that the goal is known in the graph, which is not always practical.
• Time and space complexity is O(bd/2) because only half the depth of the tree needs to be searched.
• It is based on BFS, and hence both complete and optimal.

Uniform-Cost Search (UCS)

• An uninformed search method that does not use a heuristic.
• It measures the actual cost of the path without trying to estimate it.
• Algorithm uses accumulated path cost and a priority queue to determine path to evaluate.

Algorithm Advantages

• Each algorithm has advantages and disadvantages based on the graph to be searched.
• BFS is best if the graph's branching factor is small.
• Is a good choice if a tree is deep, but a solution is known to be shallow in the graph.
• In a weighted graph, UCS should be used as it finds the best solution when DFS and BFS will not.