Search 2

14 flashcards · Computer Science · by J M COOPER

1. How is the Eights puzzle different to (eg) SAT?

   • can have infinitely long branches if we don’t check for loops • Usually no need to choose variable (e.g. letter in SAT) • there is only one piece to move (the blank) and we have a choice of places to move it to • we might want to minimise length of path • in SAT just want satisfying assignment

2. Describe best first + manhattan distance heuristic as applied to the Eights puzzle

   Best First Use two heuristics to choose next node: number of misplaced tiles (max 8, min 0) sum of distances of tiles from goal (manhattan distance) • Can use it as heuristic for estimate of distance to solution • makes sense to explore apparently nearest first

3. Calculate the manhattan distance heuristic for the current state. Comment on its accurracy.

   Optimal solution is actually 18 (we just know this, stated without proof) so manhattan distance underestimates.

4. Why is Best First + Manhattan distance NOT a good heuristic in 8s puzzle?

   • It can be misled • Suppose we have a small Manhattan distance for move X • but any solution for move X must reverse move X eventually (e.g. to allow a vital move Y) • We have in reality made the solution 2 moves longer • Heuristic thinks we are closer to a solution • Infinite loops can occur in Best First + Manhattan

5. What is a good heuristic to use in 8s puzzle?

   Best first + total distance heuristic = A* Total distance counts moves so far + manhattan distance to goal state This must be a lower bound on #moves from start state to goal state via the current state • Because moves so far is exact • Manhattan is lower bound on distance to go

6. What does the total distance heuristic guarantee?

   Total distance is an estimate of how long it takes to get from the start state to the goal state VIA the current node. heuristic score is guaranteed lower bound on true path cost via the current state heuristic score of solution is the true cost of solution

7. What does A* guarantee?

   • A* guarantees that first solution found is optimal • So we can stop searching immediately

8. Prove that A* guarantees to find the optimal solution.

   • Proof: • write A* heuristic as f(n) = g(n) + h(n) • g(n) = cost to node n • h(n) = est. cost of cheapest path to goal • f(n) = est. cost of cheapest path via n //estimated path cost f(n) from start to goal via any given node is always <= actual cost • guarantee 1: truecost(n) >= f(n) //h(n) never overestimates cost at goal (because we always know g(n) with accuracy and at goal h(n) = 0) • guarantee 2: truecost(goal) = f(goal) //todo

9. Use A* Search to get from the start state to the goal state:

   and so on until.........

10. What is the difference between A* and Best First?

    A* is just a version of Best First • In fact it is Best First • Plus the A* guarantee

11. What is Euclidean distance?

    the distance between two points dist((x, y), (a, b)) = √(x - a)² + (y - b)²

12. Perform A* search with Euclidean distance Start node is S, goal node is G

13. Why use A* search?

    • Why use A*? • You really need to be sure you have the optimum • You have a lower bound estimate (required) • You have a good lower bound (desirable) • Experience suggests lists don’t get too long

14. Why not use A* search?

    • You might not really need the optimum • Your lower bound is not very good • You find that search lists grow exponentially • Exponential space is usually worse than exp. time