AI Search Algorithms Every Data Scientist Should KnowAaron (Ari) BornsteinBlockedUnblockFollowFollowingMay 7TL;DR The post below outlines a few of the key search algorithms in AI, why they are important, what and what they are used for.

While in recent years, search and planning algorithms have taken a back seat to machine and deep learning methods, better understanding these algorithms can boost the performance of your models.

Additionally as more powerful computational technologies such as quantum computing emerge it is very likely that search based AI will make a comeback .

What is a Search Algorithm in AI?Before we get started lets define what search in AI means.

A search algorithm is not the same thing as a search engine.

Search in AI is the process of navigating from a starting state to a goal state by transitioning through intermediate states.

Almost any AI problem can be defined in these terms.

State — A potential outcome of a problemTransition — The act of moving between states.

Starting State — Where to start searching from.

Intermediate State- The states between the starting state and the goal state that we need to transition to.

Goal State — The state to stop searching.

Search Space — A collection of states.

Uniformed SearchUninformed search is used when there is no information about the cost of navigating between states.

There are three main classical algorithms for uninformed search:DFS — Traverse the search space using a LIFO Stack to determine the next node.

Advantages: Good for deep graphs, memory efficient.

Disadvantages: Can get stuck in loops.

Depth-first search – Wikipedianeeds additional citations for verification .

improve this article by adding citations to reliable sources.

Unsourced…en.

wikipedia.

orgIDFS — Traverse the search space, using a LIFO Stack, to determine the next node when it reaches a certain depth then it clears the stack, increments the depth limit and starts the search again.

Iterative deepening depth-first search – Wikipedianeeds additional citations for verification .

improve this article by adding citations to reliable sources.

Unsourced…en.

wikipedia.

orgBFS- Traverse the search space using a queue FIFO to determine the next node.

Breadth-first search – Wikipedianeeds additional citations for verification .

improve this article by adding citations to reliable sources.

Unsourced…en.

wikipedia.

orgInformed SearchAn informed search is used when we know the cost or have a solid estimate of the cost between states.

UCF- Traverse the search space with a priority queue and a score.

The score for a given state is calculated by the cost of getting to the state from the parent along the path it was discovered.

Artificial Intelligence – Uniform Cost Search(UCS)In this post I will talk about the Uniform Cost Search algorithm for finding the shortest path in a weighted graph…algorithmicthoughts.

wordpress.

comA* — Traverse the search space with a priority queue and a score.

The score of a state is calculated by the cost of getting to the state from the parent along the path it was discovered, combined with a heuristic value for the given state.

The admissible value of heuristic must abide by the two following properties.

A state’s heuristic value must be less than the lowest cost path of getting from a state to the goal node.

The heuristic value must be less than the value of the cost between the path to the state and the heuristic value of each parent node.

A* search algorithm – WikipediaPeter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute (now SRI International) first published the…en.

wikipedia.

orgIDA* — An IDFS version of A*Iterative deepening A* – WikipediaIterative deepening A* ( IDA*) is a graph traversal and path search algorithm that can find the shortest path between a…en.

wikipedia.

orgLocal SearchWe use local search algorithms when there is more than one possible goal state but some outcomes are better than others and we need to discover the best.

Used a lot in optimization of machine learning algorithms.

Hill Climbing- A greedy search method that detriments the next state based on the value thats the smallest until it hits a local maximum.

Hill climbing – Wikipedianeeds additional citations for verification .

improve this article by adding citations to reliable sources.

Unsourced…en.

wikipedia.

orgSimulated annealing- Starts with a hill climb until it hits a local maximum then uses a temperature function to decide whether to stop or continue to a worse state with the hopes of finding a betterSimulated annealing – WikipediaThis notion of slow cooling implemented in the simulated annealing algorithm is interpreted as a slow decrease in the…en.

wikipedia.

orgGSAT — An implementation of Hill Climbing for the CNF domain.

Chooses a random set of boolean values for each possible parameter, if the values match all the preconditions goal state return else we flip the values to satisfy the largest amount of possible preconditions of the goal state and then repeat this process with a new random set of values for each of the boolean values we flipped on the last iteration.

WalkSAT – WikipediaWalkSAT first picks a clause which is unsatisfied by the current assignment, then flips a variable within that clause…en.

wikipedia.

orgGenetic Search- Generate initial population of states, prune those under a threshold that have the lowest values using a fitness function.

Randomly combine the survivors, then mutate a couple of bits and evaluate fitness and repeat.

Genetic algorithm – WikipediaIn computer science and operations research, a genetic algorithm ( GA) is a metaheuristic inspired by the process of…en.

wikipedia.

orgBeam Search- Preform uniform cost search with the likelyhood values of the current and previous steps of a model.

Beam search – WikipediaIn computer science, beam search is a heuristic search algorithm that explores a graph by expanding the most promising…en.

wikipedia.

orgMonte Carlo Search — A randomized search algorithm that will return the best estimate of the correct search result when terminated.

Monte Carlo algorithms are always fast, but only probably correct.

Monte Carlo tree search – WikipediaIn computer science, Monte Carlo tree search ( MCTS) is a heuristic search algorithm for some kinds of decision…en.

wikipedia.

orgLas Vegas Search Is a randomized search algorithm unlike Monte Carlo it will only return when the correct result is found.

Las Vegas algorithms are always correct, but only probably fast.

// Las Vegas algorithm2 repeat:3 k = RandInt(n)4 if A[k] == 1,5 return k;Las Vegas algorithm – WikipediaIn computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always…en.

wikipedia.

orgAtlantic City Search — Is a bounded probabilistic polynomial time search algorithm that combines the strengths and weaknesses of the Las Vegas and Monte Carlos Search algorithms.

Atlantic City algorithm – WikipediaAn Atlantic City algorithm is a probabilistic polynomial time algorithm that answers correctly at least 75% of the time…en.

wikipedia.

orgNext StepsIf you enjoyed this article, keep your eyes out for new content shortly and follow me here on medium or twitter @pythiccoder.

To get started experimenting with these algorithms check out Azure Notebooks as well as the graph data base features of CosmosDB on Azure.

If you don’t have one yet you can pick up a free Azure Subscription below.

Create your Azure free account today | Microsoft AzureGet started with 12 months of free services and USD200 in credit.

Create your free account today with Microsoft Azure.

azure.

microsoft.

comAbout the AuthorAaron (Ari) Bornstein is an avid AI enthusiast with a passion for history, engaging with new technologies and computational medicine.

As an Open Source Engineer at Microsoft’s Cloud Developer Advocacy team, he collaborates with Israeli Hi-Tech Community, to solve real world problems with game changing technologies that are then documented, open sourced, and shared with the rest of the world.

.. More details