AI SEARCHING ALGORITHMS
What is a search algorithm?
Search algorithms are algorithms that help in solving search problems.
A search problem consists of a search space, start state, and goal state.
Search algorithms help the AI agents attain the goal state through the assessment of
scenarios and alternatives.
The algorithms provide search solutions through a sequence of actions that transform
the initial state to the goal state.
Without these algorithms, AI machines and applications cannot implement search
functions and find viable solutions.
Importance of search algorithms:
The following points explain how and why the search algorithms are important in artificial
intelligence:
1. Solving problems:
Search algorithms enhance the solving of problems in artificial intelligence through logical
search mechanisms such as problem definition, actions, and search space.
2. Search programming:
Many AI tasks can be programmed in terms of search, which enhances the formulation of the
solution to a given problem.
Arshiya Lubna-Asst.Prof-CSE & IS-Presidency University
3. Goal-based agents:
Search algorithms enhance the effective operation of goal-based agents. These agents solve
problems by searching for the most ideal series of actions that can provide the best solution to
a problem.
4. Support production systems:
Search algorithms support the operation of production systems in AI. These are
systems that support AI applications through the use of rules and the procedures for
implementing them.
Production systems use search algorithms to search for the sequence of rules that can
result in the desired action.
5.Neural network systems:
These algorithms are also important in neural network systems. These are
computing systems that consist of interconnected nodes, a hidden layer, an input
layer, and an output layer.
Neural networks are used to perform various tasks in artificial intelligence.
Search algorithms enhance the searching of connection weights that will lead to
the desired input-output mapping.
Properties of search algorithms:
Search algorithms have the following main properties:
Completeness: A search algorithm can be said to be complete if it provides a solution
for a given input when there exists at least one solution for this input.
Optimality: Search algorithms are also characterized by optimal solutions. These are
the best solutions given by the search algorithms at the lowest path cost.
Arshiya Lubna-Asst.Prof-CSE & IS-Presidency University
Time Complexity: These algorithms have a maximum time needed to accomplish a
task or provide a solution. The time taken is usually based on the complexity of the
task.
Space Complexity: They have the maximum memory or storage space needed when
conducting a search operation. This memory is also based on the complexity of the
task.
How search algorithms work:
Artificial intelligence is made possible through AI agents.
These agents perform tasks toward achieving a certain goal and establish the actions
that can result in the desired goal.
The series of these actions provides the solution to the problem.
The AI agents find the best solution for the problem by searching for all the possible
alternatives or solutions.
The process of searching is done using search algorithms.
Two main phases:
1. Defining the problem:
Before formulating a problem, various factors need to be defined to enable the search
algorithms to perform the required course of action.
Defining these factors provides the basis for searching and providing a solution.
The following are the factors that need to be defined :
a. Initial state: This is the start state in which the search starts.
b. State space: These are all the possible states that can be attained from the initial state
through a series of actions.
c. Actions: These are the steps, activities, or operations undertaken by AI agents in a
particular state.
d. Goal state: This is the endpoint or the desired state.
Arshiya Lubna-Asst.Prof-CSE & IS-Presidency University
e. Goal test: This is a test conducted to establish whether a particular state is a goal
state.
f. Path cost: This is the cost associated with a given path taken by the agents.
2. Searching in the search space:
After defining the factors described above, the agents use the search algorithms to
perform a search in the search space.
A search space is an abstract configuration that consists of a search tree of possible
solutions.
A search tree is used to configure the series of actions.
The initial state is configured as the root of the search tree.
The branches are the actions while the nodes are the outcomes of the actions.
When we have a given problem in AI, the search algorithm will identify the initial
state, state space, actions, goal state, and path cost.
From the initial state, a series of actions will be performed as the search algorithms
search for the goal state.
For every state attained by the AI agents, the search algorithms will conduct a goal
test to establish whether the state is the desired state.
If a particular state attained by the agents is not the goal state, then the search
algorithm will continue searching until the goal state is attained.
Types of search algorithms:
Search algorithms can be divided into two broad categories: uninformed search algorithms
and informed search algorithms.
Arshiya Lubna-Asst.Prof-CSE & IS-Presidency University
1. Uninformed search algorithms:
These algorithms are also called blind algorithms.
This is because they don’t have supplementary information that can assist them in
attaining the end goal other than the information given in the problem definition.
These algorithms can further be categorized into the following algorithms:
a. breadth-first search
b. depth-first search
c. uniform cost search
a. Breadth-first search:
This is an algorithm used for searching graph or tree data structures.
It begins at the tree root or search key and traverses all the neighbor nodes in the
current depth level before progressing to the nodes existing in the next depth level.
b. Depth-first search:
This is an algorithm used for searching graph or tree data structures.
Unlike the breadth-first search, it begins at the root node.
It traverses the branch nodes and then backtracks.
The data structure of this search uses the concept of LIFO (last in first out).
Arshiya Lubna-Asst.Prof-CSE & IS-Presidency University
c. Uniform cost search:
These algorithms differ from the breadth-first and depth-first algorithms in that they
consider the cost.
When there are different paths for attaining the desired goal, the optimal solution of
uniform cost algorithms is the solution that is associated with the least cost.
2.Informed search algorithms:
These are heuristic algorithms that consist of the problem definition and
supplementary information that assists in achieving the desired goal state.
They are better at solving complex problems than uninformed algorithms.
Informed search algorithms can be further categorized into the following algorithms:
a. greedy search
b. A* tree search
c. A* graph search
a. Greedy search:
In greedy search algorithms, the closest node to the goal node is expanded.
The closeness factor is calculated using a heuristic function h (x). h (x) is an estimate
of the distance between one node and the end or goal node.
The lower the value of h (x), the closer the node is to the endpoint.
When the greedy search is searching for the best path to the goal node, it will choose
nodes with the lowest possible values.
b.A * tree search:
This algorithm combines the attributes of the uniform cost algorithm and the greedy
algorithm.
Here, the heuristic is simply an amalgamation of the greedy search cost (h (x)) and the
cost in the uniform cost algorithm (g (x)).
Arshiya Lubna-Asst.Prof-CSE & IS-Presidency University
The cumulative cost is denoted as f (x).
h (x) is known as the forward cost while g (x) is the backward cost.
The forward cost estimates the distance between the current node and the goal node.
The backward cost is used to establish the overall cost between a node and the root
node.
A* tree algorithm is optimal when the forward cost (h (x)) is less than or equal to the
actual cost (h* (x)) for all nodes.
This is called the admissibility property of A* tree algorithm.
The strategy is to select the node with the lowest total cost value (f (x)).
c.A* graph search:
The major drawback of the A* tree algorithm is that there is a wastage of time due to
the re-exploration of branches that were initially explored.
This drawback has been overcome by the A* graph algorithm, which configures a rule
that averts the re-exploration of initially explored branches.
The optimal solution in the A* graph algorithm is achieved when the forward cost of
two successive nodes is less than or equal to their backward cost.
This property is termed as the consistency property of this algorithm.
A* Search Algorithm?
A* search algorithm is an algorithm that separates it from other traversal techniques.
This makes A* smart and pushes it much ahead of conventional algorithms.
Example:
Imagine a huge maze that is too big that it takes hours to reach the endpoint manually. Once
you complete it on foot, you need to go for another one. This implies that you would end up
investing a lot of time and effort to find the possible paths in this maze. Now, you want to
make it less time-consuming. To make it easier, we will consider this maze as a search
problem and will try to apply it to other possible mazes we might encounter in due course,
provided they follow the same structure and rules.
Arshiya Lubna-Asst.Prof-CSE & IS-Presidency University
As the first step to converting this maze into a search problem, we need to define these six
things.
1. A set of prospective states we might be in
2. A beginning and end state
3. A way to decide if we’ve reached the endpoint
4. A set of actions in case of possible direction/path changes
5. A function that advises us about the result of an action
6. A set of costs incurring in different states/paths of movement
Steps:
Step 1: Add the beginning node to the open list
Step 2: Repeat the following step
In the open list, find the square with the lowest F cost, which denotes the current square. Now
we move to the closed square.
Consider 8 squares adjacent to the current square and Ignore it if it is on the closed list or if it
is not workable. Do the following if it is workable.
Check if it is on the open list; if not, add it. You need to make the current square as this
square’s a parent. You will now record the different costs of the square, like the F, G, and H
costs.
If it is on the open list, use G cost to measure the better path. The lower the G cost, the better
the path. If this path is better, make the current square as the parent square. Now you need to
recalculate the other scores – the G and F scores of this square.
– You’ll stop:
If you find the path, you need to check the closed list and add the target square to it.
There is no path if the open list is empty and you cannot find the target square.
Step 3. Now you can save the path and work backward, starting from the target square, going
to the parent square from each square you go, till it takes you to the starting square. You’ve
found your path now.
Arshiya Lubna-Asst.Prof-CSE & IS-Presidency University
Applications of search algorithms:
1. Vehicle routing
Search algorithms are used in solving real-life vehicle routing problems, which are
optimization problems.
A vehicle routing problem seeks to establish the optimal series of routes that should
be taken by vehicles to deliver customers.
This is a combinatorial optimization problem that seeks to minimize the cost and
minimize the time taken to reach a given destination.
The search algorithm is used to search for the best solution.
2. Nurse scheduling problem
In the healthcare system, the provision of healthcare services 24 hours a day requires
the full-time presence of nurses.
Given that nurses cannot work without rest, scheduling is done to ensure the shifts are
allocated optimally to enhance productivity.
Search algorithms are applied in this case to solve the nurse scheduling problem.
3. Retrieving records from databases
Search algorithms are also used to retrieve information or records from databases.
The desired record is configured as the desired state.
The algorithm searches in the search space and goal tests are made until the desired
record is found.
4.Industrial processes
These algorithms are used in the optimization of industrial processes.
A good example is in the case of a chemical reaction, where the process may involve
changing some parameters such as temperature or pressure.
Arshiya Lubna-Asst.Prof-CSE & IS-Presidency University
When the initial and desired states are defined, a series of actions are performed until
the desired state (output) is attained.
Arshiya Lubna-Asst.Prof-CSE & IS-Presidency University
