4285579
Description
Flashcards by Wojciech Gryncze, updated more than 1 year ago
|
Created by Wojciech Gryncze
over 8 years ago
|
|
| Question | Answer |
| Uniformed search | Blind search - number of steep and path cost unknown - agent only know when it reach a goal |
| Informed search | Agent has background information about the problem (map, cost of actions, approximation of solutions, etc) |
| Formulating problems | A problem consists of five parts: the initial state, a set of actions, a transition model describing the results of those actions, a goal test function, and a path cost function. The environment of the problem is represented by a state spac |
| Objective of the search (The result is known) | Find sequence of the actions to achieve the goal |
| How is graph search different from tree search? | Graph search maintains in addition to its fringe (or open list) also a closed list that contains all nodes that have been expanded in the past. Every time, we expand a node and put its successors into the fringe we first check whether the s |
| State vs. Node | |
| What is an optimal solution? | Ab optimal solution has the lowest path cost among all solutions. |
| What is the searching? | Searching for solution is a traversal of some search space from the initial state to the goal state using a legal sequence of actions. |
| TREE-SEARCH Algo? | |
| GRAPH-SEARCH Algo? | |
| Completeness | It find a solution if one exists |
| Optimality | It finds a least cost solution |
| On what criteria the Search algorithms are judged ? | Search algorithms are judged on the basis of completeness, optimality, time complexity, and space complexity. Complexity depends on b, the branching factor in the state space, and d, the depth of the shallowest solution. |
| Breadth-first search | Breadth-first search expands the shallowest nodes first; it is complete, optimal for unit step costs, but has exponential space and time complexity. (Frontier is a FIFO queue) |
| Uniform-cost search | Uniform-cost search expands the node with lowest path cost, g(n), and is optimal for general step costs (Frontier is a queue ordered by path cost) |
| Depth-first search | Depth-first search expands the deepest unexpanded node first. It is neither complete nor optimal, but has linear space complexity. Depth-limited search adds a depth bound. (Frontier is a LIFO queue) (If the tree is infinite we lose the comp |
| Iterative deepening search | Iterative deepening search calls depth-first search with increasing depth limits until a goal is found. It is complete, optimal for unit step costs, has time complexity comparable to breadth-first search, and has linear space complexity. (B |
| Bidirectional search | Bidirectional search can enormously reduce time complexity, but it is not always applicable and may require too much space. |
| Uniformed search comparaison |
Want to create your own Flashcards for free with GoConqr? Learn more.