Please enable JavaScript.
Coggle requires JavaScript to display documents.
AI (CSP, Uninformed Search, Informed Search, Adversarial Search),…
AI
CSP
NodeConsistency
ArcConsistency
#
Xi, Xj
Di
change add all (Xk,Xi) to frontier
AC3 algorithm
Backtracking
Heuristic
Values
LCV
choosing value that give ample options
Variable
MRV
variable left few values in domain
Degree
variable with highest degree
ForwardChecking
= DFS + variable ordering + Fail On violation
Constraints
unary
Binary
Uninformed Search
DFS
not optimal
memory efficient
stack
BFS
Space O(b^d), time O(b^d)
Uniform cost search
can end in loops
Informed Search
A* Search
G(n)+H(n)
optimal
GreedyBestFirstSearch
F(n)=H(n)
not optimal
Adversarial Search
Heuristic
#
Admissible
H(n) less or equal to actual cost
consistent
Everynode should be less or eq actual cost