Day 6

Question 1

Problem formulation is the process of deciding what actions and states to consider, given a goal.

Question 2

Goal formulation based on the current situation and the performance measure, is the first step in problem solving.

Question 3

• We assume that the environment is observable , so the agent always knows the current state.
• We also assume the environment is discrete, so at any given state there are only finitely many actions to choose from.
• We will assume the environment is known, so the agent knows which states are reached by each action.
• Finally, we assume that the environment is deterministic, so each action has exactly one outcome.

Question 4

Space complexity of BFS algorithm is given by the Memory size of frontier which is O(bd).

Question 5

Completeness: BFS is complete, which means if the shallowest goal node is at some finite depth, then BFS will find a solution.

Answer 5

Completeness: BFS is complete, which means if the shallowest goal node is at some finite depth, then BFS will find a solution.

Question 6

BFS is optimal if path cost is 1 per step.

Question 7

Uniform-cost search is a searching algorithm used for traversing a weighted tree or graph. This algorithm comes into play when a different cost is available for each edge

Question 8

The primary goal of the uniform-cost search is to find a path to the goal node which has the lowest cumulative cost. It can be used to solve any graph/tree where the optimal cost is in demand.

Question 9

Uniform-cost search expands nodes according to their path costs form the root node

Question 10

Uniform-cost search does not care about the number of steps a path has, but only about their total cost.

Question 11

Uniform cost search is optimal because at every state the path with the least cost is chosen

Question 12

It does not care about the number of steps involve in searching and only concerned about path cost.

Question 13

A uniform-cost search algorithm is implemented by the priority queue

Question 14

Uniform cost search is equivalent to BFS algorithm if the path cost of all edges is the same.

Question 15

Completeness: Uniform-cost search is complete, such as if there is a solution, UCS will find it.

Answer 15

Completeness: Uniform-cost search is complete, such as if there is a solution, UCS will find it.

Question 16

Optimality: Uniform-cost search is always optimal as it only selects a path with the lowest path cost.