Uninformed + Informed Searches

basic algorithms:

“Blind”, don’t have Problem or domain-specific knowledge

Has further information about solution costs (heuristics)

-> problem/ domain-specific knowledge

“historyless,” one-step change

does it always find a solution if one exists?

number of nodes generated/expanded

maximum number of nodes in memory

does it always find a least-cost solution?

Expand shallowest unexpanded node (goal test at generation time)

Expand least-cost unexpanded node (goal test at expansion)

Expand deepest unexpanded node (goal test at ?)

Bound search with depth limit l and increase limit systematically (to gain completeness)

Uses heuristic function for desirability of possible solution

Uses evaluation function f(n) = h (n) (e.g. distance from n to goal)

Use evaluation function f (n) = g(n) + h(n)

(and avoid expanding paths that are already expensive)

• g(n): path costs from start to n

• h(n): estimated cost to goal from n

• f(n): estimated total cost of path through n to goal

!! h(n) has to be admissible !!

Just like climbing a hill, if the neighboring solution is better, then it is chosen over the current one

In order to escape local maxima some “bad” moves are allowed with a gradually descreasing size and frequency

(corresponds to “cooling off” process of materials)

Problem: might leave an optimal solutions favor of a bad neighboring solution