Problem Solving & Search Algorithms

Presentation Structure

• Methods used in problem solving are covered
• Problem formulation and state space concepts are presented
• Covers both blind/uninformed and intelligent/informed search techniques

Solution Search Methodology

• Start from an initial state
• Execute the goal test
• Expand current states to create successor states if a solution isn't found
• Execute an objective test
• Implement a chosen search strategy to pick a state for expansion if solution remains unfound
• Repeat until solution is determined or the process exhausts all options

Best First Search

• A general approach where the node is selected based on the minimum value of an evaluation function f(n)

Search Data Structures

• Search trees have nodes, with leaf nodes having no successors or unexpanded ones
• It is important to distinguish between state space and search tree
• Tree nodes consist of five components: state, parent node, operator, path cost and depth
• Borders/Frontiers represent a set of nodes ready for expansion with operations like IS-EMPTY, POP, TOP, and ADD

Search Strategy Evaluation

• Completeness: Does it always find a solution if one exists?
• Time complexity: How long does it take (total number of nodes generated)?
• Space complexity: How much memory does it need?
• Optimality: Does it always discover the best (least-cost) solution?
• Time and space complexity are measured by: the branching factor b, the depth of least-cost d, and the maximum depth of the state space m

Search Strategies

• Two types of strategies are, uninformed (blind) and informed (heuristic/intelligent) search

Breadth first search

• Strategy expands nodes at the shallowest depth first
• Systematic search
• Computationally expensive regarding space and time
• Has exponential complexity
• Only small problems can be solved

Uniform Cost Search

• Always expands the lowest-cost border node measured by solution cost function
• Breadth First Search is equal to Uniform Cost Search if g(n) = Depth(n)

Depth first search

• Expands the deepest node in the tree
• Requires minimal memory
• Good search with large quantity of solutions
• Can't be used with infinite trees because it gets locked in incorrect branches
• Has time complexity of O(b^m) and space complexity of O(bm)
• It becomes a search with limited depth if there is a defined limit depth

Iterative Deepening Search

• Performs depth-limited search iteratively, incrementing the depth limit each time
• Has time complexity of O(b^d) and space complexity of O(b^d)
• A suitable strategy with search problems, since the depth of solutions are not known

Iterative Deepening Search Properties

• Nodes at depth d are generated once, nodes at next-to-bottom level are generated twice, and so on, up to the children of the root, that are generated d times.
• Its is a preferred uninformed search method for when solutions are not known relating solution depth or when the state spaces cant be fit in memory

Bidirectional Search

• Simultaneously searches forward from the initial state and backward from the target
• Reduces complexity over time

Bidirectional Search Problems

• Generating predecessors
• The proliferation of objective states
• Matching between the two searches
• Determining the appropriate search type for both halves

Repeated States

• Failure to detect them results in linear problems turning exponential
• Do not return to the previous state, and don't create cycles
• Avoid using any repeated states, the computational cost must be weighed

Search Challenges

• These can be addressed as search problems using various search strategies, including: Missionaries and Cannibals, Bucket Filling problem, Towers of Hanoi, Cryptograms, 8-Queens and N-Queens, 8-Puzzle and N-Puzzle. Solutions should be generic versions that can solve different data points

Informed Search

• Uses problem-specific intelligence to guide the search, avoiding wandering aimlessly
• Defined by choosing the order of expansion of the nodes
• Utilizes evaluation functions to assess the interest of expanding a node
• Greedy search estimates the distance to the solution, and A* Algorithm estimates cost of the best path to the solution using functions

Greedy Search

• Expands the node closest to the solution
• h(n) is the estimated cost of the shortest path from state n to the objective
• It can get stuck in cycles and may not find an optimal solution without detecting repeated states
• Time complexity is O(b^m) but can decrease with good heuristic functions
• Keeps all nodes in memory

A* Algorithm

• Combined with greedy search and uniform search minimize the path already carried out with the minimum solution
• Uses the function f(n) = g(n) + h(n)
• It calculates the cheapest solution that connects across node n
• Is optimal and complete with time complexity that depends on the quality of the heuristic
• Keeps all nodes in memory

A* Algorithm Optimality

• When a sub-optimal G2 objective exists on the list, with ‘n’ being an unexpanded node towards optimal goal G1: f(G2) = g(G2) because h(G2) = 0, f(G2) > g(G1) because G2 is sub-optimal, f(G2) >= f(n) because h is admissible, A* Algorithm never chooses G2 for expansion

Heuristic Functions - 8 Puzzle

• A typical 20-step has solutions with an average branching factor of 3
• Number of states being 3^20 = 3.5x10^9
• The º States excluding repeated states = 9!= 362880

Heuristics

• h1: Number of pieces outside the correct placement, and h2: sum of pieces distances to their correction positions.

Problem Relaxation Heuristics

• Piece can move from A to B if A is adjacent to B and B is empty
• a) Piece can move from A to B if A is adjacent to B
• b) Piece can be moved from A to B if B is empty
• c) Piece can be moved from A to B

Weighted A* Search

• Explores fewer nodes at the expense of solution accuracy
• If an A* search allows the use of an Inadmissible Heuristic, it risks missing the optimal solution.
• Road engineers use a detour to know the concept of the Detour Index: Multiplier applied to the straight-line distance to account for typical curvature of roads and has localities between ranges 1.2 and 1.6.