Search 3

30 flashcards · Computer Science · by J M COOPER

1. What is A* Search?

   • A* is best first search with an “admissible” heuristic • A* guarantees to find optimal solution

2. What is an admissible heuristic?

   An admissible heuristic is heuristic f with 2 guarantees: truecost(n) >=f (n) guarantee 1 f will never overestimate the total pathcost to goal at any node truecost(goal) = f(goal) guarantee 2 at goal, the pathcost given by x will be equal to the actual pathcost

3. What do we need to get an admissible A* heuristic at any node?

   A* heuristic f(n) = g(n) + h(n) • g(n) = cost to node n from start • h(n) = estimated cost to from node n to goal so f(n) = estimated cost to from start to goal via node n

4. What is branch and bound search?

   As in A*: f(n) = g(n) + h(n) (cost to node n from start, plus estimated cost from node n to goal) looks for bound which is guaranteed to be lower than the true cost Add variable for best solution found so far: best = ∞ (because we don't know if any solution is possible yet) Search the branching tree any way you like (but usually DF) At any node n, if f(n) >= best, backtrack or don't expand node (we can't get a better solution than the one we already have so no point continuing) When any solutio…

5. When is branch and bound equivalent to A*?

   If the heuristic used is cost and bound and search used is best first, then branch and bound is just the same as A*

6. Write a BnB Depth First algorithm

   1. create a list P, best = ∞ 2. add the start node S, to P, so P = [S] 3. Until P is empty 1. extract the first state from P 2. If Goal-> set best = Cost(Goal) 3. Else ->s extend first state to all neighbours 4. reject all paths with loops or cost ≥ best 5. add remaining new states at start of list (because depth first) 4. If Goal found -> return best else -> fail.

7. What might the bound be when using BnB in a TSP problem?

   Bound might be cost of following minimum spanning tree (MST) of remaining nodes • MST: tree connected to all nodes of min cost among all such trees • all routes have to visit all remaining nodes • can’t possibly beat cost of MST (But bounds often much more sophisticated e.g. using mathematical programming optimisations)

8. Why use BnB instead of A*?

   • A* guarantees first solution found is optimal, so why not use it all the time? • BnB is usually based on Depth First Search • A* is based on Best First Search • So in A*, space required can be exponential • So A* can be infeasible in practice. • BnB can still exploit heuristics and bounds

9. How are best first, A* and Branch and Bound related?

   • Best first tries to explore most promising node first • Best First + Guarantees = A* • Branch and Bound also uses guaranteed bounds • Depth First + Guarantees = BnB

10. What is the problem with complete search methods?

    Because if there is a solution they are guaranteed to find it, they are exhaustive. if they say there is no solution, they must guarantee it so must do complete search in all parts of the search space EVEN IF the part of the search space they are in is very unlikely to yield a solution

11. What are incomplete search methods?

    Don't have to be exhaustive Can therefore move around the search space much more rapidly Risk missing solutions Use some form of hill climbing to move towards nearby solutions Need some means of making 'bad' moves to get to different parts of the search space

12. What is hill-climbing search?

    • aka greedy local search • Choose a start state, S • Identify the highest neighbour, T (random tie breaker) • Replace S with T • Continue until S is higher than its neighbours • Hope you’re at the summit of Everest

13. What is gradient-descent search?

    Exactly the same as hill climbing but going down instead of up

14. What is GSAT?

    A hill-climbing algorithm for the SAT problem.

15. What is the problem with hill-climbing and how can we combat it?

    Can get stuck at local maxima, so use local search good if we want a local max, but don't care if it is global. But can do variations on hill climbing to combat this: Allow n sideways moves (to get off a plateau without looping) Stochastic random neighbour (p varies with gradient) First choice (choose 1st higher of many neighbours) Random-restart (series of hill climbs, stop when a goal reached)

16. What is simulated annealing?

    • Stochastic hill-climbing with downward moves allowed • More early in the search, fewer later • Probability p of downward steps • Schedule maps # steps to p • If the schedule lowers p slowly enough, then a global optimum will be found…with probability 1…but don’t hold your breath

17. What is local beam search?

    • Start with k random states, Si i = 1:k • Find all the neighbours of each Si • If any is a goal, stop • Else select the best k, Ti • Replace Si with Ti and repeat • No requirement to take one neighbour for each Si • If the best neighbours are clustered around a few nodes, we concentrate search in those areas

18. What are genetic algorithms in search?

    Similar to local beam, but combines 2 parent nodes Nodes encoded as string has a fitness function which rates nodes P(node chosen) is proportional (∝) to that node's fitness (or possibly just drop all nodes below certain fitness) Select pair of nodes to combine according to P Choose random crossover point in node strings Mate by swapping sybols - one or two offspring Possibly introduce mutation Repeat until individual is fit enough or some bound on generations is reached Takes large steps early…

19. What does ∝ mean?

    Directly proportional to. Eg A ∝ B means A = kB for some constant k

20. What is random walk?

    Gives a way of making bad moves to avoid local maxima choose a start node s choose any neighbour t replace s with t and iterate Can be complete if run long enough, but v expensive

21. What are some variations on hill climbing?

    Allow n sideways moves (to get off plateau) Stochastic, pick random neighbour, P varies with gradient First choice -choose 1st higher of many neighbours Random restart - do series of climbs, stop when goal is reached

22. What must be considered in formulating a search approach?

    • Successful approaches are a black art • Formulation • Granularity • Convergence • Randomness and probabilities • Accepted solutions

23. Why can incomplete search not guarantee that there is no 16 clue valid sudoku?

    Even if you do 1000000 searches, the 1000001st could be the 16 clue. So cannot guarantee

24. How was the 16 clue sudoku proven impossible in so little CPU time?

    looked at reduced set of completed grids only Find unavoidable sets in completed grids - i.e. sets of clues that must appear in all valid puzzles for given grid size. Find fast ways to get sets of 16 clues, that hit all unavoidable sets And then check if the 16 clue set is valid using sudoku solver.

25. Why look at set of completed grids only?

    There are lots of different puzzles that correspond to the same grid. So we might be able to rule out all of those puzzles for a given completed grid - i.e. show that for this completed grid, there can be no 16 clue puzzles

26. How many completed grids are there and how could we reduce this number?

    >6.6 x 1021 Use symmetry - each completed grid is really the same as one where we rename digits 1-9 in any order, permute the bands or stacks, or transpose the whole grid This leaves only 5.5×109 completed grids to consider

27. What is GAP?

    GAP is a major piece of software for dealing with symmetries

28. What is an unavoidable set?

    A set of adjacent numbers, one of which MUST be included as a clue in any valid sudoku puzzle

29. What is a hitting set in the sudoku problem?

    When unavoidable sets have been identified, we then want to find all sets ('hitting sets') of size 16 that include at least one element from each unavoidable set. This is an NP complete problem but can be done in reasonable time.

30. Describe:

    You get a formula in conjunctive normal form Flip the literals of the clauses until you find a solution that satisfies the formula or until you reach the max_tries/max_flips limit and find no solution. The GSAT method starts with an arbitrary truth assignment. (pick random state) Then GSAT moves from one truth assignment to the next by flipping one of the propositions to achieve the greatest increase in the number of sentences satisfied. (move to highest neighbour) The search stops when it reac…