What is an uninformed search?

basic algorithms:

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

What is an informed search?

Has further information about solution costs (heuristics)

-> problem/ domain-specific knowledge

What is a local search?

“historyless,” one-step change

What does completeness mean?

does it always find a solution if one exists?

What is the time complexity?

number of nodes generated/expanded

What is the space complexity?

maximum number of nodes in memory

What is optimality?

does it always find a least-cost solution?

What is the BFS?

Complete = ?

Time = ?

Space = ?

Optimal = ?

Problems?

Expand shallowest unexpanded node (goal test at generation time)

What is the UCS?

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

What is the DFS?

Expand deepest unexpanded node (goal test at ?)

What is the IDS?

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

Overview of uninformed searches:

What is an heuristic search?

Uses heuristic function for desirability of possible solution

What is the Greedy-Search?

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

What is the A*-Search?

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 !!

Which three rules does an admissible heuristic fulfill?

When is an heuristic consistent?

What is Hill-Climbing? What problem does it have?

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

What is Simmulated Annealing?

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

Last changed2 years ago