Show Menu
Cheatography

Aritificial Intelligence Cheat Sheet Cheat Sheet by [deleted]

Search Methods

Tree Search
Expand nodes using gradients
Graph Search
Avoids revisiting nodes and ensure efficiency

Uninformed search

Uniform cost search
aka Cheape­st-­first
Add visited node to Explored and add its neighbors to the frontier
Visit cheapest node in the frontier
Move to next cheapest if all neighbors are explored
Iterative deepening
Iterat­ively calls depth-­limited search
Initialize frontier with root
If not goal, remove from frontier and expand
If at the end of depth, terminate and start over
Repeat until goal is found
Guaranteed to find optimal path
More efficient than DFS
Time comple­xity: O(b^d) Space comple­xity: O(d)
Bidire­ctional
Finds shortest path of a grpah

Informed Search

Best-first search
Choose unvisited node with the best heuristic value to visit next
Same as lowest cost BFS
Greedy best-first search
Uses heuristic to get the node closest to the goal
Bad perfor­mance if heuristic is bad
Does NOT consider cost of getting to the node
A* search
Always expand to node with minimum f
Evaluate cost of getting to goal using heuristics
f(n) = g(n)+h(n) where g is cost to get to n
Uses priority queue
Heuristics
Cost to get to the goal
Admissible herustic
Optimistic model for estimating cost to reach the goal
Never overes­timates
h(n) <= c(n) where c is actual cost
Consistent heuristic
h(n) <= c(n, a, n') + h(n')
Immediate path costs less than longer path
Consistent ⟹ Admissible

Consistent heuristic

Advers­arial Search

Hill climbing
Method of local search
Only move to neighbors to find the max
Does NOT guarantee to find optimal
Simulated annealing
Method of local search
Combine hill climbing and random walk
Always find global max
Local beam
Generate k random states
Generate successors of all k states
If goal stop; else, pick k best successors and repeat
Different from hill-c­limbing since inform­ation is shared between k points
Genetic algorithm
Cross-Over and mutation
Decomposes strands of DNA and permute
Produces children by: Selection, Cross-­over, Mutation
 

Minimax Tree

◎ Max node
☐ Min node

α-β Pruning

function alphabeta(node, depth, α, β, maximizingPlayer)
  if depth =  or node is a terminal node
      return the heuristic value of node
  if maximizingPlayer
      v := -∞
      for each child of node
          v := max(v, alphabeta(child, depth - 1, α, β, FALSE))
          α := max(α, v)
          if β ≤ α
              break ( β cut-off )
      return v
  else
      v := ∞
      for each child of node
          v := min(v, alphabeta(child, depth - 1, α, β, TRUE))
          β := min(β, v)
          if β ≤ α
              break ( α cut-off )
      return v

SAT

Propos­itional SAT: Graph coloring

At lest 1 of K per i
(Ci,1 ∨ Ci,2 ∨ ... ∨ Ci,k)
O(n) clauses
1 ≥ color per i
∀ k≠k' (¬Ci,k ∨ ¬Ci,k')
O(n^2)
If node i and j share an edge
assign different colors
∀ x∈k, (¬Ci,x ∨ ¬Cj, x)
 

Comments

No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.

          Related Cheat Sheets

          Regular Expressions Cheat Sheet
          PHP Cheat Sheet
          Python Cheat Sheet