Week 2

Question 1

Generate and Test Search Algorithm?

Answer 1

a very simple algorithm that guarantees to find a solution if done systematically and there exists a solution

Question 2

Informed Search methods?

Informed Search methods may have access to a heuristic function h(n) that estimates the cost of a solution from n

Answer 2

1. Best-first search algorithm
   the generic best-first search algorithm selects a node for expansion according to an evaluation function.
2. Greedy best-first search
   expands nodes with minimal h(n). It is not optimal but is often efficient
3. A* Search
   expands nodes with minimal f(n) = g(n) + h(n). A* is complete and optimal.
4. RBFS (recursive best-first search) and SMA* (simplified memory-bounded A*)

Question 3

Search algorithms are judges on the basis of?

Answer 3

completeness, optimality, time complexity, and space complexity. complexity depends on b, the branching factor in the state space, and d, the depth of the shallowest solution.

Question 4

Iterative deepening search only uses?

Answer 4

linear space and not much more time than other uninformed search strategies.

Question 5

Jenis-jenis Uninformed search strategy?

Answer 5

1. Breadth-First Search
2. Uniform-Cost Search
3. Depth-First Search
4. Depth-Limited Search
5. Iterative Deepening Search

Question 6

Time complexity of Breadth-First Search?

Answer 6

O(b^d)

Question 7

Why Iterative Deepening Search may seem wasteful?

Answer 7

because so many states are expanded multiple times

Question 8

Best first search (greedy) complexity?

Answer 8

Complete? NO, can get stuck in loops
Time? O(b^m)
Space? O(b^m)
Optimal? NO

Question 9

admissible heuristic used in?

Answer 9

A* search

Question 10

is A* search is optimal?

Answer 10

YES

Question 11

search algorithm that combines advantages of uniform-cost and greedy searches?

Answer 11

A* Search

Question 12

A* characteristics?

Answer 12

Complete, optimal, and optimally efficient. But space complexity still exponential.

Question 13

Greedy search?

Answer 13

best-first search with the estimated cost to reach the goal as a heuristic measure. not optimal and not complete but generally faster than uninformed search.

Question 14

What is hill climbing?

Answer 14

hill-climbing is a mathematical optimization technique for local search. can be used to solve problems that have many solutions. It starts with a random solution, and iteratively makes small changes and keep improving to find the solution.