2- Solving problems by searching Flashcards
1.what’s the problem formulation of search problem?
- Initial state of agent
- Actions available to the agent
- Transition model :description of each action does
- Goal test : check if a certain state is a goal
- Path cost : numeric value to measure
2.describe uninformed search algorithms
It can be considered as a tree made up all the possible sequenced of actions from initial state.
In the tree the root is initial state, nodes are states, branches are actions.
3.Tree search algorithm
Function TREE-SEARCH returns either a solution or a failure.
frontier: the set of all leaf nodes available for expansion at any given point.
leaf node: a node with no kid in the tree
Process:
1. Initialize the frontier using the initial state of problem
2. loop do
if the frontier is empty , return failure
choose a leaf node and remove it from the frontier.
if the node contains a goal state then return ther solution. expand the chosen node, adding the resulting nodes to the frontier.
4, how to improve tree search algorithm in order to avoid reduant paths?
Using explored set that remembers every expanded node.
- Graph search algorithm(improved tree-search)
1,Initialize the frontier using initial state
2, loop do
if the frontier is empty –> return failure
choose a leaf node and remove it from the
frontier
if the node contails a goal state then return the corresponding solution
add the node to explored set.
expand the chosen node, adding the resulting node to the frontier. (only not in frontier or explored set)
- Breadth-first search algorithm
b: branching factor of the search tree
d: depth of least-cost solution
m: maximum depth of the state space
frontier as FIFO: the successor will go at end
time: O(b^d)
space: o(b^d)
- Depth-first search
Explore the deepest unexpanded node.
LIFO: new successor at first
Time : O(b^m) terrible if 𝑚 is much larger than 𝑑
Space:O(b*m)
8.Depth-limited search
To avoid problems of the limitless trees, we use depth-first search with a depth limit L.
- Iterative deepening search
It repeatedly applies depth-limited search with increasing limits
- In what way makkes iterative deepening search better than others?
1, if b iif finite, will be complete
- Optimal cost for unit step cost
- time complexity comparable to breadth-first search
- linear sapce complexity
- def of Heuristic function?
Heuristic function = estimate of cost of the cheapest path from the state of the node N to the goal state.
- Greedy best first search and A* search?
Greedy best-first search : expands the node that appears to be the closest to goal. f(n) = h(n)
A* search : avoid expanding paths that are already expensive
fn = gn + hn
gn: path cost from the start node to node n
hn: estimated cost of the cheapest path from n to goal
fn: estimated cost of the cheapest solution through n
13.admissible heuristics and consistent heuristics
14.stable marriage definition
In a marriage that no pair (man, woman) that not married to each other that would prefer to be together. Or marriage with no blocking pairs.
Blocking pair: in a pair where this wife prefers that marriage’s husband. And this husband prefers that marriage’s wife.
14.stable marriage definition
In a marriage that no pair (man, woman) that not married to each other that would prefer to be together. Or marriage with no blocking pairs.
Blocking pair: in a pair where this wife prefers that marriage’s husband. And this husband prefers that marriage’s wife.
