Search

Question 1

Finding Optimal Solutions to Rubik’s Cube?

Answer 1

The algorithm
used is iterative-deepening-A* (IDA*), with a lower- bound heuristic function based on large memory-based
lookup tables, or \pattern databases”

Question 2

Definition of a problem

Answer 2

• Initial State
• Actions(s): Possible actions from s to change state
• Result(s,a): The next state from performing action a on state s
• GoalTest(s): Returns true if reach goal state
• Path Cost

Question 3

Which search methods are complete and optimal

Answer 3

• Breath First Search and Cheapest cost

- Depth first is not

Question 4

What knowledge is most useful in search?

Answer 4

• Estimate from the start state to the goal. A good aprox is the linear distance between them
• Greedy best-first search: expands the path that its estimate is closest.
• The best algorithm is a combination of greedy and uniform cost

Question 5

A* Search

Answer 5

• Minimum value of f = g + h
• g(path) = path cost
• h(path) = h(s) = estimated distance to goal
• Finds the shortest length path while expanding minimum number of paths possible.
• g keeps path short
• h keeps us focused on the goal

Question 6

When A* finds the lowest cost path?

Answer 6

• h(s) < true cost

Question 7

What is an admissible heuristic?

Answer 7

• heuristic function is said to be admissible if it never overestimates the cost of reaching the goal

Question 8

How to develop automatically a good heuristic?

Answer 8

• Relaxing the problem by eliminating one of the constraints

Question 9

When does problem solving works?

Answer 9

• Fully observable: must see the initial state
• Known: must know the set of available actions
• Discrete: Must be a finite number of actions to choose
• Deterministic: Must know the result of an action
• Static: only our actions can change the world

Question 10

How to implements path in a computer?

Answer 10

• nodes: state end of path, action to get there, total cost, parent node

Question 11

How to implement the frontier?

Answer 11

Operations:
- Remove best item
- Add new
- Membership test
Implementation:
- Priority queue
Representation:
- Set
Build:
- Hash table
- tree

Question 12

How to implement the explored list?

Answer 12

Operations:
- Add new
- Membership test
Representation:
- Single Set
Build:
- Hash table
- tree

Question 13

Uniform Cost Search

Answer 13

• It is cheapest first guaranties that it finds the least total cost