Search 1

18 flashcards · Computer Science · by J M COOPER

  1. What is a complete search algorithm?

    • guaranteed to find solution or prove there is none • though only if given enough time, so may timeout

  2. What is an incomplete search algorithm?

    • may not find a solution even when it exists • often more efficient (or there would be no point) • Though can still timeout even if it would have found a solution later

  3. What is depth first search?

    • explore all nodes in subtree of current node before any other nodes • pick leftmost and deepest element of frontier • treat list as a stack (LIFO) • new search states to explore added at front of list

  4. What is breadth first search?

    • explore all nodes at one height in tree before any other nodes • pick shallowest and leftmost element of frontier • treat list as a queue (FIFO) • new search states to explore added at end of list

  5. What is best first search?

    • pick whichever element of frontier seems most promising • Need heuristic score for each search state • MERGE: merge new states in sorted order of score

  6. What is depth-bounded depth first search?

    • like depth first but set limit on depth of search in tree • DFDB: always finds solution at depth <= L, while DF may find very deep solution before shallow ones • DFDB: never goes down infinite branch, relevant if search tree contains infinite branches e.g. Eights puzzle • How do we choose d? Sometimes you know (e.g. “mate in 3”)

  7. What is iterative deepening search?

    • use depth-bounded search but iteratively increase limit • d = 0 • Loop Until (solution found) • apply DFDB(d) • d := d + increment • Guarantees to find a solution if one exists (cf DFDB) • Finds shallow solutions first (cf DF) • Always has small frontier (cf Breadth First) • Surprising asymptotic guarantees

  8. What is a general search algorithm?

    1. Form a one element list with null state 2. Loop Until (list empty or we have a solution) Remove the first state X from the list Create a new state for each possible choice of decision MERGE the set of new states into the list (different algorithms will have different MERGE methods) 3. If (solution in list) succeed else list must be empty, so fail

  9. What is the downside of iterative deepening and why is it used anyway?

    • ID repeats work from depths 1 to d • But we only do b/(b-1) times as much work as we need to • Very often worth the overhead for the advantages

  10. What is NP-Complete?

    • we can recognise solutions in polynomial time • all other NP problems can be solved by translation to SAT

  11. Describe TSP

    Travelling Salesperson Problem instance is graph with cost for each edge solution is tour visiting all nodes and returning to base, meeting some cost limit - or maybe find minimum possible cost NP Complete many applications - route finder, circuit board drilling, warehouse

  12. Describe SAT. What is 3-SAT?

    “propositional SATisfiability” - very important Instances are propositional logic in clause form NP-Complete E.g. setting alphabetic typography example - instance of problem is a list of words eg ABC, ABc, AbC, Abc, aBC, abC, abc And solution is a choice of upper/lower case letter that satisfies all e.g. AbC is a unique solution 3-sat is if each word contains 3 letters

  13. Describe sorting

    common search problem we can do it efficiently so it isn't AI really (AI moves over time - define AI as Stuff that we don’t know how to do efficiently with computers yet) in NP

  14. What is a PSPACE problem?

    those which can be solved using a small amount of space

  15. What is a search state?

    • Search states summarise the state of search e.g. • In SAT a search state might be represented by aB • In TSP a search state might specify some of the order of visits • In Checkers a search state might be represented by the board position • Search in AI by structured exploration of search states

  16. What is a search space?

    Search space consists of: nodes (search states) links (legal connections between search states eg move left, go to A, etc)

  17. Draw a search tree for 3-SAT: ABC, ABc, AbC, Abc, aBC, abC, abc Assume the algorithm detects failure early

  18. Why are search trees abstract?

    Algorithms do not store whole search trees That would need exponential space we can discard explored nodes Store only frontier many algorithms understandable in terms of search trees