Ch3 (informed search)

Question 1

What is Informed Search?

Answer 1

The AI knows some info about the goal state (may not be the exact info) but will be estimated.

Question 2

What are the informed search algorithms?

Answer 2

1-Herustic
2-Greedy search
3-A* search

Question 3

Can the informed search algorithms be applied on graph?

Answer 3

yes, they are graph algorithms and also on search trees

Question 4

What is a Search Problem in AI?

Answer 4

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

Question 5

What is a Search Tree?

Answer 5

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.

Question 6

What does a Search Algorithm do? (informed or uninformed)

Answer 6

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.

Question 7

What is the Fringe in a search algorithm?

Answer 7

The fringe is the set of unexplored nodes

Question 8

Talk about the pseudocode for the tree search algorithm

Answer 8

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

Question 9

What is another name for the uniformed search algorithms?

Answer 9

the one queue, because the fringe can be represented as a queue in all of them (by using apriority queue)

Question 10

What is the main difference between search algorithms?

Answer 10

All search algorithms are the same except for their fringe strategies, which determine how nodes are expanded.

Question 11

What is a fringe in search algorithms?

Answer 11

A fringe is a priority queue—a collection of nodes where each node has an assigned priority

Question 12

How do DFS (Depth-First Search) and BFS (Breadth-First Search) optimize their fringes?

Answer 12

Instead of using an actual priority queue, DFS uses a stack, and BFS uses a queue, avoiding the
𝑂(log𝑛) overhead of a priority queue

Question 13

Can you implement a general search algorithm for different fringe strategies?

Answer 13

You can code one implementation that takes a variable queuing object, allowing flexibility between DFS, BFS, and other strategies

Question 14

What is a heuristic in search algorithms?

Answer 14

A heuristic is a function that estimates how close a state is to the goal in a search problem. (informed search algorithm)

Question 15

What is the purpose of a heuristic function?

Answer 15

A heuristic function helps guide the search algorithm by providing an estimate of the cost to reach the goal, making searches more efficient.

Question 16

How are heuristics designed?

Answer 16

Heuristics are problem-specific, designed for particular search problem (every problem can have it’s own heuristics function)

Question 17

What are some common heuristics used in pathfinding?

Answer 17

1-Manhattan Distance
2-Euclidean Distance

Question 18

What is Manhattan Distance?

Answer 18

The sum of the absolute differences between the x and y coordinates of two points.

Question 19

What is Euclidean Distance?

Answer 19

The straight-line distance between two points

Question 20

What is the output of the heuristic function when you are at the goal state?

Answer 20

will always give 0

Question 21

Can you have multiple heuristics for the same problem?

Answer 21

Yes

Question 22

Is greedy search dependent on the heuristic function?

Answer 22

Yes, the better the heuristic function the better your greedy search will be.

Question 23

what is the input and out put of the heuristic function?

Answer 23

input: state
output: estimated cost (not backwards cost) it is the cost from that state

Question 24

What is Greedy Search?

Answer 24

Greedy Search is a search algorithm that expands the node that appears closest to the goal based on a heuristic function.

Question 25

How does Greedy Search choose which node to expand?

Answer 25

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.

Question 26

What is the data structure used in Greedy search?

Answer 26

priority queue, where the node that gets expanded is the node with the least estimated cost

Question 27

What could go wrong in the Greedy search?

Answer 27

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

Question 28

Is greedy always optimal?

Answer 28

no, because it only takes the heuristic value in consideration without the actual cost(best first) , it can be optimal in simple enviornments

Question 29

What is the main strategy behind Greedy Search?

Answer 29

Greedy Search expands the node that appears closest to the goal, using a heuristic function that estimates the distance to the goal.

Question 30

What happens in the worst-case scenario of Greedy Search?

Answer 30

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.

Question 31

Give an example of a bad heuristic funtion

Answer 31

when solving a pathing problems, setting number of people living in a city as the cost.

Question 32

What is a common case with Greedy

Answer 32

Best-First Search

Question 33

What is a common issue with Greedy Best-First Search?

Answer 33

It may lead directly to the wrong goal, because it only considers immediate proximity and ignores the actual cost of the path.

Question 34

Does informed search never do exploring?

Answer 34

No but it does less than the uninformed, and the exploring will be to the states that are closer to the goal

Question 35

Since greedy search have a common case (Best-First) and it may lead to the wrong state, what is a solution for that?

Answer 35

Take the actual cost in consideration along side the estimate from the heuristic function. By A*search

Question 36

A*search

Answer 36

takes backwards cost (actual cost) and the heuristic cost (estimated cost ) and adds them, so it combines UFC with greedy.

Question 37

How is the UCS and Greedy represented in A* search?

Answer 37

Greedy by h(state) UCS g(state) f(state)=h(state)+g(state)

Question 38

What data structure does A* search use?

Answer 38

priority queue, it expands out the node with the least f(state)=h(state)+g(state)

Question 39

Should you ever stop when you enqueue a goal state?

Answer 39

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*)

Question 40

Is A* optimal?

Answer 40

when heuristics are admissible, yes optimal

Question 41

What does it mean when saying that heuristics are admissible

Answer 41

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

Question 42

What is an inadmissible heuristic

Answer 42

An inadmissible heuristic may overestimate the cost to the goal, leading to suboptimal solutions by trapping good plans

Question 43

what is another name for admissible and inadmissible

Answer 43

1-admissible is optimistic 2-inadmissible is pessimistic

Question 44

What is the best practice in A* search?

Answer 44

coming up with an admissible heuristic , meaning it is less than and as close as it can to the actual cost