Solving search problems

Definition of search problems

deterministic manner

• computing the sinus of an angle or the square root of a number
• stochastic manner
  • real-world problems ⇒ design of ABS
  • involve the search of a solution ⇒ AI’s methods

problem definition involves:

• search space
  • all possible states
  • representation
    • explicit – construction of all possible states
    • default – by using some data structures and some functions (operators)
  • one or more initial state
  • one or more final states
  • one or more paths
    • more successive states
  • a set of rules (actions)
    • successor functions (operators) – next state after a given one
    • cost functions that evaluate
      • how a state is mapped into another state
      • an entire path
    • objective functions that check if a state is final or not

solving by search

• examination of all possible states in order to identify
  • a path from the initial state to the final state
  • an optimal state
• the search space = all possible states and the operators that map them

topology of search strategies

• Solution generation
  • Constructive search
    • solution is identified step by step
    • ex. TSP
  • Perturbative search
    • a possible solution is modified in order to obtain another possible solution
    • ex. SAT - Propositional Satisfiability Problem
• Search space navigation
  • Systematic search
    • The entire search space is visited
      • Solution identification (if it exists) ⇒ complete algorithms
  • Local search
    • Moving from a point of the search space into a neighbour point ⇒ incomplete algorithms
    • A state can be visited more times
• Certain items of the search
  • Deterministic search
    • Algorithms that exactly identify the solution
  • Stochastic search
    • Algorithms that approximate the solution
• Search space exploration
  • Sequential search
  • Parallel search
• Number of objectives
  • Single-objective search
    • The solution must respect a single condition/constraint
  • Multi-objective search
    • The solution must respect more conditions/constraints
• Number of solutions
  • single-modal search
    • There is a single optimal solution
  • multi-modal search
    • There are more optimal solutions
• Algorithm
  • Search over a finite number of steps
  • Iterative search
    • The algorithms converge through the optimal solutions
  • Heuristic search
    • The algorithms provide an approximation of the solution
• Search mechanism
  • traditional search
  • modern search