AI Search Algorithms Every Data Scientist Should Know
Tags: ai, algorithms, azure, machinelearning
Published: 2019-11-18 09:01:16

---
title: AI Search Algorithms Every Data Scientist Should Know
published: true
date: 2019-05-07 18:55:19 UTC
tags: ai,algorithms,azure,machinelearning
canonical_url: https://towardsdatascience.com/ai-search-algorithms-every-data-scientist-should-know-ed0968a43a7a
---

![](https://cdn-images-1.medium.com/max/620/0*M-O2a5eQvWrB5lqN.jpg)

TL;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](https://en.wikipedia.org/wiki/Automated_planning_and_scheduling) 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.

![](https://cdn-images-1.medium.com/max/777/1*juds84wKbdAGe4FKqIw5sA.png)<figcaption>A search algorithm is not the same thing as a search engine.</figcaption>

**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 problem
- **Transition**  — 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.

### Uninformed Search

![](https://cdn-images-1.medium.com/max/300/0*0P1HFZynxL3OdGPO.png)

Uninformed 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](https://en.wikipedia.org/wiki/Stack_(abstract_data_type)) to determine the next node. **Advantages** : Good for deep graphs, memory efficient. **Disadvantages:** Can get stuck in loops.

[Depth-first search](https://en.wikipedia.org/wiki/Depth-first_search)

- **IDFS — ** Traverse the search space, using a [_LIFO Stack_](https://en.wikipedia.org/wiki/Stack_(abstract_data_type))_,_ 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 - Wikipedia](https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search)

- **BFS-** Traverse the search space using a [_queue FIFO_](https://en.wikipedia.org/wiki/Queue_(abstract_data_type)) to determine the next node.

[Breadth-first search - Wikipedia](https://en.wikipedia.org/wiki/Breadth-first_search)

### Informed Search

![](https://cdn-images-1.medium.com/max/901/0*l4jWWaONrcPZgYo6.png)

An 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](https://en.wikipedia.org/wiki/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)](https://algorithmicthoughts.wordpress.com/2012/12/15/artificial-intelligence-uniform-cost-searchucs/)

**A\* — ** 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 - Wikipedia](https://en.wikipedia.org/wiki/A*_search_algorithm)

**IDA\* ** — An IDFS version of A\*

[Iterative deepening A\* - Wikipedia](https://en.wikipedia.org/wiki/Iterative_deepening_A*)

### Local Search

![](https://cdn-images-1.medium.com/max/500/0*k3abJNZb-9nrs_1t.gif)

We 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 - Wikipedia](https://en.wikipedia.org/wiki/Hill_climbing)

**Simulated 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 better

[Simulated annealing - Wikipedia](https://en.wikipedia.org/wiki/Simulated_annealing)

**GSAT**  — 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 - Wikipedia](https://en.wikipedia.org/wiki/WalkSAT)

**Genetic 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](https://en.wikipedia.org/wiki/Genetic_algorithm)

**Beam Search** - Preform uniform cost search with the top n values likelyhood values of the current and previous outputs of a model.

[Beam search - Wikipedia](https://en.wikipedia.org/wiki/Beam_search)

**Monte 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.

![](https://cdn-images-1.medium.com/max/808/0*xlmSiIxUPAC-XTMj.png)

[Monte Carlo tree search - Wikipedia](https://en.wikipedia.org/wiki/Monte_Carlo_tree_search)

**Las 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 algorithm_
2 repeat:
3 k = RandInt(n)
4 **if** A[k] == 1,
5 **return** k;
```

[Las Vegas algorithm - Wikipedia](https://en.wikipedia.org/wiki/Las_Vegas_algorithm)

**Atlantic 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 - Wikipedia](https://en.wikipedia.org/wiki/Atlantic_City_algorithm)

### Next Steps

If you enjoyed this article, keep your eyes out for new content shortly and follow me here on medium or twitter [@pythiccoder](https://twitter.com/pythiccoder). To get started experimenting with these algorithms check out [Azure Notebooks](https://docs.microsoft.com/en-us/azure/notebooks/?WT.mc_id=medium-blog-abornst) as well as the graph data base features of [CosmosDB](https://docs.microsoft.com/en-us/azure/cosmos-db/?WT.mc_id=medium-blog-abornst) 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 Azure](https://azure.microsoft.com/en-us/offers/ms-azr-0044p/?WT.mc_id=medium-blog-abornst)

### About the Author

[**Aaron (Ari) Bornstein**](https://www.linkedin.com/in/aaron-ari-bornstein-22aa7a77/) 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.

* * *