Ch3 (informed search) Flashcards
What is Informed Search?
The AI knows some info about the goal state (may not be the exact info) but will be estimated.
What are the informed search algorithms?
1-Herustic
2-Greedy search
3-A* search
Can the informed search algorithms be applied on graph?
yes, they are graph algorithms and also on search trees
What is a Search Problem in AI?
A search problem consists of:
1-States (configurations of the world)
2-A successor function (Actions and costs)(world dynamic)
3-Solution
4-A start state and a goal test
What is a Search Tree?
Is a representation of a graph has:
1-Nodes represent plans for reaching states.
2-Each plan has a cost, calculated as the sum of action costs.
What does a Search Algorithm do? (informed or uninformed)
1-Systematically builds a search tree by expanding nodes
2-Chooses an ordering of the fringe (unexplored nodes).
3-If optimal, finds the least-cost path to the goal.
What is the Fringe in a search algorithm?
The fringe is the set of unexplored nodes
Talk about the pseudocode for the tree search algorithm
1-If there are no candidates for that node (can’t be expanded out) return failure and look for another node depending on the strategy.
2-If we reached goal state then stop and return the solution.
3-else expand out
What is another name for the uniformed search algorithms?
the one queue, because the fringe can be represented as a queue in all of them (by using apriority queue)
What is the main difference between search algorithms?
All search algorithms are the same except for their fringe strategies, which determine how nodes are expanded.
What is a fringe in search algorithms?
A fringe is a priority queue—a collection of nodes where each node has an assigned priority
How do DFS (Depth-First Search) and BFS (Breadth-First Search) optimize their fringes?
Instead of using an actual priority queue, DFS uses a stack, and BFS uses a queue, avoiding the
𝑂(log𝑛) overhead of a priority queue
Can you implement a general search algorithm for different fringe strategies?
You can code one implementation that takes a variable queuing object, allowing flexibility between DFS, BFS, and other strategies
What is a heuristic in search algorithms?
A heuristic is a function that estimates how close a state is to the goal in a search problem. (informed search algorithm)
What is the purpose of a heuristic function?
A heuristic function helps guide the search algorithm by providing an estimate of the cost to reach the goal, making searches more efficient.
How are heuristics designed?
Heuristics are problem-specific, designed for particular search problem (every problem can have it’s own heuristics function)
What are some common heuristics used in pathfinding?
1-Manhattan Distance
2-Euclidean Distance
What is Manhattan Distance?
The sum of the absolute differences between the x and y coordinates of two points.
What is Euclidean Distance?
The straight-line distance between two points
What is the output of the heuristic function when you are at the goal state?
will always give 0
Can you have multiple heuristics for the same problem?
Yes
Is greedy search dependent on the heuristic function?
Yes, the better the heuristic function the better your greedy search will be.
what is the input and out put of the heuristic function?
input: state
output: estimated cost (not backwards cost) it is the cost from that state
What is Greedy Search?
Greedy Search is a search algorithm that expands the node that appears closest to the goal based on a heuristic function.
How does Greedy Search choose which node to expand?
It selects the node with the smallest heuristic value (h(n)), and expand out (remove from queue) meaning the one that seems closest to the goal.
What is the data structure used in Greedy search?
priority queue, where the node that gets expanded is the node with the least estimated cost
What could go wrong in the Greedy search?
the heuristic function is not doing good estimated meaning the greedy search will expand wrong nodes, which can lead to incomplete or in optimal solution
Is greedy always optimal?
no, because it only takes the heuristic value in consideration without the actual cost(best first) , it can be optimal in simple enviornments
What is the main strategy behind Greedy Search?
Greedy Search expands the node that appears closest to the goal, using a heuristic function that estimates the distance to the goal.
What happens in the worst-case scenario of Greedy Search?
1-It behaves like a poorly-guided Depth-First Search (DFS), getting stuck in deep paths that don’t lead to the optimal solution.
2-This happens when heuristic function is bad.
Give an example of a bad heuristic funtion
when solving a pathing problems, setting number of people living in a city as the cost.
What is a common case with Greedy
Best-First Search
What is a common issue with Greedy Best-First Search?
It may lead directly to the wrong goal, because it only considers immediate proximity and ignores the actual cost of the path.
Does informed search never do exploring?
No but it does less than the uninformed, and the exploring will be to the states that are closer to the goal
Since greedy search have a common case (Best-First) and it may lead to the wrong state, what is a solution for that?
Take the actual cost in consideration along side the estimate from the heuristic function. By A*search
A*search
takes backwards cost (actual cost) and the heuristic cost (estimated cost ) and adds them, so it combines UFC with greedy.
How is the UCS and Greedy represented in A* search?
Greedy by h(state)
UCS g(state)
f(state)=h(state)+g(state)
What data structure does A* search use?
priority queue, it expands out the node with the least f(state)=h(state)+g(state)
Should you ever stop when you enqueue a goal state?
No, you should check if it is next to be dequeued, and then stop working, because you may have a better solution, this is for all cases the use priority queue (so far UFC, Greedy ,A*)
Is A* optimal?
when heuristics are admissible, yes optimal
What does it mean when saying that heuristics are admissible
An admissible heuristic never overestimates the true cost to reach the goal, ensuring optimal solutions.(the heuristic estimate is less than the actual cost) and it is greater or equal to zero
What is an inadmissible heuristic
An inadmissible heuristic may overestimate the cost to the goal, leading to suboptimal solutions by trapping good plans
what is another name for admissible and inadmissible
1-admissible is optimistic
2-inadmissible is pessimistic
What is the best practice in A* search?
coming up with an admissible heuristic , meaning it is less than and as close as it can to the actual cost
