Topic 2.

Problem-Solving and Search Algorithms

2.1 AI AGENT

Direct Al maps mean functionality. Whenever these agents fail to work in an area where the
mapping condition is too large and not easily facilitated by the agent, the specified problem is solved
and sent to a troubleshooting domain that eliminates the main problem stored in small storage
space and solves one by one. The final combined action will be the desired results.

Based on the problem base and their functional background, the different types of problem solvers
are defined and applied at the atomic level outside of the internal state characterized by a problem-
solving algorithm. The problem solver acts precisely by explaining several problems and solutions.
Therefore, we can say that problem solving is part of artificial intelligence that includes many
techniques such as a tree, B-tree, and heuristic algorithms to solve the problem. We can also say
that the problem-solving agent is the result-driven agent who always focuses on meeting the
objectives.

Steps to problem-solving in Al

The problem of Al is directly associated with the nature of humans and their activities. So we need a
number of finite steps to solve a problem that does easy human works. These are the following steps
which require to solve a problem:

Goal Formulation: This one is the first and simple step in problem-solving. It organizes finite steps to
formulate a target/goals which require some action to achieve the goal. Today the formulation of
the goal is based on Al agents.

Problem formulation: It is one of the core steps of problem-solving, which decides what action
should be taken to achieve the formulated goal. In Al, this core part is dependent upon the software
agent, which consists of the following components to formulate the associated problem.

Components to formulate the associated problem

Initial State: This state requires an initial state for the problem, which starts the Al agent towards a
specified goal. In this state, new methods also initialize problem domain solving by a specific class.

Action: This stage of problem formulation works with function with a specific class taken from the
initial state and all possible actions done in this stage.

Transition: This stage of problem formulation integrates the actual action done by the previous
action stage and collects the final stage to forward it to the next stage.

Goal test: This stage determines that the specified goal is achieved by the integrated transition
model or not; whenever the goal is achieved, stop the action and forward into the next stage to
determine the cost to achieve the goal.

Path costing: This component of problem-solving numerical assigned what will be the cost to
achieve the goal. It requires all hardware software and human working cost

2.2 SEARCH STRATEGIES

Search algorithms are one of the most important areas of Artificial Intelligence. This section will
explain all about the search algorithms in Al.

2.2.1 PROBLEM-SOLVING AGENTS

In artificial intelligence, search strategies for solutions to global problems. In Al, rational agents or
problem-solving agents have used extensive techniques or algorithms to solve a specific problem
and give excellent results. Troubleshooting agents are not agents who are based on principles and
use atomic representation. In this section, we will learn about various problem-solving search
algorithms.

2.2.2 SEARCH ALGORITHM TERMINOLOGIES

Search: Searching is a step-by-step procedure to solve a search problem in a given search space. A
search problem can have three main factors:

Search Space: Search space represents a set of possible solutions, which a system may have.

Start State: It is a state from where the agent begins the search.

Goal test: It is a function that observes the current state and returns whether the goal state is
achieved or not.

Problem Instance: It is start state + Goal state.

Search tree: A tree representation of a search problem is called a Search tree. The root of the search
tree is the root node which corresponds to the initial state. Actions: It describes all the available
actions to the agent.

Transition model: A description of what each action does can be represented as a transition model.

Path Cost: It is a function that assigns a numeric cost to each path.

Solution: It is an action sequence that leads from the start node to the goal node.

Optimal Solution: If a solution has the lowest cost among all solutions.

Space Complexity: The maximum number of nodes that are stored in memory.

Time Complexity: The maximum number of nodes that are created.

Problem Space Graph: It represents the problem state. States are shown by nodes, and operators
are shown by edges.

Depth of a problem: Length of the shortest path or shortest sequence of operators from Initial State
to a goal state.

Admissibility: A property of an algorithm to always find an optimal solution.

Branching Factor: The average number of child nodes in the problem space graph.

2.2.3 PROPERTIES OF SEARCH ALGORITHM

Properties of Search Algorithms:

Following are the four essential properties of search algorithms of compare the efficiency of these
algorithms:

Completeness: A search algorithm is said to be complete if it gurantees to return a solution if at least

any solution exits for any random input.

Optimality: If a solution found for an algorithm is guaranteed to be the best solution (lowest path
cost) among all other solutions, then such a solution for is said to be an optimal solution.
Time Complexity: Time complexity is a measure of time for an algorithm to complete its task.

Space Complexity: It is the maximum storage space required at any point during the search, as the
complexity of the problem.

2.2.4 TYPES OF SEARCH ALGORITHMS

Based on the search problems, we can classify the search algorithms into

 Uninformed (Blind search) search

 Informed search (Heuristic search) algorithms.

2.3 UNINFORMED SEARCH STRATEGIES

2.3.1 BREADTH-FIRST SEARCH

Breadth-first search is the most common search strategy for traversing a tree or graph. This
algorithm searches breadthwise in a tree or graph, so it is called breadth-first search. BFS algorithm
starts searching from the root node of the tree and expands all successor node at the current level
before moving to nodes of next level. The breadth-first search algorithm is an example of a general-
graph search algorithm. The search is implemented using FIFO queue data structure.

Advantages:

 BFS will provide a solution if any solution exists.

  If there are more than one solution for a given problem, then BFS will provide the minimal
solution which requires the least number of steps.

Disadvantages:

 It requires lots of memory since each level of the tree must be saved into memory to expand
the next level.
 BFS needs lots of time if the solution is far away from the root node.

Example:

Output: A-B-C-D-E-F-G-H-I-J-K

Time Complexity: Time Complexity of BFS algorithm can be obtained by the number of
nodes traversed in BFS until the shallowest Node. Where the d is the depth of shallowest solution
and b is a node at every state.

T (b) = 1 + b2 + b3 + ..... bd = O(bd)

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

Completeness: BFS is complete, which means if the shallowest goal node is at some finite
depth, then BFS will find a solution. Optimality: BFS is optimal if path cost is a non-decreasing
function of the depth of the node.

2.3.2 DEPTH FIRST SEARCH

The DFS algorithm is a recursive algorithm that uses the idea of backtracking. It involves
exhaustive searches of all the nodes by going ahead, if possible, else by backtracking. Here, the word
backtrack means that when you are moving forward, and there are no more nodes along the current
path, you move backward on the same path to find nodes to traverse. All the nodes will be visited on
the current path till all the unvisited nodes have been traversed, after which the next path will be
selected.
Advantage:

 DFS requires very less memory as it only needs to store a stack of the nodes on the path from
root node to the current node.
 It takes less time to reach to the goal node than BFS node than BFS algorithm (if it traverses in
the right path).

Disadvantage:

 There is the possibility that many states keep re-occurring, and there is no guarantee of finding
the solution.
 DFS algorithm goes for deep down searching and sometime it may go to the infinite loop.

Output: H-D-I-B-E-J-A-F-K-C-G

Completeness: DFS search algorithm is complete within finite state space as it will expand every
note within a limited search tree.

Time Complexity: Time complexity of DFS will be equivalent to the node traversed by the algorithm.
It is given by:

T (n) = 1 + n2 + n3 + ..... + nM = O (bM)

Space Complexity: DFS algorithm needs to store only single path from the root node, hence space
complexity of DFS is equivalent to the size of the fringe set, which is O(bm).

Optimal: DFS search algorithm is non-optimal, as it may generate a large number of steps or high
cost to reach to the goal node.

2.3.3 UNIFORM-COST SEARCH ALGORITHM

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. The primary goal of the
uniform-cost search expands nodes which has the lowest cumulative cost. Uniform-cost search
expands nodes according to their path costs form the root node. It can be used to solve any
graph/tree where the optimal cost is in demand. A uniform-cost search algorithm is implemented by
the priority queue. It gives maximum priority to the lowest cumulative cost. Uniform cost search is
equivalent to BFS algorithm if the path cost of all edges is same.
Advantages:

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

Disadvantages:

 It does not care about the number of steps involve is searching and only concerned about
path cost. Due to which this algorithm may be stuck in an infinite loop.

Completeness:

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

Time Complexity:

Let C' is Cost of optimal solution, and is each step to get closer to the goal node. Then the number
of steps is = C/ε + 1. Here we have taken +1, as we start from state 0 and end to C/ ε. Hence, the
worst-case time complexity of Uniform-cost search is O(b1+[C])/

Space Complexity:

The same logic is for space complexity so, the worst-case space comlexity of Uniform-cost search is
O(b1+[c13)/.

2.3.4 DEPTH LIMIT SEARCH

The algorithm is a sub-case of the basic dfs algorithm. It is called a limited search since the algorithm
has a predetermined depth limit. The algorithm is just a solution to the infinite problem of the dfs
algorithm. The Algorithm, being a child of the basic dfs, inherits the space efficiency. Therefore, it is
not advisable to use this algorithm for more than one solution to a problem.

Example:

OUTPUT: D-B-E-A-F-K-C-G

Advantages:

 Depth-limited search is Memory efficient.

Disadvantages:

 Depth-limited search also has a disadvantage of incompleteness.

 It may not be optimal if the problem has more than one solution.

Completeness: DLS search algorithm is complete if the solution is above the depth limit.
Time Complexity: The time complexity of the DLS algorithm is O(b).

Space Complexity: The space complexity of the DLS algorithm is O(bxe).

Optimal: Depth-limited search can be viewed as a special case of DFS, and it is also not optimal even
if {>d.

2.3.5 ITERATIVE DEEPENING DFS

The algorithm can be said as the combo of the dfs and bfs algorithm. The algorithm finds the best
depth limit and does it and increases until the goal is found. Advantages:

It combines the benefits of BFS and DFS search algorithms in terms of fast search and memory
efficiency.

Disadvantages:

 The main drawback is that it repeats all the work of the previous phase.

first iteration--> A

second iteration --> A-B-C

There is no need for further iteration since we find the Goal node in the second iteration itself.

Completeness:

This algorithm is complete if the branching factor is finite.

Time Complexity:

Let's suppose b is the branching factor and depth is d, then the worst-case time complexity is
O(b").

Space Complexity:

The space complexity of IDDFS will be O(bd).

Optimal:

The algorithm is optimal if path cost is a non- decreasing function of the depth of the node.

2.3.6 BIDIRECTIONAL SEARCH

 Searching a graph is quite famous problem and has a lot of practical use. In normal graph search
using BFS/DFS we begin our search in one direction usually from source vertex toward the goal
vertex, but what if we start search form both direction simultaneously.

Bidirectional search is a graph search algorithm which find smallest path from source to goal
vertex. It runs two simultaneous search

1. Forward search form source/initial vertex toward goal vertex

2. Backward search from goal/target vertex toward source vertex

Bidirectional search replaces single search graph (which is likely to grow exponentially) with two
smaller sub graphs - one starting from initial vertex and other starting from goal vertex. The search
terminates when two graphs intersect.

Suppose we want to find if there exits a path from vertex A to vertex O. Here we can execute two
searches, one from vertex A and other from vertex O. When both forward and backward search
meet at vertex H, we know that we have found a path from node A to H and search can be
terminated now. We can clearly see that we have successfully avoided unnecessary exploration.

Completeness: Bidirectional Search is complete if we use BFS in both searches.

Time Complexity: Time complexity of bidirectional search using BFS is O(bd).

Space Complexity: Space complexity of bidirectional search is O(bd).

Optimal: Bidirectional search is Optimal.