Key definitions:

1. In order for the search algorithm to work, we have provide it with a Heuristic function

2. Problem-solving technology woks when the following set of conditions is true:

1. Fully observable: must be able to see what initial state we start out with

2. Known: must know the set of available actions to us

3. Discrete: Must be a finite number of actions to choose from

4. Deterministic: Must know the result of taking an action

5. Static: Must be nothing else that can change the world other than our own action

1) Breadth first search

Points on a map routine search:

1. Frontier

2. Unexplored

3. Explored

Steps:

1. Initiate a root point as a frontier

2. Remove a frontier A, add it into explored

3. Find and mark frontiers from this removed frontier A

4. Iterate with breadth-first-search

2) Uniform cost search

1. Cheapest-first-search

2. Should clear app frontiers before terminate the process!

3) A* Search

Basic definitions:

1. Minimum value:

1. f = g + h

2. g(path) = path cost

3. h(path) = h(s) = estimated distance to goal = heuristic function

2. Minimizing g => keeps the path short

3. Minimizing h => keeps us focused on the goal

4. Result:

1. Search strategy that is the best possible.

2. Finds the shortest length path while expanding minimum number of paths possible.

5. A* finds the lowest cost path if:

1. It depends on the h function

2. h(s) to get to the right position

The data structure of Node:

1. State S

2. Parent Node pointer

Frontier:

1. Operations:

1. Remove best item

2. Add in new ones

3. Membership test

2. Implementation

1. Priority Queue

3. Representation

1. Set

4. Build

1. Hash Table

2. Tree

Explored:

1. Operations:

1. Add in new ones

2. Membership test

2. Representation

1. Set

3. Build

1. Hash Table

2. Tree