Task 1: Search Algorithms

1. Do some background research on the search algorithms and methods we have looked at
today and produce a scenario where each one might be used and a set of pros and cons
for each of them
Uninformed Search Algorithms: 

The search algorithms in this section have no additional information on the goal
node other than the one provided in the problem definition. The plans to reach
the goal state from the start state differ only by the order and/or length of
actions. Uninformed search is also called Blind search. 

Depth First Search (DFS) - is an algorithm for traversing or searching tree or graph data
structures. The algorithm starts at the root node (selecting some arbitrary node as the
root node in the case of a graph) and explores as far as possible along each branch
before backtracking.
Advantages Of DFS:
1. The memory requirement is Linear WRT Nodes.
2. Less time and space complexity rather than BFS.
3. The solution can be found out without much more search.

The disadvantage of DFS:

1. Not Guaranteed that it will give you a solution.
2. Cut-off depth is smaller so time complexity is more.
3. Determination of depth until the search has proceeded.

Applications of DFS:-
1. Finding Connected components.
2. Topological sorting.
3. Finding Bridges of the graph.

Breadth First Search (BFS) - is a traversing algorithm where you should start traversing
from a selected node (source or starting node) and traverse the graph layer wise thus
exploring the neighbour nodes (nodes which are directly connected to source node)
Advantages of BFS:

1. The solution will definitely found out by BFS If there is some solution.
2. BFS will never get trapped in a blind alley, which means unwanted nodes.
3. If there is more than one solution then it will find a solution with minimal
steps.

Disadvantages Of BFS:
1. Memory Constraints As it stores all the nodes of the present level to go for
 the next level.
2. If a solution is far away then it consumes time.

Application Of BFS:
1. Finding the Shortest Path.
2. Checking graph with petiteness.
3. Copying Cheney's Algorithm

Uniform Cost Search (UCS) - is the best algorithm for a search problem, which does not
involve the use of heuristics. It can solve any general graph for optimal cost. Uniform
Cost Search as it sounds searches in branches which are more or less the same in cost,
this demands the use of a priority queue.
Advantages

 It helps to find the path with the lowest cumulative cost inside a weighted graph
having a different cost associated with each of its edge from the root node to
the destination node.
 It is considered to be an optimal solution since, at each state, the least path is
considered to be followed.

Disadvantage

 The open list is required to be kept sorted as priorities in priority queue needs to
be maintained.
 The storage required is exponentially large.
 The algorithm may be stuck in an infinite loop as it considers every possible path
going from the root node to the destination node.

Hill Climbing Algorithm

This is an iterative algorithm that starts with an arbitrary solution to a problem and
attempts to find a better solution by changing a single element of the solution
incrementally. If the change produces a better solution, an incremental change is
taken as a new solution. This process is repeated until there are no further
improvements.

Advantages of Hill Climbing Algorithm:

 Hill climbing technique is useful in job shop scheduling, automatic

programming, circuit designing, and vehicle routing and portfolio
management.
 It is also helpful to solve pure optimization problems where the objective is
to find the best state according to the objective function.
  It requires much fewer conditions than other search techniques.

Disadvantages of Hill Climbing Algorithm:

 The question that remains on the hill-climbing search is whether this hill is
the highest hill possible. Unfortunately without further extensive
exploration, this question cannot be answered. This technique works but as
it uses local information that’s why it can be fooled. The algorithm doesn’t
maintain a search tree, so the current node data structure need only record
the state and its objective function value. It assumes that local improvement
will lead to global improvement.
 There are some reasons by which hill-climbing often gets suck which is: Local
Maxima, Ridges and Plateau

Heuristic Search
A heuristic evaluation should not replace usability testing. Although the
heuristics relate to criteria that affect your site’s usability, the issues identified in
a heuristic evaluation are different than those found in a usability test.

Advantages Disadvantages

It can provide some quick and relatively

inexpensive feedback to designers. It requires knowledge and experience to
You can obtain feedback early in the design apply the heuristics effectively.
process. Trained usability experts are sometimes
Assigning the correct heuristic can help suggest hard to find and can be expensive.
the best corrective measures to designers. You should use multiple experts and
You can use it together with other usability aggregate their results.
testing methodologies. The evaluation may identify more minor
You can conduct usability testing to further issues and fewer major issues.
examine potential issues.

A* Search
A * Search algorithm is an informed search algorithm, meaning it uses knowledge for the
path searching process.The logic used in this algorithm is similar to that of BFS- Breadth
First Search.

A * algorithm has 3 paramters:

g(n): The actual cost of traversal from initial state to the current state.
h(n): The estimated cost of traversal from the current state to the goal state.
f(n): The actual cost of traversal from the initial state to the goal state.
Advantages:

 It is optimal search algorithm in terms of heuristics.

 It is one of the best heuristic search techniques.
 It is used to solve complex search problems.
 There is no other optimal algorithm guaranteed to expand fewer nodes than A*.

Disadvantages:

 This algorithm is complete if the branching factor is finite and every action has
fixed cost.
 The performance of A* search is dependant on accuracy of heuristic algorithm
used to compute the function h(n).

Real world applications:

 It can be used as a path finding algorithm for map based applications.

 String searching applications can also use this by determining the goal state.NLP
uses this to check any parsing errors.
 A lot of games use this algorithm for its positioning system.

Simulated Annealing
Annealing is the process of heating and cooling a metal to change its internal structure
for modifying its physical properties. When the metal cools, its new structure is seized,
and the metal retains its newly obtained properties. In simulated annealing process,
the temperature is kept variable.

We initially set the temperature high and then allow it to ‘cool' slowly as the algorithm
proceeds. When the temperature is high, the algorithm is allowed to accept worse
solutions with high frequency.

Advantages of the Simulated Annealing Algorithm:

 It can deal with arbitrary systems and cost functions.

 Statistically guarantees to find an optimal solution.
 It is relatively easy to code, even for complex problems.
 Generally gives a “good’’ solution

Disadvantages of the Simulated Annealing Algorithm:

 Repeatedly annealing with a


 The schedule is very slow, especially if the cost function is expensive to
compute.
 For problems where the energy landscape is smooth, or there are few
local minima, SA is overkill — — simpler, faster methods (e.g., gradient
 descent) will work better. But usually, don’t know what the energy
landscape is.
 Heuristic methods, which are problem-specific or take advantage of
extra information about the system, will often be better than general
methods. But SA is often comparable to heuristics.
 The method cannot tell whether it has found an optimal solution. Some
other method (e.g. branch and bound) is required to do this.

Genetic Algorithms
The Genetic Algorithms were born in 1970 thanks to John Henry Holland. It is
essentially a strategy used for optimization and search problems based on
random heuristics. The idea consists of a simulation of natural selection. The
initial population will evolve through (1) emergent variations derived from the
crossover between fittest and (2) through mutations.

Pros and cons of these algorithms are basically:

Pros: (1) Faster than other algorithms. (2) Easier. If vector representation of
individual is right, we can find out a solution without a deep analysis work.

Cons: (1) The random heuristics sometimes doesn’t find the optimum. (2) It is
not a complete algorithm (not always the algorithm finds a suitable solution).
Sometimes it can get stuck with a local maximum problem. Nevertheless,
crossover operation (we will point out further down) helps to mitigate it,
although this implies more iterations.
Using the A* algorithm to solve a maze.

I first had to import the necessary packages shown below:

I then had to create a class that contains the method needed to solve the
problem.

I then defined the method that takes action to arrive at the solution using the code
below.

I then updated the state basing on the action

 To check if I have reached the goal, I used the code below.

To compute the cost of taking the action, I used the code below.

Below is the heuristic used to arrive at the final solution.

I did some background research on the search algorithms and methods

proposed and produced a scenario where each one might be used and a set of
pros and cons for each of them.