Automation And A.I. Systems will be the nexus for next generation Applications.

Join us on our journey of exploring the Techniques of these fields

Photo by Bram Janssens/Hemera / Getty Images

 

 

 Finding the needle in the Haystack: Breadth First Search... The Elixir Way

Finding the needle in the Haystack: Breadth First Search... The Elixir Way

 Graph Search Algorithms can be used in most situations when the need to search through large amounts of data surfaces. In this post we will explore an instance of the Graph Search called the Breadth First search algorithm.

Undoubtedly, you might have heard of this algorithm before, and you might have seen many search tree implementations out there on the web, but it helps to simplify the concepts behind this powerful technique through a simple example so that the everyday person can understand it. 

THE PROBLEM

Imagine you are late for a fund raising event, and you dash out the front door of your home to get into your car. Before you begin to drive away you realize that you left your wallet somewhere inside the house. This is not good considering you are on your way to a fund raising event!! You need that wallet, but you don't have time to search for it yourself.  If only there was a better way.

SOLUTION

In the virtual world, there is a way to solve this type of problem and get the result almost instantly. In order to back up my claim, I will implement the Breadth First search AI algorithm in a simple Elixir program. This program will view the house and start its search in a room I've chosen, then it will check each room in its' path for the requested item until it finds exactly what was requested! However, there is a catch. We don't want our system to have to do a brute force search by looking for the item in every single room! That search strategy would be bad form, and our system would not scale if it was applied to bigger houses. To avoid the madness of searching every room we will simplify the search by going for the most shallow, or closest point first! This will be explained in detail shortly. Before diving into the code, lets examine a few rules for this algorithm...

  • Only use this technique if there is a known solution to be found in the search, (I can't stress this enough. Not following this rule can potentially leave your system searching for days, even YEARS especially if the graph size is large enough!!)
  • Use queues, lists, or maps to represent your graph, for easy manipulation.

THE CODE

The first thing this algorithm needs is a place to run. The place it runs is known as a graph. A graph can be anything from a city map, a chess board, or a entire planet. It makes no difference. The graph can be modeled as any data structure, but most of the time the list or a queue is the main representation.

We will represent our graph using a map of lists. This map of list will represent our house. Every house has rooms, and all rooms have items in them. Before we get too carried away, lets begin our BreadthFirst module.

moduleCreation

Now that our module is created with a nice description, lets go ahead and start building out our system! Lets create the data structure that represents our graph.

- Our graph will be a map of lists. Each key in the map corresponds to a room. - Each room has a list of arbitrary items. In the real world these lists could be rather large!

- Our graph will be a map of lists. Each key in the map corresponds to a room.

- Each room has a list of arbitrary items. In the real world these lists could be rather large!

The next thing we need is a way to track our progress through the graph. This is equivalent to tracking your way through a giant maze by leaving yourself bread crumbs. Without doing this, you would easily get lost. The way the system can track itself is by separating parts of the graph into two sections. The two sections are known as the closed set, and the open set, aka Explored set, and the Frontier.

The Frontier is what the system has not experienced yet. This will be represented as a list. Lets create an agent that will track our Frontier state.

- We create an agent that will hold all un-explored rooms. -Because our graph is represented by the map called house. We can just call the Map.keys/1 function to get all the possible rooms in the house. - We will have the agent take a function that returns a list of the possible rooms, as well as a name for the agent called unExploredRooms.

- We create an agent that will hold all un-explored rooms.

-Because our graph is represented by the map called house. We can just call the Map.keys/1 function to get all the possible rooms in the house.

- We will have the agent take a function that returns a list of the possible rooms, as well as a name for the agent called unExploredRooms.

Now that our Frontier is handled. Lets track our explored rooms in a list as well. It also will make sense for us  to count how many rooms we are checking during this process. We will have the explored rooms start an agent that does this.

- We start an agent with a function that yields an empty list. We also name the agent ExploredRooms so that it is easier to reference later. - start_room_check_count is our room counter that will count the number of rooms our system checked before it found our item.

- We start an agent with a function that yields an empty list. We also name the agent ExploredRooms so that it is easier to reference later.

- start_room_check_count is our room counter that will count the number of rooms our system checked before it found our item.

Now that we referenced our start_room_check_count function lets go ahead and write the code for that function next.

- We create an agent that yields 0 and give it the name RoomCheckCount.

- We create an agent that yields 0 and give it the name RoomCheckCount.

Now, in order to track the state of all these agents we will need some functions that will handle that process for us. Right now we have 3 different things that need to be tracked. Those 3 things are 

  1. Room Check Count
  2. Unexplored Rooms
  3. Explored rooms

Lets use the Agent.get/2 function to take care of that for us.

- We simply call the Agent.get/2 function for all of the 3 different agents. You can see why we gave the agents names earlier. It allows us to access the agents current state by name.

- We simply call the Agent.get/2 function for all of the 3 different agents. You can see why we gave the agents names earlier. It allows us to access the agents current state by name.

In order for our system to find an item in our house we need to define the logic for doing so. That logic is pretty straight forward. We will need the system to check every item in the room to see if it exists. If it finds the item it will let us know. If it doesn't find the item it will expand the search to another room. Lets build that next.

- We define a function called look_for which takes two arguments, the item being looked for, and the room. - We then bind all the items in that particular room to the room_items variable using the Map.get/2 function. - Next we use standard IO to communicate what was found if the item is in the list of room items. - We also want all the rooms that were checked to be displayed, but because we are dealing with queues which have a FIFO(First In First Out) behavior, we want to reverse the list so that the room search path is displayed in the correct order. -Finally we want our room count total to show. - If the item is not in that room we expand our search further.

- We define a function called look_for which takes two arguments, the item being looked for, and the room.

- We then bind all the items in that particular room to the room_items variable using the Map.get/2 function.

- Next we use standard IO to communicate what was found if the item is in the list of room items.

- We also want all the rooms that were checked to be displayed, but because we are dealing with queues which have a FIFO(First In First Out) behavior, we want to reverse the list so that the room search path is displayed in the correct order.

-Finally we want our room count total to show.

- If the item is not in that room we expand our search further.

 

What does it mean to expand the search? Just like our maze example we will need to keep track of where we've been so that we don't get lost, so the process of expanding is the systems way of categorizing where its been and where it needs to go next. Lets write that expand function next.

- Expand will take a room. - It will reference each agent by calling the Agent.update/2 function. - Because we are dealing with queues the unexplored rooms will need to remove the last element from the current list because that room will have been explored by the system. - The explored rooms list will then need to insert the room that was removed from the unexploredRooms list. - Finally the room check count will need to be incremented after that room has been officially checked.

- Expand will take a room.

- It will reference each agent by calling the Agent.update/2 function.

- Because we are dealing with queues the unexplored rooms will need to remove the last element from the current list because that room will have been explored by the system.

- The explored rooms list will then need to insert the room that was removed from the unexploredRooms list.

- Finally the room check count will need to be incremented after that room has been officially checked.

We are nearly there. We need a function that puts all the look_for logic into action. We will write a function called find_in_rooms which will serve as our generic action sequence that will operate on our unexplored rooms list. 

- We will use the Enum.map/2 function to feed our selected item to the look_for function. - The &1 argument represents the current unexplored room by name.

- We will use the Enum.map/2 function to feed our selected item to the look_for function.

- The &1 argument represents the current unexplored room by name.

There is one final step! All we have left to build is our search function. This should be fairly simple. All we need to do is have it take a room and an item. Once it receives a room and an item it can then start the search. We also might want to keep the search algorithm from starting a search for a room that doesn't exists  just to save us time. That final function will look something like below...

- Search will take a tuple. We pass data in Elixir via tuples. The first element will be the room we want to start the search, and the second will be the item we want to find. - The first thing we do is call our start_unexplored_rooms_list agent. This needs to be done before any searching can begin - Next we look for the given room in our Agent of unexplored rooms. - We then start the exploring rooms Agent so that we can place the first room we checked in our list of explored rooms by passing that room to our expand function! - Finally we call our find_in_room function that we wrote earlier with the item we want to look for as a parameter.

- Search will take a tuple. We pass data in Elixir via tuples. The first element will be the room we want to start the search, and the second will be the item we want to find.

- The first thing we do is call our start_unexplored_rooms_list agent. This needs to be done before any searching can begin

- Next we look for the given room in our Agent of unexplored rooms.

- We then start the exploring rooms Agent so that we can place the first room we checked in our list of explored rooms by passing that room to our expand function!

- Finally we call our find_in_room function that we wrote earlier with the item we want to look for as a parameter.

Great! Our code is complete.

In the original problem we needed to search for the missing wallet. The most likely place we might have left it could have been the master bedroom. Lets tell our search algorithm to start there by simply calling BreadthFirst.search({:master_bedroom, "Wallet"}). The item might not be there, but we want our system to go until it finds it. What happens when we run this? Lets take a look...

- BANG!!!  

- BANG!!!

 

WOW! If you run this locally you will notice the results are returned instantly. Why? because we didn't search the whole graph! We only checked 4 places. If you look closely at the output you will see that it didn't find the wallet in the master bedroom, but it did begin the search there. It then started looking in the back yard, then the bath room, and then the dining room, until it finally found it in the game room!! Success! now you can make it to the fund raiser and you know exactly where your wallet is!

Thats pretty cool! I use this algorithm whenever I want an automation system to find something of importance in a VERY LARGE data set. It saves me from writing a ton of code, and it usually finds what I'm looking for almost instantly. The sky is the limit for this algorithm, and there are probably thousands of use cases for it. I've used this algorithm often while building automation systems and it has never failed me.

 

 

Performing 20,000 concurrent file searches in less than 1 minute.

Performing 20,000 concurrent file searches in less than 1 minute.

Coding A.I. Techniques in Elixir: The Generate and Test Algorithm

Coding A.I. Techniques in Elixir: The Generate and Test Algorithm