002 Search Strategies

Last updated Nov 7, 2022 Edit Source

• Moc

#moc

• Completeness: Does it always find a solution if one exists?
• Optimality: Does it always find the best solution? Shortest Path Problem
• Average Branching Factor: average number of successors of any node $$ABF=No.of\\ Nodes/No.of\\ non\\ leaf\\ nodes$$

• # Uninformed Search

  • Depth First Search
  • Breadth First Search
  • Iterative Deepening Search
  • Path Cost
    • Uniform Cost Search
    • Dijkstra’s Algorithm

• # Informed Search (Heuristics)

  • Greedy Best First Search
  • A-Star Search

d: depth of the optimal solution m: maximum depth l: cut off maximum depth